Minimax-Optimal Policy Regret in Partially Observable Markov Games

Technical Summary: Minimax-Optimal Policy Regret in Partially Observable Markov Games

Problem Formulation
This paper addresses sequential decision-making in partially observable environments against strategic, adaptive opponents, modeled as Partially Observable Markov Games (POMGs). The core challenge lies in learning latent world dynamics from partial observations while facing an adversary whose behavior adapts to the learner's strategy. Standard external regret notions are inadequate in this setting because the environment's response depends on the learner's past actions, creating counterfactual dependencies. Consequently, the paper adopts policy regret as the performance metric, which compares the learner's cumulative reward against the best fixed policy $\pi^*$, assuming the adversary would have eventually converged to a stationary response $R_\infty(\pi^*)$ had the learner committed to $\pi^*$ from the start.

The setting involves two players: a learner and an adversary, both operating under partial observability. The learner observes signals $o^A$ and the adversary observes $o^B$, while the latent state transitions based on both players' actions. The adversary is assumed to be $m$-memory bounded, meaning its response at any episode depends only on the learner's policies from the most recent $m$ episodes.

Methodology and Algorithmic Framework
The authors propose an epoch-based optimistic Maximum Likelihood Estimation (MLE) algorithm (Algorithm 1) to minimize policy regret. The methodology relies on several key structural components:

1. Causal Decomposition: A central theoretical contribution is the decomposition of the observable operator $J_{\xi,\pi}^h$ into two distinct components:

   • A world channel $W_h^\theta$, which depends solely on the world dynamics (transition and emission kernels) and is independent of the adversary's response model.
   • An adversary aggregation operator $G_{\Phi,\pi}^h$, which depends on the adversary's response function and the learner's policy but is independent of the world parameter $\theta$.
     This factorization allows the algorithm to separate the estimation of world dynamics from the control of adversary responses.

2. Structural Assumptions:

   • Posterior-Lipschitz Adversary: The adversary's response varies smoothly with the learner's policy. Crucially, this smoothness is defined relative to a fixed reference measure $\mu_{ref}$ (independent of the adversary's actual strategy) to avoid circular dependencies in the definition.
   • Multi-step Weak Revealing: Observations are sufficiently informative about latent states over a window of $\kappa$ steps, ensuring that discrepancies in world dynamics are detectable.
   • Eluder Dimension: The complexity of the joint world-adversary model class is measured by the uniform aggregate Eluder dimension ($d_E$).

3. Epoch-Based Execution: The algorithm divides time into geometrically growing epochs ($T_e = 2^e$). Within each epoch:

   • A single policy $\pi_e$ is selected optimistically from a confidence set constructed cumulatively from all past data.
   • A warm-up phase ($m-1$ episodes) allows the $m$-memory adversary to stabilize to its stationary response for the current policy.
   • The policy is executed for $T_e$ data-collection episodes.
     This structure ensures that the learner deploys only $O(\log T)$ distinct policies over $T$ episodes, which is critical for controlling the cost of comparing adversary responses across different policies.

Key Results
The paper establishes a minimax-optimal upper bound on policy regret and a matching lower bound.

• Upper Bound: Under the stated assumptions, the algorithm achieves a policy regret of:
  $$PR(T) \leq C \left( H \sqrt{\bar{\beta}_T \cdot d_E \cdot T} + mH \log T \right)$$
  where $\bar{\beta}_T = H\beta_T + H^2 \log T$. The term $H^2 \log T$ represents the "transport cost" of comparing adversary responses across the $O(\log T)$ distinct policies deployed. The $\sqrt{T}$ dependence is achieved by the geometric epoch structure; deploying $O(\sqrt{T})$ policies (as in flat batching) would result in a $T^{3/4}$ regret rate due to the accumulation of transport costs.

• Lower Bound: The authors prove a lower bound of $\Omega(\sqrt{d_E T})$ for any algorithm, even in fully revealing POMGs with memoryless adversaries. This confirms that the $\sqrt{T}$ and $d_E$ dependence in the upper bound is optimal up to problem-dependent and logarithmic factors.

• Extensions: The framework is extended to handle:

  • Unknown Horizons: The algorithm adapts to unknown $T$ without modification.
  • Fading Memory Adversaries: The results hold for adversaries with geometrically decaying memory, with the warm-up cost scaling as $O(\frac{H \log^2 T}{1-\gamma})$.
  • Tabular Settings: Explicit bounds are derived in terms of state, action, and observation space sizes.

Significance and Claims
The paper claims to provide a complete theoretical treatment of policy regret minimization in POMGs against adaptive adversaries. Its primary significance lies in demonstrating that efficient learning (with $\sqrt{T}$ regret) is possible in this complex setting, provided the adversary's response is smooth (Posterior-Lipschitz) and observations are weakly revealing.

The authors highlight two specific technical innovations that enable this result:

1. Non-circular Formulation: By defining the Posterior-Lipschitz condition relative to a fixed reference measure, they avoid the circularity issues present in prior formulations where the smoothness metric depended on the adversary being constrained.
2. Logarithmic Transport Cost: By restricting the learner to $O(\log T)$ distinct policies via the epoch-based structure, they ensure the cost of transporting adversary-response errors remains logarithmic, preserving the optimal $\sqrt{T}$ rate. This contrasts with flat-batching approaches which, the authors argue, lead to suboptimal $T^{3/4}$ rates due to polynomial growth in transport costs.

The work is presented as a foundational step for designing learning algorithms with reliable performance guarantees in multi-agent environments where agents are both partially observable and strategically adaptive. The authors note that while the statistical guarantees are established, the computational tractability of the optimistic planning step remains an open direction for future work, particularly for general model classes.