Projects
Control of Multi-Agent Systems via Clustered Policies
Systems of intelligent agents regularly interact within environments subject to their own policies. Multi-agent reinforcement learning (MARL) and game theory are two paradigms that describe how agents may learn (optimal) policies. The selfish choices of agents, however, may be contrary to the social good of the community. To change the equilibrium behavior of the group, an intelligent controller must understand the learning mechanisms at the individual level, characterize how global intervention disrupts these learned action processes, and choose control policies that induce the desired change within the group's behavior.
In this project, I studied how games and multi-agent Markov decision processes (MDPs) can be controlled by defining a "third party" MDP from a central planner's (CP's) perspective. While basic control objectives, i.e. game-play at desireable states, may be achieved via simple policies, better performance is achieved when agents are partitioned into clusters and each cluster receives personalized controls from the CP. To combat the rising complexity of this problem, I investigated approximate policy computation techniques that eliminated an exponential complexity dependence on the number of clusters, and found cases in which these techniques found optimal policies. I also investigated the submodularity properties of the multi-agent MDP's value function, and used those results to propose a method to assign agents to clusters with provable improvement in value and reduced computation complexity.
Robust Control of Multi-Agent MDPs under Node Dropout
While a control policy may be optimal, it may only maintain its great value under the precarious assumption that the system is time-homogeneous. MDPs with time-varying transition kernels can often be handled by refreshing learned models, but changes to the composition of the agents means that the structure of the MDP itself may change. When an agent (semi-)permanently leaves the system, we say that node dropout occurs, such as when a user deactivates their account or physical infrastructure is damaged. Even if the optimal pre-dropout policy can be applied after the agent leaves, there are no guarantees on how well it will perform.
In this project I study model-free policy design (i.e. when the transition matrix is unknown) that is robust to agent dropout, and how to pre-calculate optimal policies in the event dropout occurs. Using techniques from game theory, I can first measure the importance of each agent to the CP based on their ability to minimize the CP's value function. Then, robustness criteria can be defined based either on agent importance, or on the probability of each agent leaving the system. The robustness criteria is embedded into the definition of the MDP, which can be solved for the resulting robust policy.
In solving the MDP with model-free techniques, we wish to maintain a similar theme of only exerting policies in which we have a high confidence of producing a good value. To calculate the confidence bounds on the post-dropout MDP, I developed a policy importance sampling technique that can evaluate policies for the post-dropout MDP given samples from the pre-dropout MDP. Current work uses these bounds in a safe policy search routine to find the desired robust policies.
Physics-Inspired Optimization
In a machine learning application, we think of using equations to model a physical system, optimizing the model so it accurately describes the system (e.g. via parameters), and then using the optimized model to infer useful information about the physical system. In contrast, properties of certain physical systems are known to evolve over time according to laws of physics. For example, electrical circuits follow Kirchoff's current and voltage laws, and capacitors' currents are proportional to the derivative of their voltages. Circuits are a promising example in particular, as they can be designed to produce almost any desired output signal. We can thus flip the usual machine learning paradigm; instead of using equations to model a physical system, we can model a desired equation with a physical system.
Given a desired objective function, we can construct a scaled gradient flow ODE to trace the continuous time trajectory of the optimization variable. Next, an equivalent circuit (EC) is constructed such that the voltage at a key node is equivalent to the optimization variable, and a related adjoint EC models its time derivative. Based on these ECs, control schemes are proposed based on minimizing the charge stored in the EC capacitors. To solve the controlled gradient flow, we adapt discretization techniques standard in circuit simulation to the optimization field. Continued and future work develop these ideas for RL and distributed/federated learning applications.
