Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

The gist: Policy optimization updates 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

Motivation and Problem Context

The paper studies policy optimization for online learning in episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback Policy optimization updates the action distribution locally at each state (Shani et al., 2020; Luo et al., 2021) The learner aims to minimize the regret, the gap between the cumulative loss of the learner and that of the best fixed policy in hindsight Global optimization solves an optimization problem over the occupancy-measure polytope in each episode However, global optimization can be computationally demanding for large MDPs Policy optimization is a computationally efficient alternative, which updates the action distribution locally at each state (Shani et al., 2020; Luo et al., 2021).

Proposed Solution: Regularized Q-functions

The authors close the gap by using regularized Q-functions, which allow them to control the stability of the local updates jointly over all state-action pairs rather than separately at each state These regularized Q-functions yield more optimistic Q-function estimates while retaining local policy updates at each state The algorithm updates the policy by exponential weights with regularized Q-functions and covers both known and unknown transitions. Regularized Q-functions connect the local policy updates across layers, allowing them to analyze their stability together.

Relation to Exploration Bonuses and Global Optimization

The regularized Q-function implicitly incorporates an exploration bonus introduced by Luo et al. (2021) The statewise gap g(s) is defined such that the regularized value function is related to the ordinary value function by Ve π(s; f − g) for every s ∈ S. Furthermore, the local policy updates solve a global optimization problem over occupancy measures The Bregman divergence DΨ induced by the negative conditional entropy Ψ(q) = P s,a q(s, a) log(q(s, a)/q(s)) satisfies DΨ(q π′, q π) = X s q π′ (s) KL π′ (· s)∥ π (· s).

Algorithm and Regret Bounds

The main algorithm updates the policy at each state by choosing the minimizer in equation (4), namely, α(a s) ∝ π(a s)e−ηQπ(s,a;f). The algorithm achieves high-probability regret bounds of Oe(p HS(H + A)T) for known transitions and Oe(HS√ AT) for unknown transitions. Specifically, under known transitions, Algorithm 1 with γ = η = qH log(SA/δ) S(H+A)T achieves RegT ≲ s HS(H + A)T log SA/δ + H2 log SA/δ. Under unknown transitions, the algorithm achieves RegT ≲ HSs AT log SAT/δ + S3A log2 SAT/δ.

Extension to Linear-mixture MDPs

The algorithm is extended to adversarial linear-mixture MDPs where the transition kernel is linear in a known d-dimensional feature map Under Assumption 6.1, Algorithm 1 with the confidence sets (17) and γ = η = qH log(SAT /δ) S(H+A)T satisfies RegT ≲ s HSAT log SAT/δ + dS3/2√HT log SAT/δ. This bound improves the horizon dependence of the policy optimization bound of Cheng et al. (2026) by a factor of H and matches the best-known bound of Li et al. (2024).

Conclusion

The framework introduced based on regularized Q-functions improves the horizon dependence of regret bounds while retaining local policy updates For tabular MDPs with unknown transitions, this algorithm closes the horizon gap between policy optimization and the best available regret bounds achieved by global optimization. The authors believe this framework can also reduce the horizon dependence of policy optimization under delayed feedback and in best-of-both-worlds settings. The paper concludes by proving Theorem 5.1 and Theorem 5.2 for known and unknown transitions, respectively. The proof of Theorem 6.3 confirms the improvement for linear-mixture MDPs.

--- Page 1 ---

Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

for online episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback Mingyi Li∗ Taira Tsuchiya† October 8, 2026 Abstract We consider policy optimization for online learning in 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 Oe(p HS(H + A)T) for known transitions and Oe(HS√ 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 We study policy optimization for online learning in episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback Policy optimization is widely used in reinforcement learning and has achieved empirical success (e.g., Schulman et al., 2015, 2017) In each of T episodes, the environment chooses a loss function, and the learner chooses and executes a policy, observing losses only at the visited state-action pairs The learner aims to minimize the regret, the gap between the cumulative loss of the learner and that of the best fixed policy in hindsight Algorithms for online learning in episodic tabular MDPs typically use either global optimization or policy optimization Global optimization solves an optimization problem over the occupancy-measure polytope in each episode With this approach, Zimin and Neu (2013) achieve minimax-optimal regret Oe(√HSAT) for known transitions, and Jin et al. (2020) achieve the best-known regret bound of Oe(HS√ AT) for unknown transitions, where H is the horizon, S the number of states, and A the number of actions However, global optimization can be computationally demanding for large MDPs Policy optimization is a computationally efficient alternative, which updates the action distribution locally at each state (Shani et al., 2020; Luo et al., 2021) The best-known regret bounds for policy optimization are Oe(√H3SAT) for known transitions and Oe(H2S√ AT) for unknown transitions (Luo et al., 2021). These bounds have an extra factor of the horizon H compared to those of global optimization. Later work on∗The University of Tokyo; mingyi-mike@g.ecc.u-tokyo.ac.jp.†The University of Tokyo, The University of Osaka, and RIKEN; tsuchiya@mist.i.u-tokyo.ac.jp.> 1 arXiv:2610.12362v1 [cs:LG] 8 Oct 2026

--- Page 2 ---

Table 1: Regret upper bounds for episodic tabular MDPs with adversarial losses and bandit feedback under known and unknown transitions. Logarithmic factors and lower-order terms are omitted Reference Known transitions Unknown transitions Policy optimization Zimin and Neu (2013) √HSAT — — Jin et al. (2020) — HS√ AT Luo et al. (2021) √H3SAT H2S√ AT This work p HS(H + A)T HS√ AT Table 2: Regret upper bounds for adversarial linear-mixture MDPs with bandit feedback. Logarithmic factors and lower-order terms are omitted Reference Policy optimization Li et al. (2024) √HSAT + dS3/2 √HT — Cheng et al.

1. Bold Q-function Regularization for Stability: Implement regularized Q-functions, defined by equations (2) and (3), to control the stability of local updates jointly over all state-action pairs rather than separately at each state, which is shown to reduce the extra horizon dependence.

2. Closing the Horizon Gap for Unknown Transitions: The algorithm attains high-probability regret bounds of Oe(HS√AT) for unknown transitions, matching the best-known bound, improving upon previous policy optimization bounds of Oe(H2S√AT).

3. Improved Regret Bounds under Known Transitions: For known transitions, the algorithm achieves regret bounds of Oe(pHS(H + A)T) when using the specific learning rate choice, which improves the horizon dependence compared to existing results.

4. Feature-Based Generalization for Linear MDPs: Extend the framework to adversarial linear-mixture MDPs where transitions are defined by known feature maps, achieving a bound of Oe(√HSAT + dS3/2√HT) that matches the best-known global optimization bound.

5. Optimistic Exploration via Implicit Bonus: The regularized Q-function implicitly incorporates an exploration bonus, as shown by the identity in equation (7): The right-hand side of (7) is the update of Luo et al. (2021) with the exploration bonus Qπ(s, a; g).