TL;DR
This paper bridges a significant theoretical gap in reinforcement learning by introducing the first algorithms to achieve near-optimal regret bounds for adversarial Markov Decision Processes (MDPs) with delayed bandit feedback. By developing a novel "delay-adapted" importance sampling estimator, the authors improve the best-known regret bound from $(K + D)^{2/3}$ to the near-optimal $\sqrt{K + D}$, where $K$ is the number of episodes and $D$ is the total delay.
What Problem Does This Paper Address?
In standard reinforcement learning (RL) theory, we usually assume an agent receives feedback immediately after taking an action. In the real world—think robotics, autonomous vehicles, or personalized medicine—feedback is almost always delayed. A robot might not know if a maneuver was successful until seconds later; a medical treatment's effect might take weeks to observe.
The authors tackle a particularly difficult version of this problem: Adversarial MDPs with Delayed Bandit Feedback.
- Adversarial MDP: The costs associated with states and actions aren't fixed or stochastic; they can change arbitrarily (even maliciously) over time.
- Bandit Feedback: The agent only learns the costs of the specific path it traversed, not the costs of actions it didn't take.
- Unknown Transitions: The agent doesn't know the underlying physics/rules of the environment.
- Unrestricted Delay: Feedback for episode $k$ arrives at the end of episode $k + d^k$, where the delay $d^k$ can change and is chosen by an adversary.
Previous research either assumed full-information feedback (seeing all costs) or settled for sub-optimal regret bounds. This paper aims for efficiency and optimality simultaneously.
Methods
The authors propose three distinct approaches, moving from a theoretical "warm-up" to a practical, efficient solution:
- Delayed Hedge: An inefficient algorithm that treats every possible deterministic policy as a separate "arm" in a multi-armed bandit problem. While computationally impossible for large MDPs, it proved that a regret bound of $\sqrt{K + D}$ was theoretically attainable.
- Delayed UOB-FTRL: An efficient algorithm based on the Follow-the-Regularized-Leader (FTRL) framework. It uses standard loss estimators but requires a novel analysis to handle how delays interact with occupancy measures (the probability of being in a certain state-action pair).
- Delayed UOB-REPS (The Flagship): This is the primary contribution. It utilizes Online Mirror Descent (OMD) and introduces a delay-adapted importance sampling estimator.
The core innovation in Delayed UOB-REPS (shown in the algorithm below) is how it constructs its cost estimator $\hat{c}^k$. Standard estimators divide the observed cost by the probability of reaching that state. However, delays cause a "drift" between the policy used to collect data and the policy being updated. The authors solve this by re-weighting the cost using the maximum of the occupancy bounds from both the current and future episodes.
Datasets
Not discussed in the paper. This is a theoretical work focused on proving mathematical regret bounds and algorithmic complexity rather than empirical benchmarking on specific datasets.
Key Insights and Ideas
- The Stability-Drift Trade-off: In delayed settings, the main challenge is "stability." If the algorithm changes its policy too much before feedback arrives, the feedback becomes irrelevant or misleading. The authors show that standard estimators fail to control this "drift" efficiently in MDPs.
- The "Max" Trick: By using $\max\{u_h^k, u_h^{k+d^k}\}$ in the denominator of the cost estimator, the authors cleverly balance bias and variance. This ensures that the estimator doesn't explode when the policy shifts, which is the key to achieving the $\sqrt{D}$ dependency.
- Convex Conjugate Analysis: The proof for the FTRL-based algorithm relies on a sophisticated analysis of convex conjugate functions to bound the regret caused specifically by delays, overcoming the complex dependencies between states that don't exist in simpler multi-armed bandit problems.
Key Results
The paper’s results are best summarized by the significant improvement in regret bounds compared to prior work, as shown in Table 1.
- Near-Optimality: The flagship algorithm, Delayed UOB-REPS, achieves a regret bound of $\tilde{O}(H^2S\sqrt{AK} + (HSA)^{1/4} \cdot H\sqrt{D})$.
- Major Improvement: This is a massive leap over the previous state-of-the-art, D-OPPO, which had a regret scaling with $(K+D)^{2/3}$.
- Efficiency: Unlike the "Hedge" approach, both UOB-FTRL and UOB-REPS are computationally efficient, meaning they can be run in polynomial time relative to the number of states and actions.
Limitations and Future Work
- The $(HSA)^{1/4}$ Gap: There is still a small gap between the upper bound achieved in this paper and the theoretical lower bound $\Omega(H\sqrt{D})$. Closing this gap remains an open challenge.
- Policy Optimization (PO) Methods: The current algorithms are based on the O-REPS framework. The authors note that achieving similar near-optimal results using Policy Optimization methods (which are more common in deep RL practice) is an important next step.
- Dependency on $d_{max}$: In the case of unknown dynamics, one version of their algorithm has a regret term that scales linearly with the maximum delay ($d_{max}$), though they suggest "skipping" techniques can mitigate this at a slight cost to the overall bound.
Summary updated