# Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games

arXiv: https://arxiv.org/abs/2103.04539 · HTML: https://mlsanity.com/paper/2103.04539/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 71 references that are in the map.
- First posted on arXiv 8 Mar 2021.

## Builds on (most cited first, 14 of 14)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Deep Reinforcement Learning from Self-Play in Imperfect-Information Games](https://mlsanity.com/paper/1603.01121/) (2016)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Actor-Critic Policy Optimization in Partially Observable Multiagent Environments](https://mlsanity.com/paper/1810.09026/) (2018)
- [What game are we playing? End-to-end learning in normal and extensive form games](https://mlsanity.com/paper/1805.02777/) (2018)
- [Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games](https://mlsanity.com/paper/1809.03075/) (2018)
- [Stochastic Regret Minimization in Extensive-Form Games](https://mlsanity.com/paper/2002.08493/) (2020)
- [Learning to Correlate in Multi-Player General-Sum Sequential Games](https://mlsanity.com/paper/1910.06228/) (2019)
- [Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling](https://mlsanity.com/paper/1401.4591/) (2014)
- [Combining No-regret and Q-learning](https://mlsanity.com/paper/1910.03094/) (2019)

## Built on by (most cited first, 12 of 12)

- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall](https://mlsanity.com/paper/2106.06279/) (2021)
- [Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits](https://mlsanity.com/paper/2203.06803/) (2022)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Automated Security Response through Online Learning with Adaptive Conjectures](https://mlsanity.com/paper/2402.12499/) (2024)
- [Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games](https://mlsanity.com/paper/2205.07223/) (2022)
- [A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence](https://mlsanity.com/paper/2408.00751/) (2024)
- [Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game](https://mlsanity.com/paper/2203.05920/) (2022)
- [Deep (Predictive) Discounted Counterfactual Regret Minimization](https://mlsanity.com/paper/2511.08174/) (2025)
- [On-line Learning in Tree MDPs by Treating Policies as Bandit Arms](https://mlsanity.com/paper/2605.04979/) (2026)
- [Once-for-All: Scalable Simultaneous Forecasting via Equilibrium State Estimation](https://mlsanity.com/paper/2606.13285/) (2026)

## Abstract (arXiv)

Regret minimization has proved to be a versatile tool for tree-form sequential decision making and extensive-form games. In large two-player zero-sum imperfect-information games, modern extensions of counterfactual regret minimization (CFR) are currently the practical state of the art for computing a Nash equilibrium. Most regret-minimization algorithms for tree-form sequential decision making, including CFR, require (i) an exact model of the player's decision nodes, observation nodes, and how they are linked, and (ii) full knowledge, at all times t, about the payoffs -- even in parts of the decision space that are not encountered at time t. Recently, there has been growing interest towards relaxing some of those restrictions and making regret minimization applicable to settings for which reinforcement learning methods have traditionally been used -- for example, those in which only black-box access to the environment is available. We give the first, to our knowledge, regret-minimization algorithm that guarantees sublinear regret with high probability even when requirement (i) -- and thus also (ii) -- is dropped. We formalize an online learning setting in which the strategy space is not known to the agent and gets revealed incrementally whenever the agent encounters new decision points. We give an efficient algorithm that achieves O(T3/4) regret with high probability for that setting, even when the agent faces an adversarial environment. Our experiments show it significantly outperforms the prior algorithms for the problem, which do not have such guarantees. It can be used in any application for which regret minimization is useful: approximating Nash equilibrium or quantal response equilibrium, approximating coarse correlated equilibrium in multi-player games, learning a best response, learning safe opponent exploitation, and online play against an unknown opponent/environment.