Research
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.
Adversarial Markov Decision ProcessesRegret minimizationReinforcement learning theory