Adversarial MDP Policy Optimization: Regularized Q-Functions Eliminate the Horizon Gap

Title

Adversarial MDP Policy Optimization: Regularized Q-Functions Eliminate the Horizon Gap

Meta Description

Policy optimization under adversarial MDPs has long suffered from a Horizon gap. This work uses regularized Q-functions to jointly control stability across state-action pairs, improving the regret bound by a factor of H, matching the optimal bound under unknown transitions, and extending to linear-mixture MDPs.

Article Content

In reinforcement learning theory, policy optimization and occupancy-measure methods have long been separated by a gap known as the "Horizon gap." A recent theoretical study offers a breakthrough solution: through regularized Q-functions, it improves the regret bound of policy optimization under adversarial MDPs by an entire factor of $H$.

Background: Why the Horizon Gap Is So Stubborn

Consider an online episodic tabular MDP where the loss function is adversarial—that is, the environment can choose an arbitrary loss at each round, even adversarially based on the algorithm's history, while feedback is bandit-style (only the loss of the chosen action is observed). This is a stricter setting than stochastic losses.

Policy optimization is popular because it updates the policy locally at each state, avoiding global optimization over the entire occupancy-measure polytope, making it simpler in both computation and implementation. The cost is that existing regret bounds are a factor of $H$ larger than those of occupancy-measure-based algorithms. Intuitively, this is because local updates only guarantee stability at individual states, whereas global algorithms can uniformly control the accumulation of errors across all state-action pairs.

Occupancy Measure characterizes the frequency with which a policy visits state-action pairs in an MDP: for a policy $\pi$, its occupancy measure $d^\pi(s,a)$ represents the expected number of visits to state-action pair $(s,a)$ under $\pi$ (or the normalized distribution). In episodic MDPs, the occupancy measure simultaneously encodes the policy's long-term behavior. Occupancy-measure-based algorithms (such as linear programming or mirror descent) rewrite the entire policy optimization problem as convex optimization over the occupancy-measure polytope, thereby controlling error accumulation across all state-action pairs globally—which is precisely the fundamental reason their regret bounds are smaller by a factor of $H$. However, such methods require explicitly maintaining or optimizing the entire polytope, making them far more complex in computation and implementation than state-by-state locally updating policy optimization. This constitutes the motivation for this paper's attempt to close the gap.

Adversarial MDP is a stricter setting compared to stochastic-loss MDPs: at each round $t$, the environment can choose an arbitrary loss function $\ell_t(s,a)$ (possibly depending on the algorithm's history) rather than independently sampling from a fixed distribution. Since losses can vary arbitrarily over time, the algorithm must be more robust to uncertainty. Meanwhile, feedback is bandit-style—the algorithm can only observe the loss of the action actually taken, not those of other actions. In the adversarial setting, standard optimistic or upper-confidence-bound methods no longer apply directly, and regret analysis typically requires adversarial techniques from online learning (such as Follow-the-Regularized-Leader, FTRL) along with more refined stability arguments. This paper proves, under this harder setting, that policy optimization can achieve the same horizon dependence as occupancy-measure methods.

Core Method: Jointly Controlling Stability Across State-Action Pairs

The paper's key insight is: by switching to regularized Q-functions instead of relying solely on local policy gradients, stability control can be upgraded from "per-state independent" to "joint across all state-action pairs." In this way, the extra error introduced by local updates no longer inflates linearly with the horizon, and the $H$ gap is completely eliminated.

The final algorithm achieves the following regret bounds:

• Known transitions: $\widetilde O(\sqrt{HS(H+A)T})$
• Unknown transitions: $\widetilde O(HS\sqrt{AT})$

where $S$ is the number of states, $A$ is the number of actions, and $T$ is the number of rounds. Both results improve the horizon dependence of existing policy optimization bounds; the latter even matches the known optimal bound—meaning policy optimization no longer has any theoretical disadvantage in this setting.

Regularized Q-function refers to introducing a convex regularization term (e.g., entropy regularization or $L_2$ regularization) into the Q-function update, such that the Q-value update for each state-action pair depends not only on the current local gradient but also couples with the global policy distribution through the regularization term. In this paper's analysis, the regularized Q-function serves as a "global stabilizer": it constrains the policy update step sizes across all state-action pairs uniformly, thereby transforming the error that would accumulate linearly in per-state independent analysis into a jointly controllable quantity. Intuitively, standard policy gradients only perform local updates at the current state, and errors across different states cannot cancel each other out; whereas regularized Q-functions couple the updates of different states through a global regularization term, so that errors no longer amplify along the horizon dimension, ultimately eliminating the $H$-factor gap.

Significance and Extensions: Linear-Mixture MDPs Also Benefit

The authors further extend the algorithm to adversarial linear-mixture MDPs and obtain the same improvement in horizon dependence. This shows that the idea of regularized Q-functions is not limited to the tabular case and has potential for generalization in function approximation scenarios.

For the reinforcement learning theory community, this work answers a long-standing open question: is policy optimization inherently a factor of $H$ worse than occupancy-measure methods? The answer is no—the gap stems from limitations of analytical tools, not from the algorithmic paradigm itself. This provides a new path for designing policy optimization algorithms with tight regret bounds in more general settings such as function approximation and multi-agent systems.

Linear-Mixture MDP is a class of function approximation settings: the transition probability is assumed to be a linear combination of several known basis features, i.e., $P(s'|s,a) = \sum_{i=1}^d \phi_i(s'|s,a) \theta_i$, where $\phi_i$ are known features and $\theta$ are unknown parameters. It lies between tabular MDPs (where features are indicator functions) and general function approximation, allowing the state space to be enormous or even continuous while still retaining a learnable linear structure. In the adversarial setting, losses can still be chosen arbitrarily each round, but the linear structure of transitions provides estimable parameters for the algorithm. This paper extends the regularized Q-function method to this setting while maintaining the same improvement in horizon dependence, demonstrating that the technique does not rely on the finiteness of the tabular case and offers a feasible direction for more general function approximation scenarios.

One-line Summary

Eliminating the Horizon gap between policy optimization and occupancy-measure methods using regularized Q-functions, while matching the optimal regret bound.

Paragraph Summary

This paper addresses the long-standing issue that policy optimization under adversarial MDPs has a regret bound larger by a factor of H than occupancy-measure methods. It proposes using regularized Q-functions to achieve joint stability control across all state-action pairs, thereby eliminating the Horizon gap. In online episodic tabular MDPs, the algorithm achieves regret bounds of Õ(√HS(H+A)T) under known transitions and Õ(HS√AT) under unknown transitions, the latter matching the known optimal bound, meaning policy optimization no longer has a theoretical disadvantage. The authors further generalize the method to adversarial linear-mixture MDPs, obtaining the same improvement in horizon dependence, indicating that this idea is universal in function approximation scenarios and provides a new path for designing policy optimization algorithms with tight regret bounds.