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

R. BrafmanMoshe Tennenholtz

article2001JMLR1,391 citations

Introduces the R-MAX algorithm, providing a simple model-based approach that formally justifies optimism under uncertainty to achieve provably near-optimal reinforcement learning in polynomial time across Markov decision processes and zero-sum stochastic games.

Listen

Autonomous decision-making systems operating in competitive or uncertain settings must balance gathering new information (exploration) with maximizing performance using known facts (exploitation). Existing reinforcement learning methods often require an explicit choice between exploring and exploiting, a strategy that falters in adversarial environments where opponents can manipulate outcomes and prevent systematic learning. Moreover, widely used heuristics that initialize unknown states optimistically have historically lacked rigorous mathematical guarantees of efficiency and performance.

The article evaluates a model-based reinforcement learning algorithm, named R-max, designed to achieve provably near-optimal expected average reward within a bounded, polynomial number of steps. It formally demonstrates that an optimistic bias under uncertainty guarantees efficient learning and robust performance across standard decision processes, repeated games, and zero-sum stochastic games.

To establish these results, the authors construct a theoretical framework using two-player, fixed-sum stochastic games under an undiscounted average reward criterion. In the algorithm, the decision-making agent maintains an internal model that optimistically assumes all unknown state-action transitions yield the maximum possible reward. The agent computes and executes optimal policies against this optimistic model, recording observed transitions and rewards until a state has been sampled enough times to be marked known. Theoretical performance and sample complexity bounds are derived through probabilistic analyses and statistical concentration inequalities.

The findings establish that the algorithm satisfies an implicit explore-or-exploit property: at any phase, the agent either achieves near-optimal average return or visits an unknown state with high probability, regardless of the adversary's actions. With high probability (at least 1 minus a chosen failure tolerance), the agent reaches within twice the desired error bound of the optimal expected reward in polynomial time relative to the number of states, actions, accuracy requirements, and policy mixing time. Furthermore, the algorithm provides the first provably polynomial-time learning guarantee for repeated games and generalizes prior approaches without requiring an explicit exploration controller.

These results provide a solid theoretical justification for optimistic initialization, moving it from an ad-hoc heuristic to a mathematically sound design principle. For organizational and technical leaders, this means autonomous algorithms can guarantee baseline safety levels and bounded convergence times even in adversarial or non-deterministic environments. The approach avoids costly manual tuning of separate exploration policies and mitigates performance risks in competitive multi-agent systems.

Moving forward, practitioners should explore integrating optimistic model-based methods into environments where worst-case performance guarantees and robust safety baselines are paramount. However, researchers must conduct additional work to scale the algorithm for complex real-world settings. While polynomial in explicit state-space size, the approach faces computational bottlenecks in very large domains where state spaces grow exponentially and mixing times are long. Future work should focus on developing structured or factored state representations and exploring polynomial-time algorithms that achieve full adaptation to sub-optimal adversaries.

Ben-Gurion University of the Negev Stanford University Technion – Israel Institute of Technology agent systems average reward deterministic R-MAX algorithm near-optimal reinforcement learning multi-agent reinforcement learning

Brafman et al (2001).pdf

Paper: Markov Games as a Framework for Multi-Agent Reinforcement Learning, Michael L. Littman (1994). Littman introduces the framework of zero-sum Markov games and value iteration for multi-agent settings that R-MAX builds upon and generalizes to polynomial-time sample complexity.
Paper: Reinforcement Learning: A Survey, Leslie Pack Kaelbling et al. (1996). This seminal survey reviews foundational concepts in Markov decision processes, model-based exploration-exploitation dilemmas, and optimistic heuristics that R-MAX formalizes.
Paper: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund et al. (1997). Freund and Schapire establish fundamental regret-minimization techniques and concentration bounds in online learning that inform the theoretical analysis in R-MAX.
Paper: Learning to Predict by the Methods of Temporal Differences, Richard S. Sutton (1988). Sutton establishes the fundamental principles of temporal-difference learning and value estimation across multistep Markov processes.

