Online Learning in Adversarial MDPs: Is the Communicating Case Harder than Ergodic?

Gautam Chandrasekaran, Ambuj Tewari

Introduction

In the field of online reinforcement learning, a fundamental question has persisted: does the structural complexity of an environment necessarily degrade the performance of learning algorithms? Specifically, researchers have long debated whether "communicating" Markov Decision Processes (MDPs)—where any state is reachable from any other—are inherently more difficult to solve than the more restrictive "ergodic" MDPs.

In adversarial MDPs, where transitions are Markovian but rewards are chosen by an adversary, previous results in the bandit feedback setting suggested a statistical penalty for the communicating property. This paper addresses this gap in the full-information setting, demonstrating that the communicating case is not, in fact, harder than the ergodic case.

The Challenge of Communication

Most early research focused on ergodic MDPs, where every policy eventually converges to the same steady-state distribution. While mathematically convenient, this assumption is often too restrictive for real-world applications. Communicating MDPs offer a more realistic framework but introduce significant synchronization challenges.

In the bandit feedback setting, regret scales as $T^{2/3}$ or $T^{3/4}$ for communicating MDPs, compared to $\sqrt{T}$ for ergodic ones. This led to the hypothesis that a similar gap might exist under full-information feedback. This work proves this hypothesis wrong by establishing an $O(\sqrt{T})$ regret bound for the communicating case.

Algorithmic Framework

The authors propose a two-stage approach to close the performance gap:

1. Adversarial Deterministic MDPs (ADMDPs)

For environments with deterministic transitions, the problem is reduced to "prediction with expert advice." By observing that deterministic stationary policies eventually settle into cycles, the authors treat these cycles as experts. They employ a Follow the Perturbed Leader (FPL) style algorithm. To manage the "switching cost" of moving between cycles, they utilize graph-theoretic properties to identify paths of "critical length," ensuring the agent stays synchronized with the expert policy.

2. General Communicating MDPs

For stochastic transitions, the challenge shifts to state distribution alignment. When switching policies, the agent's current state may not match the distribution the new policy expects. The authors introduce a "Catching a Policy" routine. By assuming a "do-nothing" action (a state with a deterministic self-loop), they use a randomized stopping time to ensure the agent's state distribution exactly matches the target policy's distribution upon termination, effectively resetting any delay caused by the switch.

Key Results and Statistical Equivalence

The central finding of this research is that there is no statistical price for communication in the full-information setting. Both ergodic and communicating MDPs achieve the optimal $O(\sqrt{T})$ regret scaling.

Comparison of regret bounds across different MDP settings and feedback models.

The table above highlights how this work completes the landscape of regret bounds. While the bandit setting shows a clear divergence between ergodic and communicating cases, this paper proves their equivalence under full information.

Specific bounds achieved include:

  • Deterministic Case: $O(|S|^3 \cdot \gamma \sqrt{T \log |S||A|})$ regret, where $\gamma$ is the MDP's period.
  • General Case: $O(D^2 \sqrt{T |S| \log |A|})$ regret, where $D$ is the diameter of the MDP.

Discussion and Future Directions

While this work settles the statistical question, it opens new computational ones. The algorithm for deterministic MDPs is efficient, but the general stochastic algorithm is computationally inefficient, requiring time exponential in the number of states $|S|$. Furthermore, the reliance on a "do-nothing" action remains a constraint that future research might aim to relax. Finding a computationally efficient algorithm for the general communicating case remains one of the most significant open challenges in adversarial MDPs.

Summary updated

BibTeX
@inproceedings{chandrasekaran2023online,
  author = {Gautam Chandrasekaran and Ambuj Tewari},
  title = {{Online Learning in Adversarial MDPs: Is the Communicating Case Harder than Ergodic?}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=X4eqYLH8Vb},
}
Figure