Solving Stochastic Minimax Bandit Games

Minimax regret is the smallest worst-case regret achievable by an online learning algorithm. At a fixed horizon, this objective provides a computational route to algorithm design: optimizing the complete history-dependent policy offline. The resulting optimization has a natural two-player zero-sum structure, with the learner minimizing regret and the environment choosing hidden reward parameters to maximize it. We develop an approximate policy-space solver for these stochastic minimax bandit games. Each iteration plans a learner response to an environment mixture, evaluates the complete policy, and updates both players' mixtures. Grid interpolation and point-based value iteration represent finite-horizon costs in sufficient statistics. Shared two-arm costs avoid a joint state grid, while policy evaluation and mixture selection retain the original multi-arm objective. The resulting policy mixture defines an online learning algorithm that adapts its actions to observed rewards. In four exactly evaluable three-arm games, complete iterations reduce strategy-pair gaps from 0.115–0.349 to 0.001–0.016. Larger-horizon experiments cover 60 settings and track regret against tuned references over training time. Independent evaluation quantifies uncertainty in their regret differences. Response controls distinguish belief resolution from pair-prior capacity; complete runs confirm that larger priors improve regret in one Beta setting. The resulting framework uses offline game solving to design adaptive online exploration policies.