Abstract
The standard assumption in reinforcement learning (RL) is that agents observe feedback for their actions immediately. However, in practice, feedback is often delayed. This paper studies online learning in episodic Markov Decision Processes (MDPs) with unknown transitions, adversarially changing costs, and unrestricted delayed bandit feedback. We present the first algorithms that achieve near-optimal $\sqrt{K + D}$ regret, where $K$ is the number of episodes and $D = \sum_{k=1}^K d^k$ is the total delay. This significantly improves upon the previous best known regret bound of $(K + D)^{2/3}$.
Introduction
In real-world applications such as autonomous vehicles, high-frequency trading, and medical recommendation systems, feedback is rarely instantaneous. Agents must often make decisions based on stale information while waiting for the results of previous actions. This paper addresses a particularly challenging version of this problem characterized by unknown state transitions, costs that change arbitrarily over time (adversarial costs), and bandit feedback (only observing the cost of the chosen path). Furthermore, the delays are unrestricted and can be chosen by an adversary.
Methodology
The authors propose three distinct algorithmic approaches to bridge the efficiency gap in delayed RL:
- Delayed Hedge: An inefficient warm-up algorithm that treats every deterministic policy as a separate arm. It proves that a near-optimal $\sqrt{K+D}$ regret is theoretically possible, though it is computationally intractable.
- Delayed UOB-FTRL: An efficient algorithm based on the Follow-the-Regularized-Leader (FTRL) framework, which optimizes over occupancy measures to maintain computational feasibility.
- Delayed UOB-REPS with Delay-Adapted Estimator: The paper's primary contribution, utilizing Online Mirror Descent (OMD) and a novel cost estimation strategy.
The core innovation is the delay-adapted importance sampling estimator. Standard estimators can become unstable when feedback is delayed. The authors introduce a biased estimator that re-weights costs using the maximum of occupancy bounds from two different time points: when the action was taken and when the feedback arrived. This specific bias cancels out the mathematical instability caused by delays, effectively balancing the trade-off between algorithm stability and drift.
Key Results
The paper's main achievement is the dramatic improvement of the regret bound, matching the theoretical lower bound for delays up to a small factor.
As shown in the comparison table, Delayed UOB-REPS is the first algorithm to be both computationally efficient and achieve near-optimal regret with high probability. The regret bound is improved to $\tilde{O}(H^2 S \sqrt{AK} + (HSA)^{1/4} H \sqrt{D})$, where $H$ is the horizon, $S$ is the number of states, and $A$ is the number of actions. The $\sqrt{K}$ term matches the best results for non-delayed settings, while the $\sqrt{D}$ term handles delays almost as well as mathematically possible.
Conclusion
This work provides a robust theoretical foundation for RL agents operating in environments where feedback is not instantaneous. By shifting the problem from policy selection to occupancy measure optimization and introducing a novel biased estimator, the authors close a significant gap in the literature. Future work may focus on closing the remaining $(HSA)^{1/4}$ gap and extending these near-optimal bounds to popular Policy Optimization (PO) frameworks.
Summary updated