TL;DR
This paper introduces Conjugate Markov Decision Processes (CoMDPs), a framework that reformulates the search for optimal representations or skills as an MDP in its own right. By using a "coagent" to solve this conjugate problem alongside a primary agent, the authors provide a principled way to optimize internal mappings directly for maximum expected return, rather than relying on hand-tuned heuristics.
The Challenge of Finding Optimal Mappings
In Reinforcement Learning (RL), an agent doesn't just need a good policy; it often needs a good mapping. This might be a mapping from raw sensors to a feature space (representation discovery) or a mapping that defines when a sub-task should end (skill discovery).
Traditionally, researchers solve these "meta-problems" using heuristics. For example, one might find features that best preserve the geometry of the state space. However, these heuristics are only proxies; they don't guarantee that the resulting features will actually help the agent maximize its reward. The core challenge addressed in this paper is: How can we search for these mappings by directly optimizing the agent's expected return?
Methods: The CoMDP Framework
The authors propose a novel two-agent architecture to tackle this problem:
- The Agent ($A$): Solves the original, "augmented" MDP using a provided mapping $f$.
- The Coagent ($C$): Solves the Conjugate MDP (CoMDP). In this conjugate view, the "actions" of the coagent are the choices of the mapping $f$ itself.
Key Innovations
- The CoMDP Framework: The authors prove that the search for an optimal mapping $f$ can be structured as a standard MDP. Crucially, they show that the state-value function for the CoMDP is identical to that of the original MDP.
- Approximate Coordinate Ascent (APCA): A training algorithm where both the agent and coagent learn simultaneously (or alternate every $k$ steps). When $k=0$, both update at every time step, treating the other's learning as a form of environmental non-stationarity.
- Coagent Networks (CN): The framework allows for "nesting." You can have a network of multiple coagents and one primary agent. For example, some coagents might learn features while others learn "motor primitives" (coordinated action patterns), all working together to solve the same high-level task.
Experimental Setup
The authors evaluate their approach on a custom, high-dimensional simulated navigation task designed to be too difficult for simple "canonical" RL methods:
- Environment: A 10x10 continuous room.
- State Space: 20-dimensional simulated LIDAR data (distance to walls at 20 angles).
- Action Space: 50 actuators pointing in different directions. To move effectively, the agent must learn to coordinate these 50 "muscles" (turning on only those on one side), otherwise, the movements cancel each other out.
- Baselines: The approach is compared against a robust policy gradient method (Kohl & Stone, 2004) and a state-of-the-art Natural Actor-Critic (NAC).
Key Insights and Results
Theoretical Insights
- The Value Function Identity: The most striking theoretical result is that the value of a state in the CoMDP is the same as in the original MDP. This means the coagent is naturally incentivized to help the agent succeed.
- Gradient Alignment: The policy gradients for the agent and coagent are simply the components of the overall policy gradient for the entire system. This justifies why simultaneous learning works.
- Decomposition of Complexity: By using a Coagent Network, a massive problem (like coordinating 50 actuators) can be decomposed into many low-dimensional, simpler tasks. In the case study, 1,000 coagents learned binary features, while 10 other coagents learned motor primitives.
Empirical Performance
Learning curves comparing Coagent Networks to baselines Source, p. 6
- Superior Performance: The Coagent Network (CN) reached the goal significantly faster than the baselines.
- Stability: While Natural Actor-Critic (NAC) performed well when it worked, it failed to complete the task in 1/3 of the trials. The Coagent Network was much more reliable.
- Efficiency: The CN approach was roughly 10 times more computationally efficient per time step than NAC, which requires expensive matrix inversions.
- Emergent Coordination: The system successfully learned "motor primitives"—sets of actuator activations that produced rapid movement in specific directions—without any a priori knowledge of the robot's physical structure.
Limitations and Future Work
- Non-stationarity: Because the agent and coagent learn at the same time, each sees the other as a changing part of the environment. While the paper provides some convergence suggestions, the full theory of simultaneous learning in these networks remains an open area.
- Manual Architecture: In the case study, the authors manually decided to use 1,000 feature coagents and 10 motor primitive coagents. A major next step would be an algorithm that can automatically determine the optimal structure of the coagent network.
- Broader Mappings: The authors suggest this framework could be applied to other mappings, such as skill termination sets or exploration policies, which were not explored in the case study.
Summary updated