Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal $\sqrt S$ and $\sqrt K$ Dependencies in Tabular and Linear AMDPs
Deliberately delaying feedback lets the algorithms use future episodes to evaluate a policy while continuing to update it, without extra regret cost.
The paper studies adversarial Markov decision processes with unknown transitions and bandit feedback. Its method corrects for policy changes during the introduced delay and limits delays for rarely visited state-action pairs. The authors prove regret bounds that close the longstanding state-count gap in tabular models and give the first computationally efficient linear-model algorithm with optimal √K dependence, without a simulator or exploratory assumptions. The guarantees retain polynomial dependence on the episode horizon and, for linear models, feature dimension.
ArXiv · AI/CL/LG's note
The paper studies adversarial Markov decision processes with unknown transitions and bandit feedback. Its method corrects for policy changes during the introduced delay and limits delays for rarely visited state-action pairs. The authors prove regret bounds that close the longstanding state-count gap in tabular models and give the first computationally efficient linear-model algorithm with optimal √K dependence, without a simulator or exploratory assumptions. The guarantees retain polynomial dependence on the episode horizon and, for linear models, feature dimension.
ArXiv · AI/CL/LG's note
score 5