Minimax PAC Bounds for Learning in Exogenous Contextual MDPs

Corentin Pla Hugo Richard Marc Abeille Vianney Perchet CREST, ENSAE Criteo AI Lab FairPlay Joint Team Paris, France · 2026

Read Minimax PAC Bounds for Learning in Exogenous Contextual MDPs by Corentin Pla Hugo Richard Marc Abeille Vianney Perchet CREST, ENSAE Criteo AI Lab FairPlay Joint Team Paris, France (2026) 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-2606-25170.txt.

Introduction

Many decision problems mix a state the agent controls with a context it cannot, like the next piece falling in a Tetris style game. Corentin Pla, Hugo Richard, Marc Abeille, and Vianney Perchet analyse learning in such settings in 2026, asking how many samples provable learning truly needs. Contexts arrive independently from an unknown distribution and can shift both rewards and transitions. Sample use is counted separately before and during execution of the learned policy.

When only the context distribution is unknown, their variance reduced method works with a sample count that never grows with the number of contexts. They prove that rate is best possible up to small factors. Even with transitions also unknown, policy evaluation stays free of context count dependence. Matching lower bounds accompany the main algorithms.

Catalog record

CREATORCorentin Pla Hugo Richard Marc Abeille Vianney Perchet CREST, ENSAE Criteo AI Lab FairPlay Joint Team Paris, France
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE156 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.25170

Browse the full library · About the Tower of Babel