# A View of the Certainty-Equivalence Method for PAC RL as an Application of the Trajectory Tree Method

arXiv: https://arxiv.org/abs/2501.02652 · HTML: https://mlsanity.com/paper/2501.02652/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 5 Jan 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 6 of 6)

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [PEGASUS: A Policy Search Method for Large MDPs and POMDPs](https://mlsanity.com/paper/1301.3878/) (2013)

## Built on by (most cited first, 2 of 2)

- [Using Common Random Numbers for Simulation-based Planning with Rollouts](https://mlsanity.com/paper/2605.04732/) (2026)
- [On-line Learning in Tree MDPs by Treating Policies as Bandit Arms](https://mlsanity.com/paper/2605.04979/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) enables an agent interacting with an unknown MDP M to optimise its behaviour by observing transitions sampled from M. A natural entity that emerges in the agent's reasoning is widehatM, the maximum likelihood estimate of M based on the observed transitions. The well-known textitcertainty-equivalence method (CEM) dictates that the agent update its behaviour to widehatπ, which is an optimal policy for widehatM. Not only is CEM intuitive, it has been shown to enjoy minimax-optimal sample complexity in some regions of the parameter space for PAC RL with a generative model~citepAgarwal2020GenModel. A seemingly unrelated algorithm is the ``trajectory tree method'' (TTM)~citepKearns+MN:1999, originally developed for efficient decision-time planning in large POMDPs. This paper presents a theoretical investigation that stems from the surprising finding that CEM may indeed be viewed as an application of TTM. The qualitative benefits of this view are (1) new and simple proofs of sample complexity upper bounds for CEM, in fact under a (2) weaker assumption on the rewards than is prevalent in the current literature. Our analysis applies to both non-stationary and stationary MDPs. Quantitatively, we obtain (3) improvements in the sample-complexity upper bounds for CEM both for non-stationary and stationary MDPs, in the regime that the ``mistake probability'' δ is small. Additionally, we show (4) a lower bound on the sample complexity for finite-horizon MDPs, which establishes the minimax-optimality of our upper bound for non-stationary MDPs in the small-δ regime.