Skip to content
NewA calmer, faster ZeroHour

Voluntary feedback delays close a regret gap in adversarial MDPs

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

arXiv cs.AI / cs.LG / cs.CLby Aarush Kulkarni ()1 min read
AI summary · x-ai/grok-4.7Summaries by Vani AI

The method also yields the first efficient linear AMDP algorithm with regret optimal in the number of episodes K.

The paper studies episodic adversarial MDPs with unknown transitions and bandit feedback. It voluntarily delays Q-function estimates using future episodes while still updating the policy, using Geometric Resampling with Rejection and visitation thresholds. With high probability the algorithms reach Õ(poly(H)√(SAK)) regret in tabular AMDPs, matching the √S lower-bound order, and Õ(poly(d,H)√K) in linear AMDPs. The same technique extends to AMDPs with a total feedback delay 𝔇.

Key facts
  • Prior tabular regret was Õ(HS√(AK)), short of Ω(H√(SAK)) by a √S factor.
  • Efficient linear AMDPs previously reached only Õ(K^{3/4}) without a simulator.
  • Bounds are also optimal in S and 𝔇 tabular, and in K and 𝔇 linear.
Explain this AI news with Vani AIWhat was announced, what is new and why it matters, in a new chat

From the original article

1 min read at arxiv.org

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.

arXiv cs.AI / cs.LG / cs.CL

By Aarush Kulkarni · arxiv.org

Read the full article at arXiv cs.AI / cs.LG / cs.CL

A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.