Data- and Variance-dependent Regret Bounds for Online Tabular MDPs

AI summary

Overview

• Research area: Reinforcement learning theory, specifically online learning in finite-horizon episodic tabular Markov decision processes (MDPs); best-of-both-worlds algorithms and data-dependent regret analysis.
• Technical level: Advanced. The paper is dense with regret bounds, occupancy measures, OFTRL machinery, and complexity measures; it presumes familiarity with online learning and MDP regret analysis.
• Scope (one sentence): The paper designs single algorithms that simultaneously achieve first-order, second-order, and path-length regret in the adversarial regime and variance-aware gap-independent or gap-dependent regret in the stochastic regime (with adversarial corruption), for episodic tabular MDPs with known transitions, and proves matching lower bounds.

What This Paper Is About

Existing best-of-both-worlds algorithms for tabular MDPs only offer first-order data-dependent guarantees in the adversarial regime, and the variance-aware guarantees for the stochastic regime are usually achieved by separate, dedicated algorithms. The authors ask whether a single algorithm can adapt to richer data-dependent structure (second-order and path-length complexity) in the adversarial regime while also achieving variance-dependent bounds in the stochastic regime. They study the known-transition setting to isolate the difficulty of loss estimation under bandit feedback, where errors at a state-action pair propagate through MDP dynamics.

Key Contributions

1. New complexity measures. The paper introduces a second-order quantity Q_∞ ∈ [0, HT/4] that tracks how much losses fluctuate around a baseline, a path-length (total variation) measure V_1 ∈ [0, SA(T-1)] that tracks how losses change over time, and two variance measures for the stochastic regime: the occupancy-weighted variance 𝕍 ∈ [0, H/4] and the conditional occupancy-weighted variance 𝕍^c(s) ∈ [0, H/4]. It argues 𝕍 and 𝕍^c are H²-sharper analogues of the known maximum total variance and maximum conditional total variance measures, because the second term in Var★(s,a) is unnecessary with known transitions.

2. Global-optimization algorithms with refined adaptivity. Built on optimistic follow-the-regularized-leader (OFTRL) over the set of occupancy measures Ω(P) with a log-barrier regularizer and adaptive learning rates (Algorithm 1), the methods achieve first-order, second-order, and path-length regret in the adversarial regime, and variance-aware gap-independent and gap-dependent bounds in the stochastic regime.

3. Policy-optimization algorithms with the same adaptivity up to an H factor. Based on OFTRL over action distributions (Algorithm 2), they exploit a new, more optimistic Q-function estimator than the one used in the existing best-of-both-worlds policy optimization of Dann et al. (2023b).

4. Lower bounds. The paper proves data-dependent regret lower bounds Ω(√(SA L^★)), Ω(√(SA Q_∞)), Ω(√(H V_1)), and a variance-dependent lower bound Ω(√(SA 𝕍 T)), implying the global-optimization upper bounds are nearly optimal in terms of L^★, Q_∞, and V_1.

Main Findings

• Adversarial regret (global optimization, Theorem 4.1, with the gradient-descent predictor in Equation 5): Reg_T ≲ √(SA log(T) min{L^★, HT − L^★, Q_∞, V_1}) + HSA log T. The paper states this is the first second-order and path-length bound for online episodic tabular MDPs, and that it recovers the worst-case Õ(√(HSAT)) dependence of Zimin and Neu (2013).

• Stochastic regret (global optimization, Theorem 4.1): Under the stochastic regime with adversarial corruption, the same algorithm simultaneously ensures Reg_T ≲ √(SA log(T)(𝕍 T + C)) + HSA log T, and Reg_T ≲ U + √(U C) + HSA log T, where U = Σ_s Σ_{a ≠ π⋆(s)} H² log(T)/Δ(s,a). The gap-dependent bound improves over Jin et al. (2021) by avoiding their additional dependence on 1/min_{s,a} Δ(s,a).

• Second variant of global optimization (Theorem 4.2, empirical-mean predictor in Equation 6): Reg_T ≲ √(SA log(T) min{L^★, HT − L^★, Q_∞}) + HSA log(T); under stochastic corruption it gives √(SA log(T)(𝕍 T + C)) + HSA log(T) and a gap-dependent bound U_Var + √(U_Var C) + √(HS²A²C) log(T) + H^{1/2}S^{3/2}A^{3/2} log^{3/2}(T), where U_Var = Σ_s Σ_{a ≠ π⋆(s)} H 𝕍^c(s) log(T)/Δ(s,a).

• Policy optimization (Theorems 5.2 and 5.3): The adversarial bound becomes Õ(√(H²SA min{L^★, HT − L^★, Q_∞, V_1})) (Theorem 5.2) or Õ(√(H²SA min{L^★, HT − L^★, Q_∞})) (Theorem 5.3), and the stochastic-corruption bound is min{√(H²SA(𝕍 T + C)), U + √(U C)} for Theorem 5.2 and min{√(H²SA(𝕍 T + C)), U_Var + √(U_Var C)} for Theorem 5.3. The paper describes this as the same data- and variance-dependent adaptivity up to a factor of the horizon H.

