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

CREATORJongmin Lee, Mario Bravo, Roberto Cominetti
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-04477

Browse the full library · About the Tower of Babel