Minimax-Optimal Policy Regret in Partially Observable Markov Games

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.

Machine learning systems are increasingly used in settings where other participants adapt to what the system does. For example, a trading algorithm, recommendation system, or autonomous agent may influence the behavior of people or other agents around it. This makes learning harder than in standard settings, because trying a strategy today can change the environment the learner faces tomorrow. The challenge becomes even greater when the learner cannot directly observe the full state of the system. We study how to learn in such partially hidden, adaptive environments. The key difficulty is that ordinary measures of learning performance can be misleading as they compare the learner to an alternative strategy while pretending the opponent would have behaved the same way. In adaptive settings, this is not true. A different learner strategy would have induced a different opponent response. We therefore use policy regret, a counterfactual notion that compares what actually happened to what would have happened had the learner committed to another strategy from the beginning. We prove that reliable learning is possible under natural smoothness and memory assumptions on the opponent. Our algorithm achieves the best possible dependence on the number of learning episodes, and we show that no algorithm can substantially improve this rate in general. We also extend the analysis to opponents with long but fading memory and to settings where the total number of learning episodes is not known in advance.