• Variance-aware gap-dependent bound: In both global and policy optimization, a polylog(T) gap-dependent bound is achievable in the stochastic regime, but whether a path-length bound or a variance-aware gap-dependent bound is attained depends on how the loss prediction in OFTRL is chosen.

• Lower bounds (Section 6, Table 3): Ω(√(SA L^★)), Ω(√(SA Q_∞)), Ω(√(H V_1)) for adversarial instances, and Ω(√(SA 𝕍 T)). Together with the minimax lower bound Ω(√(HSAT)) of Zimin and Neu (2013), these show the global-optimization upper bounds are nearly optimal in L^★, Q_∞, and V_1, and also optimal for the variance-aware gap-independent bound.

• A sharper variance measure: The authors state 𝕍^c is H²-sharper than measures built on Var★(s,a) because it uses conditional occupancy measures q^π(s',a' | s,a) and conditions only on the trajectory after visiting (s,a), rather than aggregating over the whole trajectory.

Methodology in Plain English

The paper studies a learner that plays T episodes in a layered tabular MDP with known transition kernel P, where at each episode it picks a policy, follows the induced trajectory, and observes losses only along that trajectory. The learner's goal is to minimize regret against the best fixed policy in hindsight (Equation 2).

Both algorithm families use optimistic follow-the-regularized-leader (OFTRL): at each round, the algorithm chooses a distribution that minimizes a linear loss on past estimates plus a predicted loss for the next round, regularized by a log-barrier term (Equation 3). The regularization strength is set adaptively via per-state-action learning rates that shrink based on observed fluctuations (Equation 21).

The core technical tricks are: (1) an optimistic importance-weighted loss estimator that is unbiased in expectation (Equation 18); (2) a loss-shifting function g_t based on the advantage function of the shifted loss, which enables self-bounding analysis in the stochastic regime (Equation 23); and (3) two choices of loss predictions — a gradient-descent-style predictor with step size ξ = 1/4 (Equations 4–5), useful for path-length bounds, and an empirical-mean predictor (Equation 6), useful for variance-aware gap-dependent bounds.

For global optimization, the algorithm optimizes directly over the convex set of valid occupancy measures Ω(P). For policy optimization, the algorithm optimizes per-state action distributions with an explicit exploration rate γ_t = √(HS)/t and a virtual-episode mechanism (Y_t) to control the effective learning rates; the per-state updates resemble multi-armed bandit problems, using a more optimistic Q-function estimator than prior work to correct bias from loss predictions.

To prove lower bounds, the authors construct adversarial instances and a variance-based instance, showing any algorithm must incur Ω(√(SA L^★)), Ω(√(SA Q_∞)), Ω(√(H V_1)), and Ω(√(SA 𝕍 T)) regret.

Why This Matters

Impact on research. The paper unifies two threads that were previously handled separately: best-of-both-worlds adaptivity and variance-aware analysis. It extends second-order and path-length guarantees — common in multi-armed bandits and online convex optimization — to online episodic tabular MDPs for the first time, and it shows the global-optimization bounds are nearly optimal via matching lower bounds. By avoiding the extra 1/min Δ(s,a) factor of Jin et al. (2021), it sharpens the gap-dependent picture. It also gives a policy-optimization route with the same adaptivity up to an H factor, which matters because policy optimization is the more computationally practical family.

Real-world applications (examples the paper cites as broad MDP applications):

• Robotics control.
• Game playing.
• Healthcare decision-making (e.g., treatment policies).
• Any sequential decision problem where losses are only partially observed and the environment may drift between smooth (stochastic) and hostile (adversarial) phases.

Industry relevance. Best-of-both-worlds guarantees mean practitioners do not need to know a priori whether their environment is stochastic or adversarial before choosing an algorithm, and the adaptivity to loss fluctuation, path length, and variance can translate into faster convergence and tighter performance in slowly-changing or low-variance deployments.

Future Directions

• Unknown transitions. The paper explicitly leaves the unknown-transition setting open: extending the second-order, path-length, variance-dependent, or best-of-both-worlds guarantees to unknown transitions would require additional data-dependent control of transition-estimation errors. For policy optimization, even first-order data-dependent guarantees under unknown transitions remain open per Dann et al. (2023b).

• Closing the H gap for policy optimization. Policy optimization matches global optimization only up to a factor of the horizon H; whether this factor is fundamental or an artifact of the analysis is open.

• Refining the variance-aware gap-dependent bound. Remark 4.3 notes that if the uncorrupted losses are independent and uncorrelated across layers, the gap-dependent bound improves by a factor of H, suggesting further structure could be exploited.

• Extending beyond the tabular, known-transition setting. The complexity measures and OFTRL-based machinery raise the question of whether similar data- and variance-dependent guarantees can be obtained in richer MDP classes or under partial observability, though the paper does not pursue this.

Target Audience

Researchers and graduate students in reinforcement learning theory and online learning who work on regret analysis, best-of-both-worlds algorithms, or variance-aware bounds. It is also relevant to theoretically-minded practitioners who want a single algorithm that adapts across adversarial and stochastic regimes without knowing the environment in advance. Readers should have prior exposure to MDPs, occupancy measures, follow-the-regularized-leader, and regret lower-bound constructions; the paper is not beginner-friendly.

Authors’ abstract

This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic $Q$-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.