Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of sequential decision-making in partially observable environments against adaptive opponents by analyzing partially observable Markov games (POMGs). The authors introduce an epoch-based optimistic maximum-likelihood algorithm that achieves a minimax-optimal policy regret of $\tilde{O}(\sqrt{T})$, demonstrating explicit dependencies on key factors such as horizon length and adversary memory. Additionally, they establish a matching lower bound for the regret, reinforcing the algorithm's efficiency and extending the framework to include horizon-adaptive guarantees.
Achieving minimax-optimal policy regret in partially observable environments could redefine strategies for adaptive adversarial decision-making.
We study sequential decision-making in partially observable environments against strategic, adaptive opponents, modeled as partially observable Markov games (POMGs). The central challenge is to learn latent dynamics from partial observations while facing an adversary whose behavior depends on the learner's strategy, making standard regret notions inadequate. We prove that an epoch-based optimistic maximum-likelihood algorithm achieves $\tilde{O}(\sqrt{T})$ policy regret for fixed problem parameters, with explicit dependence on the horizon, adversary memory, confidence radius, and the aggregate Eluder dimension of the observable-operator class. The algorithm selects one policy per geometrically growing epoch using confidence sets built cumulatively from past data, which keeps the cost of comparing adversary responses across policies logarithmic in $T$. We also prove a lower bound matching the $\sqrt{T}$ and aggregate-Eluder-dimension dependence, up to problem-dependent and logarithmic factors. Finally, we extend the framework to horizon-adaptive guarantees and adversaries with geometric fading memory.