Paper review · November 16, 2026
Deliberately adding feedback delay to reach optimal √S and √K regret in adversarial MDPs: tabular and linear AMDPs
Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal $\sqrt S$ and $\sqrt K$ Dependencies in Tabular and Linear AMDPs
A technique of "intentional feedback delay," which evaluates the current policy with future episodes, closes both the √S gap in tabular AMDPs and the √K gap in linear AMDPs.
Problem
In adversarial MDPs where the transition probabilities are unknown and only the losses of state-action pairs actually visited are observed (bandit feedback), it is hard to estimate the Q-function of a changing policy. Past data comes from earlier policies that differ from the current one, so uncertainty is high; fixing the policy to collect future data worsens the dependence on K. As a result, the best regret for tabular AMDPs, Õ(HS√(AK)), was larger than the lower bound Ω(H√(SAK)) by a factor of √S. For linear AMDPs, computationally efficient algorithms were stuck at Õ(K^{3/4}).
Method
After running policy π_k, the method estimates π_k's Q-function using trajectories from later episodes. Meanwhile, the policy is still updated every episode. Because this is treated as if the feedback arrived late, techniques for delayed AMDPs can be borrowed directly. Trajectories obtained under other policies are treated as new trajectories of π_k through rejection sampling. Combining this with Geometric Resampling gives GRR (Geometric Resampling with Rejection), which estimates the inverse visitation probability 1/q. State-action pairs that are rarely visited are not estimated; instead, a large exploration bonus offsets the error (thresholding). For linear AMDPs, MGRR, which estimates the inverse covariance matrix, is applied separately to O(log K) feature regions.
Results
- For tabular AMDPs, it guarantees Õ(H^{5/2}√(SAK)) regret with high probability. The authors report that this is the first result matching the lower bound Ω(H√(SAK)) in its dependence on S, A and K, resolving an open problem posed by Jin et al. (2020).
- For linear AMDPs, it achieves Õ(d³H⁴√K) regret. It is the first computationally efficient algorithm that is optimal in K without a simulator or exploration assumptions, improving on the previous best of Õ(d^{3/2}H³K^{3/4}) (Liu et al., 2024).
- It also extends to delayed AMDPs with total delay 𝔇: Õ(H^{5/2}√(SAK)+H³√𝔇) for the tabular case and Õ(d³H⁴√K+d^{3/2}H³√𝔇) for the linear case. The authors report that these are the first bounds optimal in S and 𝔇, and in K and 𝔇, respectively.
- Because it is a policy optimization method, updates are computed in closed form and no oracle calls are needed. The authors contrast this with concurrent work (Liu et al., 2026), which gives bounds in expectation and requires Ω(K²) oracle calls.
Limitations
This is purely theoretical work with no experiments or validation in real environments. The dependence on H and d (H^{5/2}, d³H⁴) is higher than the lower bounds (H, dH^{3/2}), so it is not optimal in these terms. Additive terms independent of K are omitted from the bounds. The provided text includes only the first part of the paper, so the details of the proofs could not be checked.
Why it matters
It resolves two long-standing gaps in reinforcement learning theory with a single technique. The key idea is to use delay as a design tool rather than an obstacle to avoid. The authors believe the technique could apply to other problems where a changing policy must be evaluated without fixing the future.
Key terms
- Adversarial MDP (AMDP)
- An MDP in which an adversary sets the loss function for each episode in advance. Performance is measured by regret: the difference in cumulative loss compared with the best policy in hindsight.
- Bandit feedback
- A setting in which only the losses of state-action pairs actually visited are observed. The losses of options not taken remain unknown.
- Geometric Resampling
- A technique that uses the number of sampling trials to estimate, without bias, the inverse of the probability that an event occurs. This paper adds rejection sampling to it to create GRR.
- Occupancy measure
- The probability that a policy visits each state-action pair. When the transition probabilities are unknown, it cannot be computed exactly and must be estimated.
Original
Authors: Aarush Kulkarni, Khang Nguyen, William Chang, Yan Dai · Posted 2026-11-12 · License arXiv 비독점 배포 라이선스 · Based on the full text
This review is an AI-written summary of the paper. Please treat the original paper as the reference.