← Key papers

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

Reinforcement learning Advanced cs.LG

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

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.