Back to AI News
arxiv

Introduced Feedback Delays Yield Optimal √S and √K Regret in Adversarial MDPs

This arXiv paper studies regret minimization in episodic Adversarial Markov Decision Processes with unknown transitions and bandit feedback. It proposes a technique called introduced feedback delays, which estimates the Q-function of a changing policy using future episodes while still updating the policy, supported by Geometric Resampling with Rejection and visitation-probability thresholding. The approach achieves Õ(poly(H)√(SAK)) regret in tabular AMDPs, resolving a long-open √S gap, and Õ(poly(d,H)√K) regret in linear AMDPs, described as the first efficient algorithm optimal in K. It also extends to delayed AMDPs with bounds optimal in S and total delay for tabular settings and in K and total delay for linear settings.

AI Brief

It provides a new general technique and theoretical guarantees that resolve open regret-minimization problems in adversarial reinforcement learning.

arXiv:2611.17214v1 Announce Type: cross 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 $\Omega(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).
Be the first to rate this article.

Comments & Questions (0)

Captcha
Please be respectful — let's keep the conversation friendly.

No comments yet

Be the first to comment!