R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning

Ronen I. Brafman, Moshe Tennenholtz

TL;DR

This paper introduces R-MAX, a novel reinforcement learning algorithm that efficiently learns near-optimal strategies in complex, multi-agent "stochastic games." Unlike previous methods, R-MAX implicitly balances exploration and exploitation by maintaining an "optimistic" model of the environment, leading to provably efficient learning and a simpler, more general approach.

What Problem Does This Paper Address?

Reinforcement learning (RL) aims to train agents to make optimal decisions in an environment through trial and error. While significant progress has been made, a key challenge lies in learning effectively in environments with multiple interacting agents, especially when those interactions are uncertain or adversarial. This is particularly true in "stochastic games," which are more general than standard Markov Decision Processes (MDPs) because they involve at least two players whose actions influence both the next state and the rewards received.

Previous algorithms like Kearns and Singh's E³ algorithm offered provably efficient learning for MDPs but struggled to generalize to the more complex, adversarial nature of stochastic games. The difficulty arises because in a game, an agent cannot fully control the environment's transitions or the other players' actions. A direct extension of E³ to games would require an explicit, and often difficult, choice between exploring new possibilities and exploiting known good strategies. This paper tackles the problem of developing a reinforcement learning algorithm that can efficiently learn near-optimal strategies in these challenging multi-agent settings, specifically zero-sum stochastic games, without requiring explicit exploration-exploitation decisions.

Methods

The core innovation of R-MAX is its "optimism under uncertainty" approach, embodied in a simple, model-based algorithm. Here's how it works:

  • Optimistic Initialization: R-MAX starts with a model of the environment that is deliberately overly optimistic. It assumes that any unknown action in any state will yield the maximum possible reward (hence the name R-MAX). This initial bias encourages exploration.
  • Implicit Exploration/Exploitation: Instead of explicitly deciding to explore or exploit, R-MAX's optimistic model naturally drives this behavior. When the agent encounters a situation it's unfamiliar with, the high assumed reward incentivizes it to try actions that might lead to new information. As it gathers more data, its model becomes more accurate, and its behavior shifts towards exploitation.
  • Model Updating: The agent continuously updates its model based on observed rewards and state transitions. When enough data is collected for a particular state-action pair, that part of the model is marked as "known."
  • Polynomial Time Convergence: The algorithm is designed to guarantee that it will learn a near-optimal policy within a polynomial number of steps, relative to the size of the state space, the number of actions, and other relevant parameters.

R-MAX is presented as a generalization of previous work, simplifying and extending algorithms for MDPs, single-controller stochastic games, and repeated games.

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees for a general class of stochastic games rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • "Optimism Under Uncertainty" as a Formal Principle: The paper provides a theoretical justification for the "optimism under uncertainty" heuristic, which has been used in various RL algorithms but lacked formal backing. R-MAX demonstrates how this bias can be leveraged for provably efficient learning.
  • Implicit Exploration-Exploitation: The most significant insight is the development of an algorithm where the exploration-exploitation dilemma is resolved implicitly through the agent's optimistic model. This simplifies the learning process and makes it more robust in adversarial settings.
  • Generality and Simplicity: R-MAX is shown to be a more general framework that unifies and improves upon existing algorithms for MDPs, repeated games, and various types of stochastic games. Its conceptual simplicity makes it easier to understand and implement.
  • Safety Level Guarantee: For zero-sum stochastic games, R-MAX guarantees the "safety level" (probabilistic maximin value), meaning it ensures a minimum expected reward against any adversary.

Key Results

The paper proves that R-MAX algorithm achieves near-optimal average reward in polynomial time. Specifically, Theorem 2 states that with high probability, R-MAX will attain an expected return within $\epsilon$ of the optimal, where $\epsilon$ is a small error bound, in a number of steps polynomial in the state space size ($N$), number of actions ($k$), the e-return mixing time ($T$), and $1/\delta$ (where $\delta$ is the failure probability). The algorithm is also shown to be more efficient and general than prior algorithms for learning in stochastic games and repeated games.

Limitations and Future Work

  • Known Rmax: The current formulation assumes that the maximum possible reward ($R_{max}$) is known beforehand. The authors suggest this assumption could be removed by dynamically updating an estimate of $R_{max}$.
  • Mixing Time as Input: The initial description of the algorithm requires the e-return mixing time ($T$) as an input. The paper outlines a method to remove this dependency by repeatedly running the algorithm with increasing estimates of $T$, though this can lead to exponential time complexity in the worst case for policy computation.
  • Practical Performance: The authors acknowledge that while polynomial time convergence is theoretically guaranteed, practical environments often have exponentially many states and large mixing times, making these guarantees less directly applicable. They suggest that future work should focus on algorithms that exploit the structure of the state space.
  • Open Problem: The paper poses an open problem: whether a polynomial-time Hannan-consistent near-optimal algorithm exists for repeated games and stochastic games.

Summary updated

Abstract

R-MAX is a simple model-based reinforcement learning algorithm which can attain near-optimal average reward in polynomial time. In R-MAX, the agent always maintains a complete, but possibly inaccurate model of its environment and acts based on the optimal policy derived from this model. The model is initialized in an optimistic fashion: all actions in all states return the maximal possible reward (hence the name). During execution, the model is updated based on the agent's observations. R-MAX improves upon several previous algorithms: (1) It is simpler and more general than Kearns and Singh's E3 algorithm, covering zerosum stochastic games. (2) It has a built-in mechanism for resolving the exploration vs. exploitation dilemma. (3) It formally justifies the "optimism under uncertainty" bias used in many RL algorithms. (4) It is much simpler and more general than Brafman and Tennenholtz's LSG algorithmfor learning in single controller stochastic games. (5) It generalizes the algorithm by Monderer and Tennenholtz for learning in repeated games. (6) It is the only algorithm for near-optimal learning in repeated games known to be polynomial, providing a much simpler and more efficient alternative to previous algorithms by Banos and by Megiddo.
BibTeX
@article{brafman2002r,
  author = {Ronen I. Brafman and Moshe Tennenholtz},
  title = {{R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning}},
  journal = {J. Mach. Learn. Res.},
  year = {2002},
  url = {https://openreview.net/forum?id=uarG9m376K},
}
Figure