To make an optimal decision in a sequential environment, an agent must understand the consequences of its actions. Mathematically, classical planning frameworks model this via two components: a reward function $R(s,a)$ and a transition probability function $P(s'|s,a)$, which dictates the likelihood of landing in a next state $s'$ given the current state $s$ and action $a$.
When these functions are perfectly known, finding an optimal policy is a pure computational challenge. For instance, Matthew Zurek et al. in Faster Fixed-Point Methods for Multichain MDPs demonstrate how to rapidly solve complex, well-connected planning problems by steering agents toward high-reward regions. However, their approach—like traditional Dynamic Programming (DP)—fundamentally relies on having this complete mathematical map of the world upfront.
In the real world, a perfect model of the environment's dynamics is rarely available. The transition rules may be too complex to write down, continuous, or completely unknown. This realization drove a paradigm shift: How can agents learn to make optimal decisions when they do not know the rules of environmental change?
Bypassing the Model via Sampled Experience
The core insight that frees agents from requiring an explicit transition model is sampling. Instead of computing an expectation over all possible future states using a known probability matrix $P(s'|s,a)$, an agent can treat the environment itself as an oracle. By taking an action and observing the resulting state and reward, the agent obtains an unbiased sample of the environment's underlying dynamics.
An early breakthrough in this direction came from the integration of Temporal Difference (TD) learning with sequential decision-making. As explored in Sequential Decision Problems and Neural Networks, TD algorithms can approximate the evaluation functions of Dynamic Programming without ever needing a model of the environment, making reinforcement learning (RL) viable in complex, unmapped territories.
Model-Based Planning (Requires P):
State (s) + Action (a) ---> [ Look up P(s'|s,a) ] ---> Compute Expected Future Value
Model-Free Learning (Sample-Driven):
State (s) + Action (a) ---> [ Interact with World ] ---> Observe Sample (s', r) ---> Update Q(s,a)
This concept was formalized by Christopher J. Watkins et al. in Technical Note Q-Learning. By proving that Q-learning guarantees convergence to an optimal policy purely through sampled interactions, they established that tracking state-action values ($Q(s,a)$) bypasses the need to know where an action leads before you take it.
Eliminating the Post-Evaluation Model Dependency
Even when an algorithm estimates a state-value function $V(s)$ without a model, a subtle bottleneck often remains: action selection. In traditional Approximate Linear Programming (ALP), an agent determines the best action by evaluating:
$$\arg\max_a \sum_{s'} P(s'|s,a) V(s')$$
This means that even if you know the value of every state perfectly, you still need the transition model $P$ to know which action will successfully steer you there. To break this dependency, Jason Pazis et al. proposed Non-Parametric Approximate Linear Programming for MDPs. By enforcing a smoothness (Lipschitz) assumption directly over the state-action space, their framework enables model-free action selection during execution.
Taking this concept into deep representations, Andreea Deac et al. introduced eXecuted Latent Value Iteration Networks (XLVINs) in Neural Algorithmic Reasoners are Implicit Planners. Rather than forcing a neural network to predict fragile, explicit scalar rewards and state transitions, XLVINs perform planning computations entirely within a high-dimensional latent space, emulating value iteration implicitly and robustly handling continuous or partially observable environments.
The Decentralized Multi-Agent Challenge
The challenge of unknown transition dynamics compounds exponentially when multiple agents operate in the same environment without a centralized coordinator. In a Decentralized Partially Observable Markov Decision Process (Dec-POMDP), the next state depends on the joint action of all agents: $P(s'|s, a_1, a_2, \dots, a_n)$.
If the transition dynamics are unknown, and agents can only see a fraction of the world, the environment appears non-stationary and unpredictable to each individual. Traditional offline solvers dodge this by assuming a "god's eye view" of the entire transition matrix during training. To move beyond this limitation, Bikramjit Banerjee et al. in Sample Bounded Distributed Reinforcement Learning for Decentralized POMDPs demonstrated that distributed agents can learn optimal coordination policies purely from sampled, local experiences.
To make this decentralized learning sample-efficient, researchers have focused on bootstrapping and structural priors:
- Informed Initializations: Landon Kraemer et al. showed in Informed Initial Policies for Learning in Dec-POMDPs that agents can bypass the lack of a world model by first learning a simplified, observation-independent joint policy, giving alternating Q-learning a powerful head start.
- Dynamic Environments: In settings where the environment changes based on agent actions, Duc Thien Nguyen et al. developed distributed algorithms in Decentralized Multi-Agent Reinforcement Learning in Average-Reward Dynamic DCOPs to balance exploration and exploitation, allowing agents to map environmental changes on the fly.
- Scalable Controllers: To handle massive state spaces without explicit transition matrices, Christopher Amato et al. leveraged a Bayesian nonparametric approach in Stick-Breaking Policy Learning in Dec-POMDPs to automatically grow the complexity of an agent's finite-state controller based on experience.
Reconstructing Beliefs and Ensuring Stability
In partially observable systems, agents traditionally use a known transition and observation model to perform Bayesian updates and maintain a belief state (a probability distribution over the true state of the world). When these models are missing, agents must find alternative ways to track history and reach consensus.
One approach is to substitute explicit models with history tracking. Aditya Mahajan et al. proved in Reinforcement learning in decentralized stochastic control systems with partial history sharing that an Incrementally Expanding Representation (IER) can map shared histories to optimal actions without requiring an underlying system model. Alternatively, if agents can observe each other's actions, Rajesh K. Mishra et al. demonstrated in Decentralized Multi-agent Reinforcement Learning with Shared Actions that integrating Particle Filters into a common-agent framework allows agents to successfully estimate joint belief states in a model-free context.
Furthermore, communication can act as a substitute for a centralized model. Ali H. Sayed et al. proved in Policy Evaluation in Decentralized POMDPs with Belief Sharing that by diffusing local beliefs and value parameters across a network, decentralized agents can evaluate policies as accurately as a centralized system with perfect information. This localized coordination scales efficiently; Chongjie Zhang et al. showed in Coordinated Multi-Agent Reinforcement Learning in Networked Distributed POMDPs that combining model-free MARL with distributed constraint optimization yields highly efficient policies in dynamic networks.
Convergence and Risk in Competitive Environments
When transition dynamics are unknown, proving that an algorithm will converge to a stable strategy becomes significantly harder—particularly in competitive or risk-sensitive domains.
In zero-sum Markov games, model-free learning can suffer from high sample complexity. To address this, Ziyi Chen et al. designed the Stochastic Policy Extragradient (SPE) algorithm in Sample Efficient Stochastic Policy Extragradient Algorithm for Zero-Sum Markov Game, providing a decentralized, model-free approach that achieves state-of-the-art sample efficiency using a look-ahead stochastic update. For broader stochastic games, Lucas Baudin et al. proved in Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitions that agents can successfully find stable strategies using a decentralized, smooth fictitious play mechanism that operates entirely without transition or reward models.
Finally, exploring an unknown environment carries inherent dangers. Without a transition model to predict catastrophic outcomes, agents must learn to manage risk safely. Abdullah Al Maruf et al. tackled this in Risk-Aware Distributed Multi-Agent Reinforcement Learning by introducing a distributed QD-learning algorithm. By optimizing for the Conditional Value-at-Risk (CVaR) rather than average performance, their framework allows a network of agents to safely explore unknown dynamics and reach a consensus on risk-sensitive policies purely through local communication.
Key Foundational Work
Sequential Decision Problems and Neural Networks (1989) — contributed 1 concept elements to this direction.
Sequential Decision Probelms and Neural Networks (1989) — contributed 1 concept elements to this direction.
Integrated Modeling and Control Based on Reinforcement Learning and Dynamic Programming (1990) — contributed 1 concept elements to this direction.