Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal and Dependencies in Tabular and Linear AMDPs
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 states, actions, and horizon , the best known -episode regret is , whose gap to the lower bound has long remained open. In linear AMDPs with -dimensional features, after a five-year line of improvements starting from , computationally efficient algorithms without a simulator or exploratory assumptions still only attain 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 . 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, regret in tabular AMDPs, resolving the open problem; and regret in linear AMDPs, giving the first efficient algorithm optimal in . They also naturally extend to delayed AMDPs with a total feedback delay , yielding the first bounds optimal in and (tabular) and in and (linear).
Figures & tables
| Tabular AMDP | Linear AMDP | ||
|---|---|---|---|
| Bandit | Delayed Bandit | Bandit | Delayed Bandit |
| \widetilde{\mathcal{O}}(H^{3/2}{\color[rgb]{0.7,0,0}\bm{SA^{1/4}K^{3/4}}}) ( Rosenberg and Mansour, 2019b ) \widetilde{\mathcal{O}}(H{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}) ( Jin et al., 2020a ) \widetilde{\mathcal{O}}(H^{2}{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}) ( Luo et al., 2021 ) \widetilde{\mathcal{O}}(H{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}) ( Dai et al., 2022 ) \widetilde{\mathcal{O}}(H^{2}{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}) ( Dann et al., 2023 ) \widetilde{\mathcal{O}}(H{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}) ( Li and Tsuchiya, 2026 ) | \widetilde{\mathcal{O}}({\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{A}}}{\color[rgb]{0.7,0,0}\bm{K^{2/3}}}+{} H^{2}{\color[rgb]{0.7,0,0}\bm{\mathfrak{D}^{2/3}}}) ( Lancewicki et al., 2022 ) \widetilde{\mathcal{O}}(H{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}+{} H{\color[rgb]{0.7,0,0}\bm{\sqrt[4]{SA}}}{\color[rgb]{0,0.5,0}\bm{\sqrt{\mathfrak{D}}}}) ( Jin et al., 2022 ) \widetilde{\mathcal{O}}(H{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}+{} H{\color[rgb]{0.7,0,0}\bm{\sqrt{SA}}}{\color[rgb]{0,0.5,0}\bm{\sqrt{\mathfrak{D}}}}) ( Dai et al., 2022 ) \widetilde{\mathcal{O}}(H^{2}{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}+{} H^{3}{\color[rgb]{0,0.5,0}\bm{\sqrt{\mathfrak{D}}}}) ( Lancewicki et al., 2023 ) \widetilde{\mathcal{O}}(H{\color[rgb]{0.7,0,0}\bm{S}}{\color[rgb]{0,0.5,0}\bm{\sqrt{AK}}}+{} H{\color[rgb]{0,0.5,0}\bm{\sqrt{\mathfrak{D}}}}) ( Zierahn et al., 2025 ) 3 3 3 Their bound also exhibits a linear dependency on the maximum feedback delay . | \widetilde{\mathcal{O}}(d^{2}H^{4}{\color[rgb]{0.7,0,0}\bm{K^{14/15}}}) ( Luo et al., 2021 ) \widetilde{\mathcal{O}}(d^{2/3}H^{20/9}{\color[rgb]{0.7,0,0}\bm{A^{1/9}K^{8/9}}}) ( Dai et al., 2023 ) \widetilde{\mathcal{O}}(dH^{2}{\color[rgb]{0.7,0,0}\bm{K^{6/7}}}+{} d^{3/2}H^{4}{\color[rgb]{0.7,0,0}\bm{K^{5/7}}}) ( Sherman et al., 2023 ) \widetilde{\mathcal{O}}(d^{7/5}H^{12/5}{\color[rgb]{0.7,0,0}\bm{K^{4/5}}}) (inefficient) ( Kong et al., 2024 ) 4 4 4 Their bound additionally requires an exploratory assumption (see Footnote 7 ). \widetilde{\mathcal{O}}(d^{3/2}H^{3}{\color[rgb]{0.7,0,0}\bm{K^{3/4}}}) ( Liu et al., 2024 ) \widetilde{\mathcal{O}}(d^{7/2}H^{7/2}{\color[rgb]{0,0.5,0}\bm{\sqrt{K}}}) (inefficient) ( Liu et al., 2024 ) | \widetilde{\mathcal{O}}(d^{5/4}H^{3}{\color[rgb]{0.7,0,0}\bm{K^{3/4}}}+{} H^{2}{\color[rgb]{0.7,0,0}\bm{\mathfrak{D}^{3/4}}}) ( Lancewicki et al., 2023 ) 5 5 5 Their bound additionally assumes a simulator, which draws trajectories from any state-action pair for free. |
| \widetilde{\mathcal{O}}(H^{5/2}{\color[rgb]{0,0.5,0}\bm{\sqrt{SAK}}}) ( Theorem 4.1 ) | \widetilde{\mathcal{O}}(H^{5/2}{\color[rgb]{0,0.5,0}\bm{\sqrt{SAK}}}+{} H^{3}{\color[rgb]{0,0.5,0}\bm{\sqrt{\mathfrak{D}}}}) ( Theorem 6.1 ) | \widetilde{\mathcal{O}}(d^{3}H^{4}{\color[rgb]{0,0.5,0}\bm{\sqrt{K}}}) ( Theorem 5.1 ) | \widetilde{\mathcal{O}}(d^{3}H^{4}{\color[rgb]{0,0.5,0}\bm{\sqrt{K}}}+{} d^{3/2}H^{3}{\color[rgb]{0,0.5,0}\bm{\sqrt{\mathfrak{D}}}}) ( Theorem 6.2 ) |
| \Omega(H{\color[rgb]{0,0.5,0}\bm{\sqrt{SAK}}}) ( Jin et al., 2018 ) | \Omega(H{\color[rgb]{0,0.5,0}\bm{\sqrt{SAK}}}+{} H{\color[rgb]{0,0.5,0}\bm{\sqrt{\mathfrak{D}}}}) ( Lancewicki et al., 2022 ) | \Omega(dH^{3/2}{\color[rgb]{0,0.5,0}\bm{\sqrt{K}}}) ( Zhou et al., 2021 ) | \Omega(dH^{3/2}{\color[rgb]{0,0.5,0}\bm{\sqrt{K}}}+{} H{\color[rgb]{0,0.5,0}\bm{\sqrt{\mathfrak{D}}}}) ( Zhou et al., 2021 ; Lancewicki et al., 2022 ) |
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Regret Minimization in RL
Regret minimization in reinforcement learning develops agents that learn effective policies while limiting cumulative loss against an optimal benchmark.
See all 70 papers