Paper: Near-optimal Regret Bounds for Reinforcement Learning, Thomas Jaksch et al. (2008). Jaksch, Ortner, and Auer develop UCRL2, advancing the principle of optimism in the face of uncertainty established by R-MAX by providing near-optimal regret bounds characterized by environment diameter.
Paper: Finite-time Analysis of the Multiarmed Bandit Problem, Peter Auer et al. (2002). Auer, Cesa-Bianchi, and Fischer provide finite-time logarithmic regret bounds using Upper Confidence Bounds (UCB), formalizing the optimism-under-uncertainty principle for bandit settings.
Paper: Using Confidence Bounds for Exploitation-Exploration Trade-offs, Peter Auer (2003). Auer extends confidence-bound-driven exploration to non-stationary and associative environments with linear function approximation.
Paper: Improved Algorithms for Linear Stochastic Bandits, Yasin Abbasi-Yadkori et al. (2011). Abbasi-Yadkori, Pál, and Szepesvári refine optimism in the face of uncertainty using self-normalized martingale inequalities to achieve tighter bounds for linear stochastic bandits.
Paper: Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Sébastien Bubeck et al. (2012). Bubeck and Cesa-Bianchi provide an extensive survey and unified regret analysis of optimistic exploration methods across stochastic and adversarial bandit settings.
Paper: Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms, Kaiqing Zhang et al. (2019). Zhang, Yang, and Başar provide a modern theoretical overview of multi-agent reinforcement learning in Markov and stochastic games, surveying sample efficiency and convergence guarantees that followed R-MAX.
Paper: Deep Exploration via Bootstrapped DQN, Ian Osband et al. (2016). Osband et al. scale the concept of directed, temporally extended exploration to deep reinforcement learning architectures using bootstrapped ensembles.

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

Abstract

R-MAX is a very 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, it 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 zero-sum 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 simpler, more general, and more efficient than Brafman and Tennenholtz’s LSG algorithm for 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 learning in repeated games, to date, which is provably efficient, considerably improving and simplifying previous algorithms by Banos and by Megiddo.

Topics

agent systems average reward deterministic multi-agent optimal policies performance guarantees polynomial-time algorithms reinforcement learning method repeated games robust performance

Keywords

R-MAX algorithm near-optimal reinforcement learning multi-agent reinforcement learning Markov decision processes stochastic games probabilistic maximin fictitious stage-game exploration policy

1. Introduction
2. Preliminaries
2.1 Stochastic Games
2.2 Assumptions, Complexity and Optimality
3. The R-max Algorithm
4. Optimality and Convergence
4.1 Repeated Games
5. Conclusion
Acknowledgments
References

Knowls

Knowl 1 — Polynomial-Time Near-Optimal Convergence of R-MAX in Stochastic Games
theoretical result
Let $M$ be a two-player, fixed-sum stochastic game with $N$ states (stage games), $k$ actions available to each player, and stage-game rewards bounded in $[0, R_{\max}]$ . Let $0 < \delta < 1$ be the failure probability bound and $\epsilon > 0$ be the error bound. Let $\Pi_M(\epsilon, T)$ denote the set of agent policies whose $\epsilon$ -return mixing time is at most $T$ , and let $\text{Opt}_M(\Pi(\epsilon, T))$ denote the optimal expected $T$ -step undiscounted average return achievable by policies in $\Pi_M(\epsilon, T)$ .

