Dynamic Thresholding and Pruning for Regret Minimization

By Noam Brown, Christian Kroer, Tuomas Sandholm. 2017

54 citations recorded by the source corpus.

Regret minimization is widely used in determining strategies for imperfect-information games and in online learning. In large games, computing the regrets associated with a single iteration can be slow. For this reason, pruning — in which parts of the decision tree are not traversed in every iteration — has emerged as an essential method for speeding up iterations in large games. The ability to prune is a primary reason why the Counterfactual Regret Minimization (CFR) algorithm using regret matching has emerged as the most popular iterative algorithm for imperfect-information games, despite its relatively poor convergence bound. In this paper, we introduce dynamic thresholding, in which a threshold is set at every iteration such that any action in the decision tree with probability below the threshold is set to zero probability. This enables pruning for the first time in a wide range of algorithms. We prove that dynamic thresholding can be applied to Hedge while increasing its convergence bound by only a constant factor in terms of number of iterations. Experiments demonstrate a substantial improvement in performance for Hedge as well as the excessive gap technique.

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “It has revolutionized Poker AI research [58, 60], leading to the largest variants of poker being solved and competitive polices that have beat top human professionals [10, 45, 13, 15].”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “For example, [281, 282, 283, 284, 285, 286] combine CFR with Monte-Carlo sampling; [287, 288, 289] propose to estimate the counterfactual value functions via regression; [290, 291, 292] improve the computational efficiency by pruning suboptimal paths in the game tree; [293, 294, 295] analyze the per”
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, unknown): “regret-matching [28] or exponentially-weighted experts [6, 15].”