This paper presents a counterintuitive breakthrough in Reinforcement Learning (RL): to achieve optimal performance in complex, changing environments, you should sometimes act as if your feedback is arriving late—even when it isn't.
TL;DR
The authors resolve long-standing open problems in Adversarial Markov Decision Processes (AMDPs) by voluntarily introducing feedback delays. By combining "introduced delays" with a novel rejection sampling technique, they achieve the first computationally efficient, optimal regret bounds for both tabular and linear AMDPs with unknown transitions and bandit feedback.
What Problem Does This Paper Address?
In an Adversarial MDP (AMDP), an agent interacts with an environment where the rewards (or losses) are chosen by an adversary, and the underlying transition rules are unknown. The agent only receives "bandit feedback," meaning they only see the loss for the specific path they took, not what would have happened if they had chosen differently.
The goal is to minimize regret: the difference between the agent's total loss and the loss of the best fixed policy in hindsight.
Two major gaps have persisted in this field:
- The Tabular Gap: For environments with $S$ states, there was a $\sqrt{S}$ gap between the best known algorithms and the theoretical lower bound.
- The Linear Gap: In environments with high-dimensional features ($d$), efficient algorithms could only achieve $K^{3/4}$ regret (where $K$ is the number of episodes), while the theoretical optimum is $\sqrt{K}$.
The core difficulty is estimating the "value" (Q-function) of a policy that is constantly changing. Using past data is problematic because old policies might not visit the same states as the current one. Conversely, "freezing" the policy to collect fresh data for many episodes makes the algorithm too slow to adapt to the adversary.
Methods
The authors propose a paradigm shift: Introduced Feedback Delays. Instead of relying on the past or freezing the future, they estimate the current policy's performance using data from future episodes while continuing to update the policy in every single episode.
To make this work, they introduce two key technical components:
- Geometric Resampling with Rejection (GRR): Since future episodes use different policies, their trajectories aren't directly representative of the current policy. The authors use rejection sampling to "filter" future trajectories so they statistically match the current policy. This allows them to estimate the inverse visitation probabilities ($1/q$) without stopping the learning process.
- Thresholding: GRR can take a very long time to "succeed" for states that are rarely visited. To prevent infinite delays, the authors set a threshold. If a state is too rare, they skip the estimation and instead use a large "exploration bonus" to encourage the agent to visit it more often in the future.
For the linear setting, they extend this to Matrix Geometric Resampling with Rejection (MGRR), which estimates the inverse covariance matrix of the features.
Datasets
The paper is purely theoretical and does not use empirical datasets or benchmarks. The results are proven mathematically for the general classes of tabular and linear AMDPs.
Key Insights and Ideas
- Delays as a Tool: Usually, feedback delay is seen as a hurdle. Here, it is a voluntary design choice that decouples policy updates from policy evaluation, surprisingly coming at "no extra cost" to the total regret.
- Rejection Sampling for Policy Evaluation: The insight that the likelihood ratio between two policies on a trajectory can be computed without knowing the environment's transition probabilities is what makes GRR possible.
- Closing the Gap: By avoiding the "optimism" or "epoching" used in prior work, the authors remove the extra $\sqrt{S}$ and $K^{1/4}$ factors that plagued previous bounds.
Key Results
The authors provide high-probability regret bounds that match or significantly improve upon the state-of-the-art, as summarized in Table 1:
- Tabular AMDPs: Achieved $\tilde{O}(\text{poly}(H)\sqrt{SAK})$ regret, finally matching the $\sqrt{S}$ dependency of the lower bound and answering a six-year-old open problem.
- Linear AMDPs: Provided the first computationally efficient algorithm to achieve $\sqrt{K}$ regret, closing a five-year gap in efficiency.
- Delayed Environments: Their analysis naturally extends to environments that already have feedback delays ($\mathfrak{D}$), providing the first bounds that are optimal in both the environment parameters ($S, K$) and the total delay ($\mathfrak{D}$).
Limitations and Future Work
- Horizon Dependency ($H$): While the scaling with states and episodes is optimal, the dependency on the episode length (horizon $H$) is currently $H^{5/2}$ or $H^4$, which is larger than the theoretical lower bound of $H^1$. Optimizing this remains an open challenge.
- Feature Dimension ($d$): In the linear case, the regret scales with $d^3$. The authors suggest that more sample-efficient ways to normalize features could potentially reduce this to $d^1$.
- Broader Applications: The "introduced delay" technique requires policies to change slowly. The authors believe this could be applied to other complex settings, such as Multi-Agent Reinforcement Learning (MARL), where evaluating a changing joint policy is a major bottleneck.
Summary updated