cs.LGNov 12, 2026

Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal S\sqrt S and K\sqrt K Dependencies in Tabular and Linear AMDPs

Authors: Aarush Kulkarni, Khang Nguyen, William Chang, Yan Dai

Organizations: Independent Researcher · Department of Mathematics, University of Southern California · Department of Mathematics, University of California Los Angeles · Operations Research Center, Massachusetts Institute of Technology

Abstract

We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback. In tabular AMDPs with SS states, AA actions, and horizon HH, the best known KK-episode regret is O~(HSAK)\tilde O(HS\sqrt{AK}), whose S\sqrt S gap to the Ω(HSAK)Ω(H\sqrt{SAK}) lower bound has long remained open. In linear AMDPs with dd-dimensional features, after a five-year line of improvements starting from K14/15K^{14/15}, computationally efficient algorithms without a simulator or exploratory assumptions still only attain O~(K3/4)\tilde O(K^{3/4}) regret. A common challenge in both settings is to estimate the Q-function of a changing policy: past data comes from earlier policies that differ from (and are correlated with) the current one, while freezing the policy for future episodes worsens the dependency on KK. We instead propose a general technique called introduced feedback delays: we estimate the Q-function of the policy using future episodes while still updating the policy, as if the feedback were delayed. While feedback delays are usually an obstacle imposed by the environment, here they are introduced voluntarily and, perhaps surprisingly, come at no extra cost. We develop Geometric Resampling with Rejection (GRR) to account for policy changes during the delay, and threshold the visitation probabilities to avoid long delays on rarely visited state-action pairs. With this unified technique, our policy optimization algorithms achieve, with high probability, O~(poly(H)SAK)\tilde O(\text{poly}(H)\sqrt{SAK}) regret in tabular AMDPs, resolving the open problem; and O~(poly(d,H)K)\tilde O(\text{poly}(d,H)\sqrt K) regret in linear AMDPs, giving the first efficient algorithm optimal in KK. They also naturally extend to delayed AMDPs with a total feedback delay D\mathfrak D, yielding the first bounds optimal in SS and D\mathfrak D (tabular) and in KK and D\mathfrak D (linear).

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Oct 22, 2026

A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

We study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback. The state-of-the-art result for this setting (Liu et al., 2024) either achieves K\sqrt{K} regret with a computationally inefficient algorithm or achieves suboptimal K3/4K^{3/4} regret, where KK is the number of episodes. Our work gives the first K\sqrt{K} regret with a polynomial-time algorithm. Our method reduces adversarial linear MDPs to adversarial linear bandits whose action set consists of policies' expected feature vectors. The central challenge is that this action set is unknown and can be estimated only through exploration. We address this challenge by constructing an approximate separation oracle for the action set that either generates executable policies from queried features, or refines an outer approximation of the action set. This approach draws inspiration from the reduction of van Erven et al. (2025) for linear contextual bandits and the oracle-efficient linear bandit algorithm of Ito et al. (2019), but additionally deals with the imprecision of the oracle. The resulting algorithm requires only aggregate loss feedback, and to our knowledge. This is the first polynomial-time algorithm for adversarial MDPs with aggregate feedback beyond the tabular case.
Oct 8, 2026

Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

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 HH than those of occupancy-measure-based algorithms. We close this gap by using regularized QQ-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 O~(HS(H+A)T)\widetilde O(\sqrt{HS(H+A)T}) for known transitions and O~(HSAT)\widetilde O(HS\sqrt{AT}) for unknown transitions, where SS is the number of states, AA the number of actions, and TT 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.
Feb 2, 2026

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

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 QQ-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.