Minimax PAC Bounds for Learning in Exogenous Contextual MDPs

Corentin Pla; Hugo Richard; Marc Abeille; Vianney Perchet

stat.MLJun 23, 2026

Minimax PAC Bounds for Learning in Exogenous Contextual MDPs

Authors: Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet

Organizations: CREST, ENSAE · Criteo AI Lab · FairPlay Joint Team · Paris, France

Abstract

We study PAC learning in tabular discounted Markov decision processes with exogenous i.i.d. contexts, with discount factor $γ$ , finite state space $\mathcal X$ , action space $\mathcal A$ , and context space $\mathcal Z$ . At each time step, a context is drawn independently from an unknown distribution $μ$ and revealed before the agent acts. This context may affect both rewards and transitions, while remaining uncontrolled by the agent. Depending on the regime, the learner has access either to a sampling oracle for $μ$ , to a sampling oracle for the transition kernel conditioned on state-context-action tuples, or to both. Oracles can be accessed before and during policy execution. The sample complexity is measured by a couple $(n,m)$ , where $n$ is the number of calls to the sampling oracles before execution and $m$ is the number of calls to the sampling oracles during execution. When rewards and transitions are known and only the context distribution $μ$ is sampled, we give a variance-reduced algorithm that solves policy evaluation (PE), best-value estimation (BVE), and best-policy extraction (BPE) with $\left(\widetilde O\left(1/((1-γ)^3\varepsilon^2)\right), 0 \right)$ sample complexity. The rate is independent of $|\mathcal Z|$ and minimax optimal up to logarithmic factors. As a corollary, we also obtain tight rates in the case of one-step perfect look-ahead, improving upon the existing guarantees. In the fully unknown regime, where both $μ$ and P must be learned, we show that PE remains $|\mathcal Z|$ -free, with matching upper and lower bounds $\bigl(\widetilde O(|\mathcal X|/((1-γ)^3\varepsilon^2)),\, \widetilde O(1/((1-γ)^2\varepsilon^2))\bigr)$ .

Explore similar work

May 5, 2026cs.LG

Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes

We study the

(\varepsilon, δ)

-PAC policy identification problem in finite-horizon episodic Markov Decision Processes. Existing approaches provide finite-time guarantees for approximate settings (

\varepsilon>0

) but suffer from high computational cost, rendering them hard to implement, and also suffer from suboptimal dependence on

\log(1/δ)

. We propose a randomized and computationally efficient algorithm for best policy identification that combines posterior sampling with an online learning algorithm to guide exploration in the MDP. Our method achieves asymptotic optimality in sample complexity, also in terms of posterior contraction rate, and runs in

O(S^2AH)

per episode, matching standard model-based approaches. Unlike prior algorithms such as MOCA and PEDEL, our guarantees remain meaningful in the asymptotic regime and avoid sub-optimal polynomial dependence on

\log(1/δ)

. Our results provide both theoretical insights and practical tools for efficient policy identification in tabular MDPs.

Cyrille Kone, Kevin Jamieson

Finite-Horizon Episodic Markov Decision Processes Optimal Policies Markov Decision Processes Posterior Sampling

Ask PDF

May 15, 2026cs.LG

Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning

We study episodic reinforcement learning with fixed reward and transition functions, but with episode-dependent admissible action sets that are observed at the start of each episode. Performance is measured by cumulative regret against the episode-wise optimal value,

\sum_{k=1}^K [V^{*,M^k} - V^{π^k,M^k}]

, where

M^k

represents the action context in the

k

-th episode. We show that the MVP algorithm naturally extends to this framework and enjoys strong theoretical guarantees. In particular, we establish a minimax regret bound of

\widetilde{O}(\sqrt{SAH^3K\log L})

for adversarial contexts, where

L

denotes the number of possible contexts. This result implies a regret bound of

\widetilde{O}(\sqrt{SAH^3K})

for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of

\widetilde{O}(SAH^3/ε^2)

for a fixed context distribution. In addition, we derive a gap-dependent regret bound of

\widetilde O\left( \inf_{p\in [0,1)} \left( \frac{1}{Δ_{\min}^{p}} + pKΔ_{\min}^{p} \right)\log K \cdot \mathrm{poly}(S,A,H) \right),

where

Δ_{\min}^{p}

is the global

p

-trimmed positive-gap floor over suboptimal

(h,s,a)

triples. This bound can substantially improve upon the minimax rate when the relevant suboptimality gaps are large.

Zijun Chen, Zihan Zhang

Linear Regret Safe Reinforcement Learning Regret

Ask PDF

Jun 12, 2026cs.LG

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms

N

. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in

N

. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an

O(1/\sqrt{N})

optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution of our work is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.

Tianhao Wu, Matthew Zurek, Weina Wang +1

Markov Decision Processes Sample Complexity Lyapunov Function

Ask PDF