With probability at least $1 - \delta$ , the R-MAX algorithm achieves an expected average return of at least: $\text{Opt}_M(\Pi(\epsilon, T)) - 2\epsilon$ within a total number of game steps that is polynomial in $N$ , $k$ , $T$ , $\frac{1}{\epsilon}$ , $\ln\left(\frac{1}{\delta}\right)$ , and $R_{\max}$ .
Knowl 2 — The R-MAX Reinforcement Learning Algorithm for Stochastic Games
algorithm
The R-MAX algorithm learns near-optimal policies in two-player fixed-sum stochastic games (and Markov Decision Processes as a single-player special case) by maintaining an optimistic model where unvisited or insufficiently visited state-action pairs yield maximal possible reward $R_{\max}$ and transition deterministically to an absorbing fictitious state $G_0$ . An optimal $T$ -step policy is computed with respect to this model and executed, updating empirical transition frequencies and rewards until all relevant entries are marked as known.
Input: Number of stage games $N$ , action count $k$ , accuracy $\epsilon > 0$ , failure probability $\delta \in (0, 1)$ , reward bound $R_{\max}$ , mixing time $T$ .
Initialize:
    Construct model $M'$ with $N+1$ stage games $\{G_0, G_1, \dots, G_N\}$ and $k$ actions $\{a_1, \dots, a_k\}$ .
    For each $i \in \{0, \dots, N\}$ and each joint action $(a, a')$ :
        Set model reward $R^i(a, a') = (R_{\max}, 0)$ .
        Set transition probability $P_{M'}(G_i, G_0, a, a') = 1.0$ .
    For each entry $(G_i, a, a')$ with $i \in \{1, \dots, N\}$ :
        Set status $(G_i, a, a') = \text{unknown}$ .
        Set visit_count $(G_i, a, a') = 0$ .
        Set dest_count $(G_i, a, a', G_j) = 0$ for all $j \in \{1, \dots, N\}$ .
    Compute sample threshold $K_1 = \max\left( \left\lceil \left( \frac{4 N T R_{\max}}{\epsilon} \right)^3 \right\rceil, \left\lceil -6 \ln^3\left( \frac{\delta}{6 N k^2} \right) \right\rceil \right) + 1$ .
Repeat indefinitely:
    Compute an optimal $T$ -step policy $\pi$ for current state $G_s$ on model $M'$ .
    Execute $\pi$ for at most $T$ steps or until an unknown entry becomes known:
        In current state $G_i$ , agent plays action $a$ , adversary plays action $a'$ .
        Observe adversary action $a'$ , immediate reward $r$ , and next state $G_j$ .
        If $(a, a')$ is played in $G_i$ for the first time:
            Update reward $R^i(a, a')$ to $(r, r_{\text{adv}})$ .
        Increment visit_count $(G_i, a, a')$ .
        Increment dest_count $(G_i, a, a', G_j)$ .
        If status $(G_i, a, a') == \text{unknown}$ and visit_count $(G_i, a, a') \ge K_1$ :
            Set status $(G_i, a, a') = \text{known}$ .
            For each $t \in \{1, \dots, N\}$ :
                Set $P_{M'}(G_i, G_t, a, a') = \text{dest_count}(G_i, a, a', G_t) / K_1$ .
            Set $P_{M'}(G_i, G_0, a, a') = 0.0$ .
            Break inner execution loop to recompute optimal policy $\pi$ .
Knowl 3 — Implicit Explore or Exploit Lemma
theoretical result
Let $M$ be a two-player fixed-sum stochastic game with payoffs bounded in $[0, R_{\max}]$ , let $L$ be the set of joint action entries $(G_i, a, a')$ currently marked unknown, and let $M_L$ be the induced stochastic game where entries in $L$ transition deterministically to a fictitious state $G_0$ yielding reward $R_{\max}$ . Let $R^{M_L}\text{-}\max$ denote the optimal policy with respect to $M_L$ .

For any adversary policy $\rho$ , any starting state $s$ , and any $0 < \alpha < 1$ , when executing $R^{M_L}\text{-}\max$ for $T$ steps on the true game $M$ , at least one of the following two conditions holds:
1. The expected $T$ -step average reward $V_{R\text{-}\max} = U_M(s, R^{M_L}\text{-}\max, \rho, T)$ satisfies: $V_{R\text{-}\max} > \text{Opt}(\Pi_M(\epsilon, T)) - \alpha$
2. An unknown entry in $L$ is visited during the $T$ steps on $M$ with probability at least: $\frac{\alpha}{R_{\max}}$
Knowl 4 — Simulation Lemma for Stochastic Games
theoretical result
Let $M$ and $\bar{M}$ be two stochastic games over the same $N$ states and same action spaces, where all stage-game reward matrices $R^i$ are identical and bounded in $[0, R_{\max}]$ . If $\bar{M}$ is an $\alpha$ -approximation of $M$ with: $\alpha = \frac{\epsilon}{N T R_{\max}}$ such that for all states $s, t$ and all joint actions $(a, a')$ : $|P_M(s, t, a, a') - P_{\bar{M}}(s, t, a, a')| \le \alpha$ then for every state $s$ , every agent policy $\pi$ , and every adversary policy $\rho$ , the expected $T$ -step undiscounted average rewards satisfy: $|U_{\bar{M}}(s, \pi, \rho, T) - U_M(s, \pi, \rho, T)| \le \epsilon$
Knowl 5 — Induced Stochastic Game Model Construction
model/method
Let $M$ be a two-player fixed-sum stochastic game on states $S = \{G_1, \dots, G_N\}$ and actions $A = \{a_1, \dots, a_k\}$ . Let $L \subseteq S \times A \times A$ denote the subset of state-joint-action tuples $(G_i, a, a')$ designated as unknown.

The induced stochastic game $M_L$ is defined on state space $S \cup \{G_0\}$ as follows:
1. For every entry $(G_i, a, a') \notin L$ , transition probabilities $P_{M_L}(G_i, \cdot, a, a')$ and reward pairs $R^i(a, a')$ are identical to their values in $M$ .
2. For every unknown entry $(G_i, a, a') \in L$ and for all actions $(a, a')$ in state $G_0$ , the transition is deterministic to $G_0$ : $P_{M_L}(G_i, G_0, a, a') = 1.0$ and the reward is set to $R_{\max}$ for the agent and $0$ for the adversary.
Knowl 6 — Sample Complexity Threshold for Known State-Action Transitions
equation
In the R-MAX algorithm, the minimum number of observations $K_1$ required to mark an unknown entry $(G_i, a, a')$ as known and estimate its transition probabilities is: $K_1 = \max\left( \left\lceil \left( \frac{4 N T R_{\max}}{\epsilon} \right)^3 \right\rceil, \left\lceil -6 \ln^3\left( \frac{\delta}{6 N k^2} \right) \right\rceil \right) + 1$ where $N$ is the number of stage games, $k$ is the number of actions per player, $T$ is the $\epsilon$ -return mixing time, $R_{\max}$ is the maximum possible reward, $\epsilon > 0$ is the target error, and $\delta \in (0, 1)$ is the failure probability.

Sampling each joint action entry $K_1$ times guarantees via the Chernoff bound that the empirical transition probability to any state $t$ deviates from the true transition probability by at most $\frac{\epsilon}{2 N T R_{\max}}$ with failure probability at most $\frac{\delta}{3 N k^2}$ , bounding the union bound error across all $N k^2$ entries by $\frac{\delta}{3}$ .
Knowl 7 — Extension of R-MAX to Unknown Mixing Times
algorithm
When the true $\epsilon$ -return mixing time $T_0$ of an optimal policy is not known in advance, R-MAX is run iteratively with increasing candidate mixing times $T = 1, 2, 3, \dots$ , executing candidate horizon $T$ for $P(T)$ steps, where $P(T)$ is the polynomial bound on steps needed to guarantee near-optimality for mixing time $T$ .
Input: Number of stage games $N$ , action count $k$ , accuracy $\epsilon > 0$ , failure probability $\delta \in (0, 1)$ , reward bound $R_{\max}$ , target error $\gamma > 0$ .
Initialize:
    Initialize persistent empirical model $M'$ with optimistic priors.
    Candidate mixing time $T = 1$ .
Repeat indefinitely:
    Compute step count $P(T)$ polynomial in $(N, k, T, 1/\epsilon, 1/\delta, R_{\max})$ .
    Run R-MAX with mixing time parameter $T$ for $P(T)$ steps, preserving all observed counts and known states in $M'$ .
    Increment candidate mixing time: $T \leftarrow T + 1$ .
Once $T \ge T_0$ , all subsequent phases yield near-optimal expected reward. After $D' = \lceil T_0 R_{\max} / \gamma \rceil$ additional phases with $T > T_0$ , the cumulative average reward of the agent across all phases is guaranteed to be within $\gamma$ of optimal.
Knowl 8 — R-MAX for Repeated Games with Incomplete Information
algorithm
In a repeated two-player fixed-sum game with incomplete information (an Adaptive Competitive Decision Process), there are no state transitions ( $N=1, T=1$ ). R-MAX simplifies to maintaining an optimistic payoff matrix where unexplored joint actions yield $R_{\max}$ .
Input: Number of actions $k$ , reward upper bound $R_{\max}$ .
Initialize:
    Initialize payoff matrix $R \in \mathbb{R}^{k \times k}$ with entries $(R_{\max}, 0)$ .
    Set status $(a, a') = \text{unknown}$ for all action pairs $(a, a') \in \{a_1, \dots, a_k\}^2$ .
Repeat:
    Compute optimal probabilistic (maximin) strategy $\pi \in \Delta(\{a_1, \dots, a_k\})$ for matrix game $R$ .
    Sample action $a \sim \pi$ and execute action $a$ .
    Observe adversary action $a'$ and agent reward $r$ .
    If status $(a, a') == \text{unknown}$ :
        Set $R(a, a') = (r, r_{\text{adv}})$ .
        Set status $(a, a') = \text{known}$ .
Knowl 9 — Two-Player Fixed-Sum Stochastic Games and Value Formulation
definition
A two-player fixed-sum stochastic game $M$ is defined by a state set $S = \{G_1, \dots, G_N\}$ , an action set $A = \{a_1, \dots, a_k\}$ shared by both players, a set of stage-game reward matrices $\{R^i\}_{i=1}^N$ with entries $R^i(a, a') \in [0, R_{\max}]$ , and a transition probability function $P_M(G_i, G_j, a, a')$ specifying the probability of transitioning from state $G_i$ to $G_j$ under joint action $(a, a')$ .

For an agent policy $\pi$ and adversary policy $\rho$ started in state $s \in S$ , the expected $T$ -step undiscounted average reward is denoted $U_M(s, \pi, \rho, T)$ . The guaranteed value of policy $\pi$ is: $U_M(s, \pi, T) = \min_{\rho} U_M(s, \pi, \rho, T)$ $U_M(s, \pi) = \liminf_{T \to \infty} U_M(s, \pi, T)$ $U_M(\pi) = \min_{s \in S} U_M(s, \pi)$

The $\epsilon$ -return mixing time of policy $\pi$ is the smallest integer $T$ such that for every initial state $s$ , every adversary policy $\rho$ , and all $t \ge T$ : $U_M(s, \pi, \rho, t) > U_M(\pi) - \epsilon$ $\Pi_M(\epsilon, T)$ denotes the set of policies with $\epsilon$ -return mixing time at most $T$ , and $\text{Opt}_M(\Pi(\epsilon, T)) = \max_{\pi \in \Pi_M(\epsilon, T)} U_M(\pi)$ .
Knowl 10 — Scalability and Halting Limitations of R-MAX
limitation
R-MAX exhibits two main practical limitations:
1. State-space and mixing time scaling: The sample and computational complexity bounds depend polynomially on the explicit state space size $N$ and the policy mixing time $T$ . In factored or continuous state spaces, $N$ grows exponentially with the number of state variables, making tabular R-MAX computationally intractable without structural approximations.
2. Absence of halting with unknown mixing time: When the mixing time $T$ is unknown and updated via iterative candidate increases $T = 1, 2, 3, \dots$ , the algorithm does not terminate. Computing the optimal $T$ -step policy at each model update eventually requires exponential computation per decision step once candidate $T$ becomes exponentially larger than the true mixing time $T_0$ .

Coverage note — Omitted historical and background comparisons to earlier heuristics (such as Dyna exploration bonuses, prioritized sweeping, and interval exploration) as well as the step-by-step Chernoff derivations of intermediate bounds.

References

1.R. Aumann and M. Maschler. Repeated Games with Incomplete Information. MIT Press, 1995.
2.A. Banos. On pseudo games. The Annals of Mathematical Statistics, 39:1932–1945, 1968.
3.R. Brafman and M. Tennenholtz. A near-optimal polynomial time algorithm for learning in certain classes of stochastic games. Artificial Intelligence, 121(1–2):31–47, 2000.
4.D. Fudenberg and D.K. Levine. Self-confirming equilibrium. Econometrica, 61(3):523–545, 1993.
5.S. Hart and A. Mas-Colell. A reinforcement procedure leading to correlated equilibrium. Technical report, Center for Rationality – Hebrew University of Jerusalem, 2000.
6.A.J. Hoffman and R.M. Karp. On Nonterminating Stochastic Games. Management Science, 12(5):359–370, 1966.
7.J. Hu and M.P. Wellman. Multi-agent reinforcement learning: Theoretical framework and an algorithms. In Proc. 15th International Conference on Machine Learning, 1998.
8.L. P. Kaelbling. Learning in Embedded Systems. The MIT Press, 1993.
9.L. P. Kaelbling, M. L. Littman, and A. W. Moore. Reinforcement learning: A survey. Journal of AI Research, 4:237–285, 1996.
10.M. Kearns and D. Koller. Efficient reinforcement learning in factored mdps. In Proc. 16th International Joint Conference on Artificial Intelligence (IJCAI), pages 740–747, 1999.
11.M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. In Int. Conf. on Machine Learning, 1998.
12.M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proc. 11th Intl. Conf. on Machine Learning, pages 157–163, 1994.
13.M. L. Littman and Csaba Szepesv´ari. A generalized reinforcement-learning model: Convergence and apllications. In Proc. 13th Intl. Conf. on Machine Learning, pages 310–318, 1996.
14.N. Megiddo. On repeated games with incomplete information played by non-bayesian players. International Journal of Game Theory, 9:157–167, 1980.
15.D. Monderer and M. Tennenholtz. Dynamic Non-Bayesian Decision-Making. J. of AI Research, 7:231–248, 1997.
16.A. W. Moore and C. G. Atkenson. Prioratized sweeping: Reinforcement learning with less data and less real time. Machine Learning, 13, 1993.
17.J. H. Schmidhuber. Curious model-building control systems. In Proc. Intl. Joint Conf. on Neural Networks, pages 1458–1463, 1991.
18.R. S. Sutton. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In Proc. of the 7th Intl. Conf. on Machine Learning. Morgan Kaufmann, 1990.
19.R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
20.P. Tadepalli and D. Ok. Model-based average reward reinforcement learning. Artificial Intelligence, 100:177–224, 1998.

Citation

MLA

Brafman, R. I., and M. Tennenholtz. “R-MAX: A General Polynomial Time Algorithm for Near-optimal Reinforcement Learning”. International Joint Conference on Artificial Intelligence, 2001, pp. 953–58, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4042.

APA

Brafman, R. I., & Tennenholtz, M. (2001). R-MAX: a general polynomial time algorithm for near-optimal reinforcement learning. International Joint Conference on Artificial Intelligence, 953–958. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4042

Chicago

Brafman, R. I., and M. Tennenholtz. 2001. “R-MAX: A General Polynomial Time Algorithm for Near-optimal Reinforcement Learning”. International Joint Conference on Artificial Intelligence, 953–58. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4042.

Harvard

Brafman, R.I. and Tennenholtz, M. (2001) “R-MAX: a general polynomial time algorithm for near-optimal reinforcement learning”, International Joint Conference on Artificial Intelligence, pp. 953–958. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4042.

Vancouver

1. Brafman RI, Tennenholtz M (2001) R-MAX: a general polynomial time algorithm for near-optimal reinforcement learning. International Joint Conference on Artificial Intelligence 953–958

BibTeX

@article{brafman2001max,
  title = {R-MAX: a general polynomial time algorithm for near-optimal reinforcement learning},
  author = {Brafman, Ronen I. and Tennenholtz, Moshe},
  year = {2001},
  journal = {International Joint Conference on Artificial Intelligence},
  pages = {953-958},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4042}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Polynomial-Time Near-Optimal Convergence of R-MAX in Stochastic Games

Knowl 2 — The R-MAX Reinforcement Learning Algorithm for Stochastic Games

Knowl 3 — Implicit Explore or Exploit Lemma

Knowl 4 — Simulation Lemma for Stochastic Games

Knowl 5 — Induced Stochastic Game Model Construction

Knowl 6 — Sample Complexity Threshold for Known State-Action Transitions

Knowl 7 — Extension of R-MAX to Unknown Mixing Times

Knowl 8 — R-MAX for Repeated Games with Incomplete Information

Knowl 9 — Two-Player Fixed-Sum Stochastic Games and Value Formulation

Knowl 10 — Scalability and Halting Limitations of R-MAX

References

Citation

BibTeX

Access the Paper