Variance Reduction In Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) For Extensive Form Games Using Baselines
2018 · Martin Schmid, Neil Burch, Marc Lanctot, et al.
Abstract
Learning strategies for imperfect information games from samples of interaction is a challenging problem. A common method for this setting, Monte Carlo Counterfactual Regret Minimization (MCCFR), can have slow long-term convergence rates due to high variance. In this paper, we introduce a variance reduction technique (VR-MCCFR) that applies to any sampling variant of MCCFR. Using this technique, per-iteration estimated values and updates are reformulated as a function of sampled values and state-action baselines, similar to their use in policy gradient reinforcement learning. The new formulation allows estimates to be bootstrapped from other estimates within the same episode, propagating the benefits of baselines along the sampled trajectory; the estimates remain unbiased even when bootstrapping from other estimates. Finally, we show that given a perfect baseline, the variance of the value estimates can be reduced to zero. Experimental evaluation shows that VR-MCCFR brings an order of
Authors
(none)
Tags
Stats
Related papers
- Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
- DREAM: Deep Regret Minimization With Advantage Baselines And Model-free Learning (2020)0.00
- Generalized Bandit Regret Minimizer Framework In Imperfect Information Extensive-form Game (2022)0.00
- Model-free Online Learning In Unknown Sequential Decision Making Problems And Games (2021)5.24
- Variance Reduction For Score Functions Using Optimal Baselines (2022)0.00
- Alternative Function Approximation Parameterizations For Solving Games: An Analysis Of \(f\)-regression Counterfactual Regret Minimization (2019)2.26
- Sharp Variance-dependent Bounds In Reinforcement Learning: Best Of Both Worlds In Stochastic And Deterministic Environments (2023)0.00
- Combining No-regret And Q-learning (2019)0.00