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

Aarush Kulkarni, Khang Nguyen, William Chang, Yan Dai

Massachusetts Institute of Technology +2 · arXiv

Affiliations: Massachusetts Institute of Technology, University of California Los Angeles, University of Southern California

Paper

Abstract

We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback. In tabular AMDPs with $S$ states, $A$ actions, and horizon $H$, the best known $K$-episode regret is $\tilde O(HS\sqrt{AK})$, whose $\sqrt S$ gap to the $Ω(H\sqrt{SAK})$ lower bound has long remained open. In linear AMDPs with $d$-dimensional features, after a five-year line of improvements starting from $K^{14/15}$, computationally efficient algorithms without a simulator or exploratory assumptions still only attain $\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 $K$. 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, $\tilde O(\text{poly}(H)\sqrt{SAK})$ regret in tabular AMDPs, resolving the open problem; and $\tilde O(\text{poly}(d,H)\sqrt K)$ regret in linear AMDPs, giving the first efficient algorithm optimal in $K$. They also naturally extend to delayed AMDPs with a total feedback delay $\mathfrak D$, yielding the first bounds optimal in $S$ and $\mathfrak D$ (tabular) and in $K$ and $\mathfrak D$ (linear).

The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.

Research summary

The paper resolves a long-standing open problem in adversarial reinforcement learning by introducing a novel technique of voluntary feedback delays to achieve optimal regret bounds in tabular and linear AMDPs. It provides a unified framework that improves upon previous state-of-the-art results by eliminating the need for freezing policies or relying on past data mismatches, offering a significant theoretical advance in the field of online learning with partial information.

Methodology

The paper introduces a novel technique called "introduced feedback delays" to solve the regret minimization problem in Adversarial Markov Decision Processes (AMDPs). The core innovation is the voluntary introduction of delays in feedback processing to allow for the estimation of Q-functions using future episodes while continuing to update policies. This is facilitated by two key procedures: Geometric Resampling with Rejection (GRR) to handle policy changes during the delay via rejection sampling, and thresholding of visitation probabilities to avoid long delays on rarely visited state-action pairs. The method is unified across tabular and linear AMDPs, and naturally extends to delayed AMDPs. The theoretical analysis is rigorous, providing high-probability regret bounds that match lower bounds in key parameters ($S, A, K$ for tabular; $K$ for linear).

Results & evaluation

This is a purely theoretical paper. There are no empirical experiments, benchmarks, or datasets presented. The contribution is entirely in the form of theoretical guarantees and algorithm design. Therefore, experimental evaluation is not applicable in the traditional sense, but the theoretical results are the primary deliverable.

Reproducibility

The algorithms are described in sufficient detail for implementation, including the GRR procedure, thresholding mechanisms, and policy updates. The theoretical proofs are provided in the appendix (implied by the structure). However, without code or empirical validation, reproducibility is limited to theoretical verification.

Limitations

The paper is purely theoretical and lacks empirical validation on real-world or simulated environments. The complexity of the algorithms (involving resampling and rejection) may pose practical implementation challenges. The results are specific to the AMDP model with oblivious adversaries and may not directly translate to other RL settings without further adaptation.

Broader impact

The resolution of the open problem regarding the $\sqrt{S}$ gap in tabular AMDPs and the $K$ gap in linear AMDPs is significant for the online learning and reinforcement learning communities. The "introduced feedback delays" technique is a general tool that could be applied to other problems involving changing policies and partial information. It advances the state-of-the-art in computationally efficient regret minimization for adversarial settings. The paper resolves a long-standing open problem in adversarial reinforcement learning by introducing a novel technique of voluntary feedback delays to achieve optimal regret bounds in tabular and linear AMDPs. It provides a unified framework that improves upon previous state-of-the-art results by eliminating the need for freezing policies or relying on past data mismatches, offering a significant theoretical advance in the field of online learning with partial information.

Author of this paper? Send a correction.