Near-Optimal Sample Complexity for MDPs via Anchoring
Jongmin Lee, Mario Bravo, Roberto Cominetti · 2025
Read Near-Optimal Sample Complexity for MDPs via Anchoring by Jongmin Lee, Mario Bravo, Roberto Cominetti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-04477.txt.
Description
Jongmin Lee and two co-authors present a faster learning method for Markov decision processes, in a 2025 theory study. Such processes model choices where each act brings a reward and moves the world to a new state. The goal here is a near-best policy for long-run average reward. Their method blends repeated sampling with an anchored update rule named for Halpern. It needs no prior facts about the hidden bias values it works around.
The method finds a near-best policy with sample and time costs that match the best known lower bound, up to one factor. A built-in stopping rule ends the run in finite time with certainty. To the authors' knowledge, no other label-free method beats this cost. They also show how the same ideas adapt to the discounted reward case.
Catalog record
| CREATOR | Jongmin Lee, Mario Bravo, Roberto Cominetti |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-04477