Research map / Bandits and online learning / RL theory and MDPs

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback

ICML 2025 · Bandits and online learning › RL theory and MDPs · approach: Regret bounds with function approximation

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first asymptotically nearly minimax-optimal regret bound, Õ(√(SAH³K)), for episodic tabular RL with trajectory feedback, via a tighter reward confidence region from linear-bandit techniques and a reference transition model for exploration.

Problem

Regret minimization in episodic tabular MDPs where the agent observes only the cumulative trajectory reward rather than per-step rewards; prior bounds for this setting scale suboptimally in S.

Approach

Builds a tighter trajectory-based confidence region for the reward by treating the problem as linear bandits over trajectory features, and uses a reference transition model with a Kiefer–Wolfowitz-style optimal design plus batched policy elimination to reach the Õ(√(SAH³K)) rate matching the standard RL lower bound.

Key results

• Achieves regret Õ(√(SAH³K)) with high probability for episodic MDPs with trajectory feedback (Theorem 5.6), matching the known Ω(√(SAH³K)) lower bound asymptotically in K.
• Improves on Efroni et al. (2021), whose bounds scale as Õ(√(S²A²H⁴K)), in dependence on S.
• Full regret bound includes lower-order terms: √(S³A²H³K)^(3/8) + √(S¹¹A³H¹⁹K)^(1/4) + √(S¹⁷A³H²⁷).

Measured effects reported in the paper

Surprising findings

• Trajectory feedback is statistically no harder than standard RL with per-step rewards in the asymptotic regime, since reward learning cost is dominated by transition learning.

Limitations

• The algorithm is computationally inefficient, requiring optimization over exponentially many deterministic policies.
• Result is asymptotic in K; lower-order terms are large and not minimized.
• Analysis restricted to tabular MDPs with known S, A, H.

Experimental setup

Metrics: regret upper bound (theoretical)

Baselines: Efroni et al. 2021 Cohen et al. 2021 Cassel et al. 2024

Builds on: Efroni et al. 2021 RL with trajectory feedback Zhang et al. 2022 policy elimination Azar et al. 2017 UCBVI Kiefer-Wolfowitz optimal design

Closest papers by meaning

• Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.90)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.90)
• Reinforcement Learning with Segment Feedback (ICML 2025 · similarity 0.90)
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.90)
• Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.89)
• Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds (ICLR 2025 · similarity 0.89)