Efficient Minimax Strategies for Square Loss Games
We consider online prediction problems where the loss between the prediction and the outcome is measured by the squared Euclidean distance and its generalization, the squared Mahalanobis distance. We derive the minimax solutions for the case where the prediction and action spaces are the simplex (this setup is sometimes called the Brier game) and the $\ell_2$ ball (this setup is related to Gaussian density estimation). We show that in both cases the value of each sub-game is a quadratic function of a simple statistic of the state, with coefficients that can be efficiently computed using an explicit recurrence relation. The resulting deterministic minimax strategy and randomized maximin strategy are linear functions of the statistic.
Code (0)
등록된 구현이 없습니다.
Tasks
Density EstimationPredictionSimilar Papers 제목 키워드 기반
Decoupled SGDA for Games with Intermittent Strategy Communication
We focus on reducing communication overhead in multiplayer games, where frequently exchanging strategies between players is not feasible and players have noisy or outdated strategies of the other players. We introduce De…
Can Meta-Interpretive Learning outperform Deep Reinforcement Learning of Evaluable Game strategies?
World-class human players have been outperformed in a number of complex two person games (Go, Chess, Checkers) by Deep Reinforcement Learning systems. However, owing to tractability considerations minimax regret of a lea…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)+1Deep Learning Across Games
We train two neural networks adversarially to play static games. At each iteration, a row and column network observe a new random bimatrix game and output individual mixed strategies. The parameters of each network are i…
Deep LearningStatistical Games
This work contains the mathematical exploration of a few prototypical games in which central concepts from statistics and probability theory naturally emerge. The first two kinds of games are termed Fisher and Bayesian g…
Decision MakingPredicting The Performance of Minimax and Product in Game-Tree
The discovery that the minimax decision rule performs poorly in some games has sparked interest in possible alternatives to minimax. Until recently, the only games in which minimax was known to perform poorly were games …