R-max
Concrete Problems in AI Safety — inherited
A prior near-optimal RL exploration algorithm (Brafman & Tennenholtz 2003) that treats unexplored actions optimistically.
Optimism can be a strategy. R-max, an algorithm Brafman and Tennenholtz published in 2003, assumes every unexplored action might yield maximum reward, which provably drives an agent to try everything, dangerous corners included.
The page moves from the pre-existing algorithm and its near-optimality guarantee, through the mechanism of optimism in the face of uncertainty, to why that same mechanism is both the guarantee and the hazard.
A pre-existing near-optimal exploration algorithm
R-max predates Concrete Problems by well over a decade; it is a model-based reinforcement-learning algorithm introduced by Brafman and Tennenholtz (2003) with a formal near-optimality guarantee, and the paper cites it, alongside epsilon-greedy, as a standard exploration policy that "make[s] no attempt to avoid dangerous situations" (concrete-problems, §"6 Safe Exploration", p. 14).
The mechanism: optimism in the face of uncertainty
R-max works by optimism: every state-action pair the agent has not yet visited enough times is assigned the maximum possible reward $R_{\max}$ in its internal model, regardless of what reward it might actually yield. Formally, the agent maintains a count $n(s,a)$ for each pair and treats any pair with $n(s,a)$ below a threshold as transitioning deterministically to a fictitious maximally rewarding absorbing state; once enough visits accumulate, the true empirical transition and reward estimates replace the optimistic placeholder. Planning against this optimistic model, rather than the true one, guarantees that the agent either behaves near-optimally with respect to its current knowledge or is actively driven to explore whatever it does not yet know, since anything unexplored looks, by construction, like the best possible outcome. This is what gives R-max its headline result: with high probability, the algorithm achieves reward within $\epsilon$ of the optimal expected value on all but a number of timesteps that is polynomial in the size of the state and action spaces, $1/\epsilon$, $1/\delta$, and the mixing time or horizon of the MDP, a sample-complexity guarantee proved without any assumption of safety.
Why the same mechanism is both the guarantee and the hazard
The paper's own framing groups R-max with Epsilon-greedy exploration as equally blind to danger, but the two are blind for opposite reasons. Epsilon-greedy's hazard is incidental, it does not seek out unknown states, it simply fails to avoid them when chance selects one. R-max's hazard is structural: its optimism is precisely what actively steers the agent toward whatever is unexplored, including states that remain unexplored because they are catastrophic, and that same steering mechanism is what produces its efficiency proof. R-max's guarantee is also narrower than it may sound: it is a guarantee about expected total reward, the very objective risk-sensitive performance criteria was proposed to move away from, since near-optimal expected performance says nothing about the variance of outcomes along the way or the probability of a single rare catastrophic episode (concrete-problems, §"Risk-Sensitive Performance Criteria:", p. 14). R-max belongs to the theme Exploration policies and the objectives that make them safe or reckless as part of the baseline machinery the paper's safe-exploration proposals are measured against, an algorithm whose proof target the paper argues is, for safety purposes, the wrong target.