Source-linked AI summary
Closing the Horizon Gap in Policy Optimization for Adversarial MDPs
Mingyi Li, Taira Tsuchiya
TL;DR
Policy optimization faced an unresolved extra-horizon-dependence question relative to occupancy-measure approaches. The paper uses regularized Q-functions to analyze local updates jointly across state-action pairs, improving horizon dependence and matching the best-known bound for unknown transitions.
Problem
The paper asks whether policy optimization can improve its extra horizon dependence relative to occupancy-measure approaches.
Source: §1 · pp. 1–2Method
The algorithm incorporates regularization directly into Q-functions and uses them for local policy updates, with stability analyzed jointly across state-action pairs.
Source: §4 · p. 6, §5.3 · p. 9Results
For unknown transitions, the leading regret term improves by a factor of H and matches the best-known upper bound; the paper reports improved horizon dependence in both tabular settings.
Source: §1.1 · p. 2, §7 · p. 13Takeaways & Limitations
For tabular MDPs with unknown transitions, the framework closes the horizon gap between policy optimization and the best available regret bounds from global optimization.
Source: §7 · p. 13The adversary may depend on the learner and past history, but not on the randomness of the current episode.
Source: §3 · p. 5
Abstract
from arXiv · showhide
We consider policy optimization for online episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback. Policy optimization updates the policy locally at each state and avoids optimization over the occupancy-measure polytope, but its existing regret bounds are larger by a factor of the horizon $H$ than those of occupancy-measure-based algorithms. We close this gap by using regularized $Q$-functions, which allow us to control the stability of the local updates jointly over all state-action pairs rather than separately at each state. The resulting algorithm attains high-probability regret bounds of $\widetilde O(\sqrt{HS(H+A)T})$ for known transitions and $\widetilde O(HS\sqrt{AT})$ for unknown transitions, where $S$ is the number of states, $A$ the number of actions, and $T$ the number of episodes. Both bounds improve the horizon dependence of existing policy optimization bounds, and the latter matches the best-known bound. We further extend the algorithm to adversarial linear-mixture MDPs and obtain the same improvement in the horizon dependence.
1 Introduction
The introduction asks whether policy optimization can avoid the extra horizon dependence in its regret bounds without giving up local updates. The paper uses regularized Q-functions to control updates jointly across state-action pairs, improving horizon dependence for tabular MDPs and extending the approach to linear-mixture MDPs.
1 Introduction
- Global optimization can achieve strong regret bounds but may be computationally demanding, while policy optimization retains local updates and its prior bounds incurred an extra factor of H.Removing that extra horizon factor remained an open problem.Source: §1 · pp. 1–2
1.1 Contributions of this paper
- For unknown transitions, the leading regret term improves by a factor of H and matches the best-known upper bound; both tabular settings improve horizon dependence.The paper reports results for known and unknown transitions.Source: §1.1 · p. 2
- Regularized Q-functions connect local policy updates across layers, enabling joint stability analysis over all state-action pairs rather than separate statewise analyses.The regularized value depends recursively on values in the next layer, so optimism propagates backward.Source: §1.1 · pp. 2–3
- For adversarial linear-mixture MDPs, the extension improves the horizon dependence by a factor of H and matches the best-known bound.The transition kernel is assumed linear in a known d-dimensional feature map.Source: §1.1 · p. 3
2 Related work
Prior work compares global optimization over occupancy measures with local policy optimization across several adversarial-MDP feedback settings. The related work also places regularized Q-functions in the context of existing methods for policy updates and exploration.
The horizon gap in policy optimization
- For delayed bandit and preference feedback, prior work reports larger horizon dependence for policy optimization than for global optimization.The preference-feedback comparison concerns adversarial Borda-score rewards, known transitions, and K arms.Source: §2 · p. 3
- Under aggregate bandit feedback, policy optimization is well suited to observing only each trajectory’s total loss, and its known-transition bound matches a lower bound up to logarithmic factors.For unknown transitions, the cited policy-optimization bound is compared with a global-optimization bound that has a larger horizon dependence when SA ≥ H^3.Source: §2 · pp. 3–4
- For adversarial linear-mixture MDPs with unknown transitions and bandit feedback, the cited policy-optimization bound incurs an extra factor of H relative to global optimization.Linear-mixture MDPs use a known d-dimensional feature map to generalize across states and actions.Source: §2 · p. 4
Regularized Q-functions
- Regularized Q-functions have appeared in stochastic control and reinforcement learning, while this paper studies their use for stability analysis under adversarial losses and bandit feedback.Prior connections include policy improvement, dynamic policy programming, regularized-MDP theory, and occupancy-measure updates.Source: §2 · p. 4
3 Preliminaries
The preliminaries specify the episodic tabular MDP, interaction, and regret setting. For unknown transitions, the paper uses confidence sets built from observed transitions.
3 Preliminaries
- The setting is an episodic tabular MDP with a fixed transition kernel, layered states, and losses selected adversarially across T episodes.The learner observes losses only at visited state-action pairs; the objective is regret against the best fixed policy in hindsight.Source: §3 · pp. 4–5
3.1 Confidence sets
- For unknown transitions, confidence sets are imposed separately on each state-action pair, making the resulting set of transition kernels rectangular.The true transition kernel belongs to every episode’s confidence set with probability at least 1 − 4δ.Source: §3.1 · p. 5
- When transitions are known, the confidence set is the singleton containing the true transition kernel; upper and lower occupancies can be computed by dynamic programming over layers.The confidence-set passage states that the true kernel remains in the sets with probability at least 1 − 4δ when transitions are unknown.Source: §3.1 · p. 5
4 Regularized Q-functions
The paper uses regularized Q-functions to incorporate an exploration correction into local policy updates. These updates can also be interpreted jointly as solving a regularized occupancy-measure optimization problem.
4 Regularized Q-functions
- The regularized Q-function incorporates an exploration correction directly, and the policy is updated using that function rather than an ordinary Q-function with a separately subtracted bonus.The cited existing algorithms estimate an ordinary Q-function and subtract an exploration bonus.Source: §4 · p. 6
4.1 Relation to exploration bonuses
- The regularized Q-function implicitly incorporates the exploration bonus used in the update of Luo et al. (2021).The bonus is expressed through the ordinary Q-function evaluated at a statewise correction.Source: §4.1 · pp. 6–7
4.2 Relation to global optimization
- The local updates together solve a KL-regularized occupancy-measure problem, enabling joint analysis across state-action pairs while retaining per-state policy optimization.The occupancy-measure interpretation is used to analyze updates jointly, even though the algorithm optimizes over action distributions separately at each state.Source: §4.2 · p. 7
5 Main algorithm
The algorithm estimates losses from bandit observations, constructs optimistic regularized Q-functions, and updates policies locally. Its regret bounds improve the horizon dependence of policy optimization, with the unknown-transition leading term matching a best-known bound.
5.1 Algorithm design
- The algorithm first estimates losses from bandit feedback, then constructs an optimistic Q-function by minimizing the regularized Q-function over the transition confidence set.It uses the estimated losses as input and the current policy as the reference policy; a minimizing kernel is shared across state-action pairs because the set is rectangular.Source: §5.1 · pp. 7–8
- The algorithm updates each state’s action distribution with exponential weights using the optimistic regularized Q-values.The Q-values are computed backward from the terminal layer, and the policy update uses the current policy as its reference.Source: §5.1 · pp. 7–8
5.2 Regret upper bounds
- The bounds improve policy optimization’s horizon dependence in both transition settings, and the unknown-transition leading term matches the best-known global-optimization bound.For known transitions, the cited comparison is with Zimin and Neu (2013); for unknown transitions, the match is with Jin et al. (2020).Source: §5.2 · pp. 8–9
5.3 Regret analysis
- The regret analysis decomposes error into learner loss-estimation error, regret on estimated losses, and comparator estimation error.Unlike statewise performance-difference decompositions, the analysis treats state-action pairs jointly, using regularized Q-functions to connect local updates across layers.Source: §5.3 · p. 9
6 Linear-mixture MDPs
The section extends the algorithm to adversarial linear-mixture MDPs and gives a regret bound that improves policy optimization’s horizon dependence by a factor of H, matching the best-known bound up to logarithmic factors.
6 Linear-mixture MDPs
- The algorithm extends to adversarial MDPs with linear-mixture transitions under a feature-normalization assumption.The assumption uses known features and a known bound on the unknown transition parameters.Source: §6 · pp. 11–12
- The extension estimates θ_h and constructs confidence sets that are used in Algorithm 1 in place of the earlier transition confidence sets.The confidence sets contain the true transition kernel for all episodes with probability at least 1−δ; they are rectangular across state-action pairs.Source: §6 · p. 12
- The linear-mixture bound improves policy optimization’s horizon dependence by H and matches the best-known occupancy-measure bound up to logarithmic factors.The comparison is to the bound achieved by the occupancy-measure method of Li et al. (2024).Source: §6 · p. 12
7 Conclusion
The paper introduces regularized Q-functions to improve regret bounds while retaining local policy updates, closing the horizon gap for tabular MDPs with unknown transitions. It leaves extensions to delayed feedback and best-of-both-worlds settings for future work.
7 Conclusion
- The framework uses regularized Q-functions to improve regret bounds while retaining local policy updates.Source: §7 · p. 13
- For tabular MDPs with unknown transitions, the algorithm closes the horizon gap between policy optimization and the best available regret bounds achieved by global optimization.Source: §7 · p. 13
- The paper identifies delayed-feedback and best-of-both-worlds settings as possible future extensions of the framework.The authors state they believe the framework can reduce horizon dependence in those settings.Source: §7 · p. 13
AI use statement
The authors report AI assistance with proof development and checking, literature searches, and editing, and state that they reviewed the work and take responsibility for the paper.
AI use statement
- GPT-6-Astra, GPT-6.1-Sol, and Claude Opus 5.5 assisted with proof development and checking, literature searches, and editing.Source: AI use statement · p. 13
- The authors say they reviewed all AI-assisted work and take responsibility for the paper.Source: AI use statement · p. 13
A Proofs deferred from Section 5
The appendix supplies proofs for Theorems 5.1 and 5.2 and supporting lemmas, using a regret decomposition under a high-probability confidence event.
A Proofs deferred from Section 5
- The authors prove Theorems 5.1 and 5.2, along with the supporting Lemmas 5.3 and 5.5.Source: A Proofs deferred from Section 5 · p. 16
- Under P∈P_t for all episodes, the regret decomposition and Lemmas 5.3, 5.5, and 5.6 yield the theorem with probability at least 1−3δ.Source: A Proofs deferred from Section 5 · p. 16
- For known transitions, P_t={P}, so the final term in the bound is zero.Source: A Proofs deferred from Section 5 · p. 17
B Proofs deferred from Section 6
This section defers proofs of Theorems 5.2 and 6.3. The proof of Theorem 6.3 invokes Section 6, equation (18), Lemma 6.2, and sets γ = η.
B Proofs deferred from Section 6
- The section identifies Theorem 5.2 as proved in the deferred proofs.Source: B Proofs deferred from Section 6 · p. 17
- Theorem 6.3's proof uses the Section 6 guarantee, equation (18), Lemma 6.2, and the choice γ = η.It states probability at least 1 − δ for P ∈ P_t for all t ∈ [T], then gives a subsequent bound with probability at least 1 − 5δ.Source: B Proofs deferred from Section 6 · p. 17
- The proof's final inequality uses H ≤ S.Source: B Proofs deferred from Section 6 · p. 17
C Concentration inequalities
This section collects concentration inequalities used in the regret proofs, including Azuma–Hoeffding and a result attributed to Jin et al. (2020).
C Concentration inequalities
- The section provides concentration inequalities used in the regret proofs.Source: C Concentration inequalities · p. 17
- Azuma–Hoeffding applies to conditionally mean-zero, bounded, F_{t+1}-measurable variables.The stated conditions are E_t[X_t] = 0 and |X_t| ≤ R almost surely for every t.Source: C Concentration inequalities · p. 17
- A lemma attributed to Jin et al. (2020, Lemma 11) concerns F_t-measurable functions α_t: S × A → [0, 2γ].Source: C Concentration inequalities · p. 17