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
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 𝔇.
- 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.
From the original article
1 min read at arxiv.orgWe 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.
By Aarush Kulkarni · arxiv.org
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.