Adaptive Maximin Learning with Intermittent Opponent Observations

We study an unknown zero-sum matrix game against an adaptive opponent, with $m$ learner actions, $n$ opponent actions, and $T$ rounds. Rewards are always observed; opponent actions are independently revealed with unknown probability $q\in [0,1]$. The benchmark is the best mean payoff a fixed action can guarantee against every opponent action. Regret is the expected sum of this value minus the mean payoff of each chosen action pair. A base policy given only $m,n,T$ achieves worst-case regret $O(\sqrt{mT\log (mnT)})$ and two gap-dependent logarithmic bounds. One uses revealed actions and scales as $1/q$ for $q>0$. The other holds with the same constant for every $q$ at a strict pure saddle, a pair of actions that are unique best responses to each other. On a family with tied opponent best responses, the revealed-action bound has a matching fixed-instance lower bound for policies with logarithmic worst-case regret on every fixed matrix at every fixed $q>0$. An enhanced policy combines row-reward estimates with revealed-action frequencies. It uses the same inputs, preserves the base guarantees, and attains $q^{-1/2}$ dependence on a different two-row family for $q>0$.