# Combining Counterfactual Regret Minimization with Information Gain to Solve
Extensive Games with Imperfect Information

Chen Qiu, Xuan Wang, Tianzi Ma, Yaojun Wen, Jiajia Zhang
Corresponding author.

###### Abstract

Counterfactual regret Minimization (CFR) is an effective algorithm for solving
extensive games with imperfect information (IIEG). However, CFR is only
allowed to apply in a known environment such as the transition functions of
the chance player and reward functions of the terminal nodes are aware in
IIEGs. For uncertain scenarios like the cases under Reinforcement Learning
(RL), variational information maximizing exploration (VIME) provides a useful
framework for exploring environments using information gain. In this paper, we
propose a method named VCFR that combines CFR with information gain to
calculate Nash Equilibrium (NE) in the scenario of IIEG under RL. By adding
information gain to the reward, the average strategy calculated by CFR can be
directly used as an interactive strategy, and the exploration efficiency of
the algorithm to uncertain environments has been significantly improved.
Experimentally, The results demonstrate that this approach can not only
effectively reduce the number of interactions with the environment, but also
find an approximate NE.

## Introduction

Counterfactual regret minimization (CFR) (Zinkevich et al. 2007; Gibson et al.
2012; Brown and Sandholm 2018) is widely used in the benchmark field of the
extensive-form game with imperfect information (IIEG)(Osborne and Rubinstein
1994), since it can converge to equilibrium and gain an average strategy
through iterations. But in fact, CFR needs much necessary information for
calculation to work. In contrast, Reinforcement Learning (RL)(Sutton and Barto
2018) algorithms provide a series of useful frameworks for making decisions in
an uncertain environment. Agents constantly interact with the environment to
obtain information and improve the game strategies in the end. The advantage
of RL methods is that the agents can improve by themselves via setting reward
function, but it is easy to make the agents fall into the local optimal state.
Therefore, how to use CFR in IIEG under RL for finding a Nash equilibrium (NE)
(Nash et al. 1950; Roughgarden 2010), and design an effective exploration
strategy to minimize interactions with the environment are important
challenges.

More specifically, we focus on the RL problems in two-player zero-sum
extensive games with imperfect information (TEGI). Previous work in an
algorithm called PSRLCFR (Zhou, Li, and Zhu 2020) has also investigated the
same problem. PSRLCFR uses Thompson Sampling to model the environment, and
achieving the goal of closing the gap between the sampled and real
environments via exploring in the direction of the greatest difference between
the two sampled environments. However, the efficiency of this exploration
method is not good enough. Because the variance of single sampling is large
and cannot represent the real environmental distribution.

We use another approach to improve the efficiency of exploration and speed up
convergence. Variational information maximizing exploration (VIME) (Houthooft
et al. 2016) provides an effective framework for exploring an unknown
environment of RL. VIME proposes a curiosity-driven exploration strategy. In
the dynamic model, it takes the information gain obtained from the agent’s
internal belief as a driving force. The characteristic of this exploration
algorithm is that the information owned by the agent is regarded as part of
the state, and the agent hopes to obtain new information by traversing new
states.

Nevertheless, applying VIME to TEGI missions under unknown environments
requires interaction strategies that are to better interact with the
environment for collecting data. The goal of the agent is to maximize its
reward in a single-agent RL (SARL) (Neto 2005) problem, but the reward of an
agent is affected by the environment and the strategies of other agents. In
consequence, solving the TEGI is to find an approximate NE where none of the
players can increase reward by changing their strategies, and CFR can complete
this work when environmental information is available.

In this work, our contributions are summarized as follows:

  * •

We propose a framework named VCFR, which is composed of VIME and CFR. It
allows the CFR algorithm to be used rationally for solving the problem of TEGI
under RL.

  * •

VCFR indirectly changes the calculation of CFR by adding information gain to
the reward. It not only finds approximate Nash equilibria but also obtains
strategies that can be used directly in exploration to reduce the number of
interactions with the environment.

  * •

VCFR is a plug-and-play framework for solving IIEG in an unknown environment.
More specifically, CFR can be replaced by other algorithms used to solve
strategies, such as CFR+, DCFR, etc.

  * •

Experimental results show that VCFR outperforms other comparison methods, and
the number of interactions with environment is fewer than them.

## Notation and Background

This section briefly introduces the definition of two-player zero-sum
imperfect-information extensive game (TEGI) under Reinforcement Learning which
is the setting used in our experiment. In addition, we review related
techniques, namely variational information maximizing exploration (VIME) and
counterfactual regret minimization (CFR), which give us inspiration for a
solution.

### Problem Statement of Extensive Game

The extensive games with two players is a special case of general extensive
games with imperfect information which is usually used to model the sequential
decision-making game. Therefore, we first introduce the concept of extensive
games(for a full treatment, see (Osborne and Rubinstein 1994)).

There is a finite set A finite set $\mathcal{P}$ of players in an imperfect-
information extensive game, $\mathcal{P}=\\{1,2,\ldots,n\\}$. The “Nature” of
the game is chance player $\mathcal{C}$, which chooses actions with unknown
probability distribution under Reinforcement Learning. Here, we define $c^{*}$
as $\mathcal{C}$’s probability of strategies. A history(or state) $h$ denotes
all information of each player including chance player. $H$ is a finite set of
histories including the empty sequence $\emptyset$, and $h$ can be thought of
the finite set of all nodes in the game tree. $Z\subseteq H$ refers to the set
of terminal histories. The set of available actions after a non-terminal
history $h$ is referred to $A(h)=\\{a:(h,a)\in H\\}$. $\mathcal{P}(h)$ is the
player who takes an action after the history $h$. In particular, if
$\mathcal{P}(h)=\mathcal{C}$ then chance player chooses a action with a
probability after $h$. $\mathcal{I}_{i}$ of a history
$\mathcal{P}(h)\neq\mathcal{C}$ is an information partition of player $i$, and
player $i$ cannot distinguish $h_{1},h_{2}\in I_{i}$. The information
sets(infosets) of player $i$ is $I_{i}\in\mathcal{I}_{i}(h)$ when $i$ is at
state $h$. A strategy
$\sigma=\left\\{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}\right\\}$ is a set of
the strategy for all players. $\sigma_{i}\left(h_{1}\right)$ and
$\sigma_{i}\left(h_{2}\right)$ are equal for player $i$ when $h_{1},h_{2}\in
I_{i}$. For convenience, we let $\sigma_{-i}$ denote all the policies in
$\sigma$ except $\sigma_{i}$. Let $r^{*}$ denotes the reward function at
terminal state, i.e., $r^{*}(h,i)$ is the distribution of the reward of player
$i$. . The maximal size of available actions for $h$ is referred to
$\mathcal{A}=\max_{h}|A(h)|$.

$\pi^{\sigma}(h)=\Pi_{h^{\prime}\cdot a\sqsubseteq
h}\sigma_{P\left(h^{\prime}\right)}\left(h^{\prime},a\right)$ denotes the
probability of reaching $h$ when all players choose actions according to
$\sigma$. $d^{*}=(r^{*},c^{*})$ can be regarded as the unknown environment,
where $r^{*}$ and $c^{*}$ follow a prior distribution $\mathbf{D}$. Since
$c^{*}$ is uncertain under RL, the probability of reaching $h$ depends on
$\sigma$ and $c^{*}$. Defining by formal formula is $\pi_{\sigma}\left(h\mid
d^{*}\right)=\prod_{i\in[\mathcal{P}]\cup\\{\mathcal{C}\\}}\pi_{\sigma}^{i}\left(h\mid(r^{*},c^{*})\right)$.
Similarly, we use $v_{i}\left(h\mid\sigma,(r^{*},c^{*})\right)$ to refer to
the expected payoff for $i$ according to $\sigma$.

#### Nash Equilibrium.

Finding a approximate Nash Equilibrium (Nash et al. 1950; Roughgarden 2010) is
a significant solution to TEGI. The best response means the strategy
$BR(\sigma_{-i})$ that maximizes the reward of player $i$ when $\sigma_{-i}$
is given. That is,
$v_{i}(BR(\sigma_{-i}),\sigma_{-i})=\max_{\sigma_{i}^{\prime}}v_{i}(\sigma_{i}^{\prime},\sigma_{-i})$.
A Nash Equilibrium $\sigma^{*}$ is a policy where all players play a best
response: $\forall
p,v_{p}\left(\sigma_{p}^{*},\sigma_{-p}^{*}\right)=\max_{\sigma_{p}^{\prime}}v_{p}\left(\sigma_{p}^{\prime},\sigma_{-p}^{*}\right)$.
More specifically, Nash Equilibrium has been proven to exist in TEGI. The
exploitability is generally used to measure the approximation error of
$\sigma=(\sigma_{1},\sigma_{2})$:

$expl(\sigma_{i}\mid
d^{*})=\sum_{\sigma_{i=1,2}}\max_{\sigma^{*}_{i}}v^{i}\left(\sigma^{*}_{-i},\sigma_{-i}\mid
d^{*}\right)$ (1)

The total exploitability is denoted by
$\sum_{i\in\mathcal{P}}expl\left(\sigma_{i}|d^{*}\right)$.

### Variational Information Maximizing Exploration

Variational information maximizing exploration (VIME) is an exploration
strategy algorithm based on the maximization of information gain for uncertain
environments of Reinforcement Learning problems. VIME makes actions take
advantage of the interaction opportunities with the environment to obtain as
much information as possible.

VIME adopts Bayesian neural networks (BNNs) to model the environment. The
information gain used by VIME refers to the reduction degree of information
complexity(uncertainty) in an environment. It is calculated in the dynamic
model of environment, $p\left(s_{t+1}\mid s_{t},a_{t};\theta\right)$. That is,
an agent should maximize the decrease degree in uncertain via taking actions.
This process can be abstracted as minimizing the entropy over a sequence of
actions $a_{t}$:

$\sum_{t}\left(H\left(\Theta\mid h_{t},a_{t}\right)-H\left(\Theta\mid
S_{t+1},h_{t},a_{t}\right)\right)$ (2)

where $h_{t}$ is the history of agent and $\Theta$ is a set of the random
variables $\theta\in\Theta$ about the agent in the environment. The mutual
information $\Delta H$ is related to the next state $s_{t+1}$ and the model
parameter $\Theta$:

$\Delta
H\left(s_{t+1},\Theta|s_{t},a_{t}\right)=H\left(\theta|h_{t}\right)-H\left(\theta|s_{t},a_{t},s_{t+1}\right)$
(3)

which is equal to the KL divergence $D_{KL}$. Furthermore, an agent is
encouraged to act towards node with greater $D_{KL}$. So KL divergence can be
considered to be consistent with the information gain. If the entropy of
$\theta$ can be decreased when the agent is in the state $s_{t+1}$, it
indicates that the state $s_{t+1}$ is helpful to promote the dynamic belief.
For an agent, $D_{KL}$ can be interpreted as an intrinsic reward which is
different from rewards in the environment. So the reward of next state is
noted that

$r^{\prime}(s_{t+1})=r(s_{t})+\eta
D_{\mathrm{KL}}\left[p\left(\theta|h_{t},s_{t+1}\right)\|p\left(\theta|h_{t}\right)\right]$
(4)

where $\eta\in\mathbf{R}^{+}$ is a discount factor and contributes to
exploration.

### Counterfactual Regret Minimization

The counterfactual regret minimization (CFR) algorithm (Zinkevich et al. 2007;
Brown et al. 2019), which converges to Nash equilibrium by constantly
iterating to reduce regrets, has been proved to be successful in two-player
zero-sum games with incomplete information through experiments. The core idea
of CFR is to apply the regret minimization algorithms (Littlestone and Warmuth
1994; Chaudhuri, Freund, and Hsu 2009) to each infoset in order to calculate
strategies. In other words, it divides the total regret into a number of
regrets on infosets. The purpose of optimizing policy and finding NE is
achieved by minimizing the cumulative regret. Let $v^{\theta}_{i}(I)$ be the
counterfactual value of player $i\in P(I)$ at infoset $I$:

$v^{\sigma}(I)=\sum_{z\in
Z_{I}}\pi_{-p}^{\sigma}(z[I])\pi^{\sigma}(z[I]\rightarrow z)u_{p}(z)$ (5)

The immediate counterfactual regret $r^{t}(I,a)$ is the counterfactual value
difference between taking action $a$ and whole the infoset $I$ on round t:

$r^{t}(I,a)=v^{\sigma^{t}}(I,a)-v^{\sigma^{t}}(I)$ (6)

For infoset $I$, the counterfactual regret of action $a$ after iteration T is

$R^{T}(I,a)=r^{T}(I,a\mid d^{*})+R^{T-1}(I,a\mid d^{*})$ (7)

$R^{T}(I,a|d^{*})=r^{T}(I,a|d^{*})$ when $T=1$. Formally, The update of
strategy $\sigma^{T+1}$ on round $T+1$ follows as

$\sigma^{t+1}(I,a\mid d^{*})=\frac{R_{+}^{t}(I,a\mid
d^{*})}{\sum_{a^{\prime}\in A(I)}R_{+}^{t}\left(I,a^{\prime}\mid
d^{*}\right)}$ (8)

where $R^{T}_{+}(I,a|d^{*})$ is denoted as non-negative. If
$\sum_{a^{\prime}\in A(I)}R_{+}^{t}\left(I,a^{\prime}\mid d^{*}\right)\leq 0$,
a player will choose a strategy uniformly randomly with probability. And the
average $\bar{\sigma}_{p}^{T}(I|d^{*})$ for each inforset $I$ on iteration $T$
is
$\bar{\sigma}_{p}^{T}(I|d^{*})=\frac{\sum_{t=1}^{T}\left(\pi_{p}^{\sigma^{t}}(I|d^{*})\sigma_{p}^{t}(I|d^{*})\right)}{\sum_{t=1}^{T}\pi_{p}^{\sigma}(I|d^{*})}$.

## Method

In this section, we detailedly describe the VCFR algorithm combining
Variational Information Maximization Exploration (VIME) and Counterfactual
Regret Minimization (CFR) in two parts, which can be used to solve the TEGI
problem under RL. In the first part, an exploration method based on
information gain is introduced, and applied to game tree within the field of
TEGI. The second part describes that the reward with information gain is used
by CFR to solve the approximate Nash equilibrium and interactive strategies.

First of all, we give an overview of the algorithm which is presented in
detail in Algorithm 1.

Algorithm 1 VCFR

1: while $t<T$ do

2: Sample $d_{t}$ according to Observed rewards and transition probability
from unknown environment

3: for each update do

4: Sample rewards from $r\sim P(\cdot\mid z)$, $z\in Z$

5: Collect all $(z,r)$ as datasets

6: for all $(z,r)$ in datasets do

7: Calculate $D_{KL}$ for each $(z,r)$ through the model built by BNN

8: Construct $r^{\prime}=r+\eta D_{KL}$

9: end for

10: Train BNN using datasets and update the distribution of environment

11: end for

12: for $i\in\\{1,2\\}$ do

13: for $h\in H$ do

14: if the probability that node arrives $probs<1e-5$ then

15: prune this node

16: end if

17: Calculate $\bar{\sigma}_{i}^{t}(I)$ by the value of regret with Regret
Matching

18: end for

19: Calculate the average strategy with information gain
$\bar{\sigma}_{i}^{T}$.

20: end for

21: for all $i\in\\{1,2\\}$ do

22: Gather the environment data and update Observed rewards and transition
probability with interaction strategy $\bar{\sigma}_{i}^{T}$

23: end for

24: end while

The posterior distribution of reward corresponding to each action is stored in
the data pool $\mathbb{L}$. We take the prior distribution as input, and we
use Bayesian Neural Network(BNN) (Graves 2011; Blundell et al. 2015) in VIME
to obtain the posterior distribution $\mathbb{P}$ of the reward corresponding
to each action. CFR can calculate the average strategy with the new reward
added with information gain, and will explore the environment to collect the
data according to the curiosity-driven strategy. The approximate Nash
equilibrium will be found after continuous iterations. The whole architecture
of our proposed algorithm is shown in Figure 1.

Figure 1: An architecture illustration of our proposed method. The model
starts by initializing the data pool with the observed reward function $r$.
The data sampled from the data pool is used to train the BNN. Then the KL
divergence on each node can be calculated with the weight distribution of BNN.
The reward $r^{\prime}$ that increases the information gain is assigned to the
terminal node in the game tree. Finally, the data pool is updated by
interacting with the environment using average strategies.

### Modeling Environment with BNN

The construction of the environment model is divided into three steps.
Firstly, the posterior distribution of the unknown environment needs to be
obtained by interacting with the real environment. Secondly, the unknown
environment is modeled by the achieved data. And finally the dynamics model is
set up for the environment. More specifically, we adopt BNN as a modeling
approach. The BNN is different from other neural networks, and it is a kind of
model that can be used to model the posterior distribution to represent
weights in the form of distribution. The regularization effect is provided by
introducing uncertainty into the weights of neural network. BNN can generate
confidence in the prediction results via propagating the uncertainty of the
weights into the prediction process. The output of BNN can describe the
likelihood of probability distributions, then a posterior distribution can be
calculated by sampling or variational inference. BNN has the ability to
quantify uncertain information and strong robustness, and it is very suitable
for the task of modeling environment.

In this work, BNN maintains an player’s dynamics model $p(r|d_{t},z;\theta)$,
where $d_{t}$ denotes the environment obtained by sampling. Even if the
environment has been modeled, it is still difficult to find an approximate
Nash equilibrium without an effective way to update and explore it. In order
to make the modeled unknown environment closer to the real one, and meanwhile
make the exploration strategies more efficient, we use information gain for
more targeted exploration. The information gain can be defined in this task as
the difference between two distributions before and after the environmental
update, which is described by the KL divergence of the two distributions:

$I\left(r;\Theta|d_{t},z\right)=\mathbb{E}_{r}\left[D_{\mathrm{KL}}\left[p\left(\theta|d_{t},z\right)\|p\left(\theta|d^{*},z\right)\right]\right]$
(9)

We take the calculated KL divergence $D_{KL}$ as a measure of the player’s
desire to explore. In other words, the information gain can be considered
numerically equal to the KL divergence. The uncertainty of the environment is
treated as an intrinsic reward for a player. We set a threshold $\lambda$ for
KL divergence. In order to explore the direction of greater curiosity about
the environment, we set the threshold $\lambda$ to 1, and use $\lambda$ to
periodically update the value of information gain. The update frequency
remains unchanged when $D_{KL}>\lambda$. On the contrary, It indicates that
the desire for exploration is low when $K_{KL}<\lambda$, and the update
frequency is reduced. The computational efficiency of information gain can be
greatly improved without affecting the exploration results. The original
reward $r_{t}$ adds to KL divergence for obtaining a new reward
$r^{\prime}_{t}$ with information gain as follows:

$r^{\prime}_{t}=r_{t}+\eta D_{\mathrm{KL}}$ (10)

where $r^{\prime}_{t}$ will be used later as a processed reward on the
interaction strategy. The hyperparameter $\eta$ is set to 0.01, which can
reduce the impact on the results calculated from the CFR and also enhance the
availability of exploration simultaneously. In the process of learning,
maximizing $r^{\prime}$ will be able to achieve a balance of exploration and
exploitation. In this way, the environment can gradually converge to the real
one in theory.

### Information Gain Based CFR

The purpose of information gain based CFR is to find an approximate Nash
equilibrium and obtain the average strategy. This average strategy can not
only be utilized by the player but also be directly used as an interactive
strategy to explore the environment. The traditional CFR algorithm
continuously minimize the regret $R^{T}(I,a)$ by inputting the information of
the game tree, such as the strategy combination of each node and the reward of
the terminal node. However, the real environment $d^{*}$ and the sampled one
are different, so it is not possible to effectively reduce the regret value.
In other words, In this way, the approximate Nash equilibrium of sampled
environments will not be eventually found by continuously decreasing the
exploitability under real environment. Formally, the relationship between
exploitability and regret can be expressed by the following formula:

$\displaystyle expl\left(\bar{\sigma}_{i}|d^{*}\right)=$
$\displaystyle\frac{1}{T}\Big{(}\sum_{i\in\\{1,2\\}}R_{i}^{T}+\sum_{t\leq
T}\big{(}u_{i}(\sigma_{T}^{*}|d^{*})$ (11) $\displaystyle-
u_{i}(\sigma_{T}^{i}|d_{t})\big{)}\Big{)}$

We have also made some improvements to the CFR for situations where some
environmental information cannot be known. We use the $r^{\prime}$, which adds
to information gain, obtained in Equation (10) as one of the environmental
information sources for CFR. The information gain is added to the terminal
node of the game tree. Due to the recursive and iterative characteristics of
CFR, the information gain can affect each node from the bottom to top.
Different from traditional CFR, which continuously reduces the exploitability
to improve the strategy, the addition of information gain is able to keep the
reward $r^{\prime}$ to the direction of environmental exploration to improve
the effect. The large cost of time and space is always a difficulty in the
problem of extensive games with imperfect information. Inspired by pruning
(Brown and Sandholm 2015), judging its arrival probability first for each node
in the game tree. When the node is at a extremely low arrival probability, it
will be regarded as a relatively invalid node and not be traversed in this
round. For all remaining nodes, the player $i$ makes use of the current
strategy $\sigma^{t}_{i}$ to calculate the cumulative regret $R_{t}$ and the
counterfactual value (CFV) $v^{\sigma^{t}}_{i}(h)$ (Li et al. 2020). Through
the regret matching (RM) (Hart and Mas-Colell 2000) of regret value for each
node, the $\sigma^{t}_{i}$ can be calculated. In the end, a game tree with
$v^{\sigma^{t}}_{i}(h)$, $R_{t}$ and $\sigma^{t}_{i}$ for all valid nodes can
be obtained. The significance of the average cumulative regret value
$\bar{R_{T}}$ and the average strategy $\bar{\sigma^{T}}$ is that there is a
non-negligible relationship between them and NE. Despite unknown environmental
information is used in our method, our goal is still to minimize $R_{T}$ and
improve the player’s reward so that the average strategy approaches an
approximate NE.

In our experimental scenario, the interaction strategy is also a vital step,
which affects the environmental certainty. because whether the sampling
environment of the model converges to the real one has a significant impact on
the calculation results of the availability. When the environment is randomly
initialized, the environmental uncertainty is extremely large in the initial
state. Therefore, there is a greater variance in environmental distribution.
To converge the unknown environment and reduce the variance, the average
strategies with information gain are directly used to interact with the real
environment for collecting data in our method.

## Experiments

This section focuses on the details of the experiment, then we introduce the
representative baselines. Finally, we show the experimental results and
analyze them.

### Experimental Setup

Poker is a game with imperfect information, and is suitable to be used as a
platform for evaluating algorithms of equilibrium-finding. In fact, the game
techniques related to imperfect information have also been verified with poker
games in recent years. In this work, we use a variant of Leduc Hold’em poder.
More specifically, we have made some changes to Leduc Hold’em poker (Southey
et al. 2012) which has two players with pre-specified bet and raise amounts to
serve as an experimental environment for our method. It should be noted that
the structure of game tree in changed Leduc Hold’em poker is the same as the
previous structure, but the transition probability of $c$ chance player and
the reward function $r$ of terminal node are uncertain.

Each player’s bid is limited to no more than four or five times the big blind.
The numbers of nodes in the generated game tree are $9,652$ and $34,438$
respectively. Initializing randomly $r\in\\{-1,1\\}$, and the reward function
$r(h)$ is a binary distribution.

We take advantage of Bayesian neural network (BNN) to model the environment.
The BNN architecture we have adopted is shown in Figure 2.

Figure 2: The architecture of Beyesian neural network used by this work, where
$W_{1},W_{2}~{}N(\Sigma,\delta)$. The network takes the distribution of
original rewards $r$ as input and outputs rewards $r\prime$ with information
gain for each possible actions.

This network has a depth of 3 layers. 6 and 1 are the sizes of the input layer
and the output layer. The parameters of the input and hidden layers are set to
Gaussian distribution. The size of the hidden layer is different in Leduc(4)
and Leduc(5), which are 32 and 64 respectively. The 6-dimensional vector
matrix of a single terminal node is encoded as the input to the BNN. We
perform 20,000 iterations using a batch size of 500 in Leduc(4) and 1000 in
Leduc(5).

(a) VCFR and other algorithms in Leduc(4)

(b) VCFR and other algorithms in Leduc(5)

Figure 3: Comparison between VCFR and other algorithms in different
environments. (a) and (b) respectively represent the experiment results in
Leduc(4) and Leduc(5). Among them, VCFR and naive can be seen as a group of
ablation experiments.

(a) VDCFR in Leduc(4)

(b) VDCFR in Leduc(5)

(c) VFSP in Leduc(4)

(d) VFSP in Leduc(5)

Figure 4: The experiment results which can demonstrate the better
generalization of our proposed method. (a) and (b) show the ablation
experiments’ results of VDCFR in Leduc(4) and Leduc(5). The ablation
experiments’ results of VFSP in Leduc(4) and Leduc(5) as shown in (c) and (d).

### Baselines

We choose four kinds of methods as our baselines. The description of baselines
are given below:

  * •

PSRL-CFR: Posterior sampling for reinforcement learning with counterfactual
regret minimization (PSRL-CFR) (Zhou, Li, and Zhu 2020) proposes a framework
that combines PSRL and CFR. The environment is transformed into known by
Thompson sampling, and the CFR algorithm is used to calculate the approximate
Nash equilibrium. In order to update data in the environment, the special
strategies $\hat{\sigma}_{1}$ and $\hat{\sigma}_{2}$ are regarded as
interaction strategies.

  * •

FSP: Fictitious self-play (Conitzer and Sandholm 2007; Heinrich, Lanctot, and
Silver 2015) is a popular algorithm to find Nash equilibrium (NE) in uncertain
setting. FSP needs to make use of Fitted-Q iteration (see PSRL-CFR) with
initial hyperparameters to learn the best response to the average strategy of
each player’s opponent when the environment is unknown.

  * •

MCCFR-OS: Monte Carlo counterfactual regret minimization based on outcome
sampling (Lanctot et al. 2009) is a popular variant of CFR that avoids
traversing the entire game-tree by sampling only a single playing of the game
on each iteration. The $\epsilon$-greedy is the exploration strategy where
$\epsilon=0.1$.

  * •

Variants of VCFR: In order to better measure the validity of our experimental
methods, we use three additional variants of VCFR: 1) Naive: The reward
without information gain is inputted into CFR procedure,and the average
strategy by calculating is used as exploration policy to interact with the
unknown environment; 2) Naive-DCFR: To prove the generalization of our
algorithm framework, we use other variant algorithm Discounted CFR. DCFR
(Brown and Sandholm 2019) is a variant algorithm of CFR, and it has three
parameters $\alpha$, $\beta$, and $\gamma$ as discount factors to improve
speed of solution. In every round t, the effects of three parameters are
multiplying cumulative regrets $R$ by $t^{\alpha}/(t^{\alpha}+1)$ when $R>0$,
by $t^{\beta}/(t^{\beta}+1)$ when $R<0$, and contributions to average policy
$\bar{\sigma}$ by $\left(t/(t+1)\right)^{\gamma}$. The basic process is the
same as Navie-CFR, only replacing CFR with DCFR. The previous experiment has
an excellent performance when setting $\alpha=\frac{3}{2}$, $\beta=0$, and
$\gamma=2$; 3) Random: The players take random actions in each round.

### Experimental Results

We iterate the different algorithms on Leduc(4) and Leduc(5) for 20,000 rounds
respectively, and each round has to interact with the environment.
Exploitability is a popular metric to evaluate the effectiveness of our
methods.

Figure 3(a) presents the VCFR and some baselines’ comparison results in
Leduc(4). We can see that our proposed VCFR method performs better than other
algorithms in two different experimental settings. Specifically, in Leduc(4),
VCFR performs the best among all methods, and its exploitability drops to
-0.135 at 20,000 rounds. Followed by the PSRLCFR method with exploitability of
-0.864. Random and PSRLCFR using a special interaction strategy are also
reducing the exploitability, but the speed and the lower bound of convergence
are worse than our method. From the comparison result between the Naive CFR
and VCFR, it is proved that the average strategy with information gain can not
only explore the environment efficiently but also accelerate the convergence.
In Leduc(5) with higher space complexity, the results in Figure 3(b)
demonstrate that our method still maintains excellent performance. After
20,000 iterations, the exploitability of VCFR, PSRLCFR, Random, Naive and
MCCFR-OS are -1.230, -0.980, -0.632, -0.499 and -0.163, respectively. However,
the exploitability of VCFR decreases slower than in Leduc(4). It may be
because the convergence speed of BNN modeling environment will reduce with the
increase of the complexity of the environment. MCCFR-OS and Random perform
poorly in both game environments. The reason for this result is probably that
their exploration strategies are inefficient.

In addition, to verify the better generalization ability of the proposed
method through experiments, we add two additional algorithms: VDCFR and VFSP.
The algorithm architecture of VDCFR and VFSP is similar to VCFR, nonetheless,
CFR is replaced by DCFR or FSP.

The results of two additional ablation experiments are shown in Figure 4,
which can demonstrate the better generalization of our approaches. The
comparison of the two ablation experiments, VFSP and FSP, as well as VDCFR and
Navie-DCFR, shows that the information gain has a significant influence on the
average strategy that can be used to explore the environment. Figure
4(a)-Figure 4(d) show that the algorithm with information gain can speed up
finding approximate Nash equilibrium, and the interaction strategy promotes
convergence in an unknown environment.

## Related Work

### Measure of Uncertainty

There are some previous methods to solve measure of uncertain in unknown
environment. The random prior function (Osband, Aslanides, and Cassirer 2018)
is originally used to enhance the performance of Bootstrapped DQN. While
training bootstrapped function to fit Q with a posterior probability, random
network gives each bootstrapped function a fixed prior. Since the prior
probabilities are initialized randomly, it is possible to improve the
diversity of bootstrapped functions and better fit the distribution of the
posterior probabilities. The measurement method of uncertainty obtained by
fitting random prior has been proved to be successful in theory and
application (Burda et al. 2019; Ciosek et al. 2020). The Deep ensembles
(Lakshminarayanan, Pritzel, and Blundell 2016) is a commonly used measurement
method of uncertainty. Each model in the ensemble is trained based on
bootstrap data, so that the predicted variance between models can be utilized
as a measure of epistemic uncertainty. The disadvantage of deep ensembles is
that it tends to give overconfident estimates of uncertainty. For obtaining
uncertainty estimates, dropout (Gal and Ghahramani 2016) is firstly proposed
to model uncertainty in Deep Learning as a practical tool, and it can also be
extended to quasi-KL (Gal, Hron, and Kendall 2017). However, in this work, we
focus on measuring the uncertainty of the environment with Bayesian Neural
network (BNN)(Brosse, Durmus, and Moulines 2018; Rezende, Mohamed, and
Wierstra 2014). BNN is a traditional approach to measure uncertainty, which
combines probabilistic modeling with neural networks and is able to output the
degree of confidence of prediction results.

### Exploration under Reinforcement Learning

The exploration methods of Reinforcement Learning (RL) for an unknown
environment can be mainly grouped into the following three categories.

The first category related this work is optimistic exploration which is widely
used in RL. Upper-Confidence-Bound exploration (Carpentier et al. 2011) used
in AlphaGo is similar to greedy selection. They both tend to choose the latest
or best actions. The optimistic inital value (Shojaee and Mashhadi 2017)
realizes exploration by increasing the initial value of the function, which
essentially explores the state with a lower frequency of occurrence. It is
worth noting that selection of initial values requires the prior knowledge,
and the exploration will be unstable during the initial stage. Agents tend to
selcet actions with higher entropy values in the gradient bandit algorithm
(Silver et al. 2014), where the entropy of each action is adjusted by the
rewards.

The second category is the posterior sampling (Osband and Van Roy 2017;
Chapelle and Li 2011), which incorporates ideas from Bayesian learning and
focuses on using posterior probabilities for more targeted exploration. The
algorithm based on posterior sampling will modify its probability distribution
after each sampling. Through a large number of samples, the variance of each
action will be reduced.

The third category is related to our work is exploration based on information
gain (Russo and Van Roy 2014). Information gain is generally comprehended as
the intrinsic reward of agents, which can measure the contribution of a new
state to information. To reach a state where more rewards can be obtained, an
agent selects the actions of maximizing empowerment that is calculated by
mutual information (Mohamed and Rezende 2015). If a set of states share the
same optimal action, then the action can be interpreted as a representation of
the states. There is another approach (Still and Precup 2012) also uses mutual
information as an exploration reward. If a set of states share the same
optimal action, then the action can be considered as a representation of
states. The goal is to find the action with the most state information among
the strategies which has uniform rewards. That is, It needs to minimize the
mutual information of actions and the states.

## Conclusion and Discussion

In this paper, we propose a framework named VCFR which combines CFR with
information gain. It is able to obtain efficient exploration strategies for
solving the problem of finding approximate Nash Equilibrium in the scenario of
two-player zero-sum extensive games under unknown environments. Our proposed
method is flexible in that two modules are independent of each other, and this
means that the CFR can be replaced by any algorithms used to find approximate
Nash equilibrium. The results show that our approach outperforms other
baselines.

In the future, this approach can be optimized from different perspectives. Our
method computes the KL divergence at each round. Although we have tried to set
the threshold to shorten the experiment time, the effect is still limited.
Therefore, how to design an effective approach to shorten the calculation time
of KL divergence is a direction that can improve the results.

Another possible perspective is that reducing the reliance of our method on
the structure of two-player zero-sum extended games. The future work needs to
be extended to other types of games or extensive form games with three and
more players.

## References

  * Blundell et al. (2015) Blundell, C.; Cornebise, J.; Kavukcuoglu, K.; and Wierstra, D. 2015.  Weight uncertainty in neural network.  In _International Conference on Machine Learning_ , 1613–1622. PMLR.
  * Brosse, Durmus, and Moulines (2018) Brosse, N.; Durmus, A.; and Moulines, E. 2018.  The promises and pitfalls of stochastic gradient Langevin dynamics.  _arXiv preprint arXiv:1811.10072_.
  * Brown et al. (2019) Brown, N.; Lerer, A.; Gross, S.; and Sandholm, T. 2019.  Deep counterfactual regret minimization.  In _International conference on machine learning_ , 793–802. PMLR.
  * Brown and Sandholm (2015) Brown, N.; and Sandholm, T. 2015.  Regret-Based Pruning in Extensive-Form Games.  In _NIPS_ , 1972–1980.
  * Brown and Sandholm (2018) Brown, N.; and Sandholm, T. 2018.  Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.  _Science_ , 359(6374): 418–424.
  * Brown and Sandholm (2019) Brown, N.; and Sandholm, T. 2019.  Solving imperfect-information games via discounted regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 1829–1836.
  * Burda et al. (2019) Burda, Y.; Edwards, H.; Storkey, A. J.; and Klimov, O. 2019.  Exploration by random network distillation.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net.
  * Carpentier et al. (2011) Carpentier, A.; Lazaric, A.; Ghavamzadeh, M.; Munos, R.; and Auer, P. 2011.  Upper-confidence-bound algorithms for active learning in multi-armed bandits.  In _International Conference on Algorithmic Learning Theory_ , 189–203. Springer.
  * Chapelle and Li (2011) Chapelle, O.; and Li, L. 2011.  An empirical evaluation of thompson sampling.  _Advances in neural information processing systems_ , 24: 2249–2257.
  * Chaudhuri, Freund, and Hsu (2009) Chaudhuri, K.; Freund, Y.; and Hsu, D. J. 2009.  A parameter-free hedging algorithm.  In _Advances in neural information processing systems_ , 297–305.
  * Ciosek et al. (2020) Ciosek, K.; Fortuin, V.; Tomioka, R.; Hofmann, K.; and Turner, R. E. 2020.  Conservative Uncertainty Estimation By Fitting Prior Networks.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Conitzer and Sandholm (2007) Conitzer, V.; and Sandholm, T. 2007.  AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents.  _Mach. Learn._ , 67(1-2): 23–43.
  * Gal and Ghahramani (2016) Gal, Y.; and Ghahramani, Z. 2016.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In _international conference on machine learning_ , 1050–1059. PMLR.
  * Gal, Hron, and Kendall (2017) Gal, Y.; Hron, J.; and Kendall, A. 2017.  Concrete dropout.  _arXiv preprint arXiv:1705.07832_.
  * Gibson et al. (2012) Gibson, R.; Lanctot, M.; Burch, N.; Szafron, D.; and Bowling, M. 2012.  Generalized sampling and variance in counterfactual regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 26.
  * Graves (2011) Graves, A. 2011.  Practical variational inference for neural networks.  _Advances in neural information processing systems_ , 24.
  * Hart and Mas-Colell (2000) Hart, S.; and Mas-Colell, A. 2000.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(5): 1127–1150.
  * Heinrich, Lanctot, and Silver (2015) Heinrich, J.; Lanctot, M.; and Silver, D. 2015.  Fictitious self-play in extensive-form games.  In _International conference on machine learning_ , 805–813. PMLR.
  * Houthooft et al. (2016) Houthooft, R.; Chen, X.; Duan, Y.; Schulman, J.; De Turck, F.; and Abbeel, P. 2016\.  Vime: Variational information maximizing exploration.  _arXiv preprint arXiv:1605.09674_.
  * Lakshminarayanan, Pritzel, and Blundell (2016) Lakshminarayanan, B.; Pritzel, A.; and Blundell, C. 2016.  Simple and scalable predictive uncertainty estimation using deep ensembles.  _arXiv preprint arXiv:1612.01474_.
  * Lanctot et al. (2009) Lanctot, M.; Waugh, K.; Zinkevich, M.; and Bowling, M. 2009.  Monte Carlo sampling for regret minimization in extensive games.  _Advances in neural information processing systems_ , 22: 1078–1086.
  * Li et al. (2020) Li, H.; Hu, K.; Zhang, S.; Qi, Y.; and Song, L. 2020.  Double Neural Counterfactual Regret Minimization.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Littlestone and Warmuth (1994) Littlestone, N.; and Warmuth, M. K. 1994.  The Weighted Majority Algorithm.  _Inf. Comput._ , 108(2): 212–261.
  * Mohamed and Rezende (2015) Mohamed, S.; and Rezende, D. J. 2015.  Variational information maximisation for intrinsically motivated reinforcement learning.  _arXiv preprint arXiv:1509.08731_.
  * Nash et al. (1950) Nash, J. F.; et al. 1950.  Equilibrium points in n-person games.  _Proceedings of the national academy of sciences_ , 36(1): 48–49.
  * Neto (2005) Neto, G. 2005.  From single-agent to multi-agent reinforcement learning: Foundational concepts and methods.  _Learning theory course_ , 2.
  * Osband, Aslanides, and Cassirer (2018) Osband, I.; Aslanides, J.; and Cassirer, A. 2018.  Randomized prior functions for deep reinforcement learning.  _arXiv preprint arXiv:1806.03335_.
  * Osband and Van Roy (2017) Osband, I.; and Van Roy, B. 2017.  Why is posterior sampling better than optimism for reinforcement learning?  In _International conference on machine learning_ , 2701–2710. PMLR.
  * Osborne and Rubinstein (1994) Osborne, M. J.; and Rubinstein, A. 1994.  _A course in game theory_.  MIT press.
  * Rezende, Mohamed, and Wierstra (2014) Rezende, D. J.; Mohamed, S.; and Wierstra, D. 2014.  Stochastic backpropagation and approximate inference in deep generative models.  In _International conference on machine learning_ , 1278–1286. PMLR.
  * Roughgarden (2010) Roughgarden, T. 2010.  Algorithmic game theory.  _Commun. ACM_ , 53(7): 78–86.
  * Russo and Van Roy (2014) Russo, D.; and Van Roy, B. 2014.  Learning to optimize via information-directed sampling.  _Advances in Neural Information Processing Systems_ , 27: 1583–1591.
  * Shojaee and Mashhadi (2017) Shojaee, G. K.; and Mashhadi, H. R. 2017.  Optimistic initial value analysis in a greedy selection approach to MAB problems.  In _2017 7th International Conference on Computer and Knowledge Engineering (ICCKE)_ , 419–424. IEEE.
  * Silver et al. (2014) Silver, D.; Lever, G.; Heess, N.; Degris, T.; Wierstra, D.; and Riedmiller, M. 2014\.  Deterministic policy gradient algorithms.  In _International conference on machine learning_ , 387–395. PMLR.
  * Southey et al. (2012) Southey, F.; Bowling, M.; Larson, B.; Piccione, C.; Burch, N.; Billings, D.; and Rayner, D. C. 2012.  Bayes’ Bluff: Opponent Modelling in Poker.  _CoRR_ , abs/1207.1411.
  * Still and Precup (2012) Still, S.; and Precup, D. 2012.  An information-theoretic approach to curiosity-driven reinforcement learning.  _Theory in Biosciences_ , 131(3): 139–148.
  * Sutton and Barto (2018) Sutton, R. S.; and Barto, A. G. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Zhou, Li, and Zhu (2020) Zhou, Y.; Li, J.; and Zhu, J. 2020.  Posterior sampling for multi-agent reinforcement learning: solving extensive games with imperfect information.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Zinkevich et al. (2007) Zinkevich, M.; Johanson, M.; Bowling, M.; and Piccione, C. 2007.  Regret minimization in games with incomplete information.  _Advances in neural information processing systems_ , 20: 1729–1736.

## References

  * Blundell et al. (2015) Blundell, C.; Cornebise, J.; Kavukcuoglu, K.; and Wierstra, D. 2015.  Weight uncertainty in neural network.  In _International Conference on Machine Learning_ , 1613–1622. PMLR.
  * Brosse, Durmus, and Moulines (2018) Brosse, N.; Durmus, A.; and Moulines, E. 2018.  The promises and pitfalls of stochastic gradient Langevin dynamics.  _arXiv preprint arXiv:1811.10072_.
  * Brown et al. (2019) Brown, N.; Lerer, A.; Gross, S.; and Sandholm, T. 2019.  Deep counterfactual regret minimization.  In _International conference on machine learning_ , 793–802. PMLR.
  * Brown and Sandholm (2015) Brown, N.; and Sandholm, T. 2015.  Regret-Based Pruning in Extensive-Form Games.  In _NIPS_ , 1972–1980.
  * Brown and Sandholm (2018) Brown, N.; and Sandholm, T. 2018.  Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.  _Science_ , 359(6374): 418–424.
  * Brown and Sandholm (2019) Brown, N.; and Sandholm, T. 2019.  Solving imperfect-information games via discounted regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 1829–1836.
  * Burda et al. (2019) Burda, Y.; Edwards, H.; Storkey, A. J.; and Klimov, O. 2019.  Exploration by random network distillation.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net.
  * Carpentier et al. (2011) Carpentier, A.; Lazaric, A.; Ghavamzadeh, M.; Munos, R.; and Auer, P. 2011.  Upper-confidence-bound algorithms for active learning in multi-armed bandits.  In _International Conference on Algorithmic Learning Theory_ , 189–203. Springer.
  * Chapelle and Li (2011) Chapelle, O.; and Li, L. 2011.  An empirical evaluation of thompson sampling.  _Advances in neural information processing systems_ , 24: 2249–2257.
  * Chaudhuri, Freund, and Hsu (2009) Chaudhuri, K.; Freund, Y.; and Hsu, D. J. 2009.  A parameter-free hedging algorithm.  In _Advances in neural information processing systems_ , 297–305.
  * Ciosek et al. (2020) Ciosek, K.; Fortuin, V.; Tomioka, R.; Hofmann, K.; and Turner, R. E. 2020.  Conservative Uncertainty Estimation By Fitting Prior Networks.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Conitzer and Sandholm (2007) Conitzer, V.; and Sandholm, T. 2007.  AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents.  _Mach. Learn._ , 67(1-2): 23–43.
  * Gal and Ghahramani (2016) Gal, Y.; and Ghahramani, Z. 2016.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In _international conference on machine learning_ , 1050–1059. PMLR.
  * Gal, Hron, and Kendall (2017) Gal, Y.; Hron, J.; and Kendall, A. 2017.  Concrete dropout.  _arXiv preprint arXiv:1705.07832_.
  * Gibson et al. (2012) Gibson, R.; Lanctot, M.; Burch, N.; Szafron, D.; and Bowling, M. 2012.  Generalized sampling and variance in counterfactual regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 26.
  * Graves (2011) Graves, A. 2011.  Practical variational inference for neural networks.  _Advances in neural information processing systems_ , 24.
  * Hart and Mas-Colell (2000) Hart, S.; and Mas-Colell, A. 2000.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(5): 1127–1150.
  * Heinrich, Lanctot, and Silver (2015) Heinrich, J.; Lanctot, M.; and Silver, D. 2015.  Fictitious self-play in extensive-form games.  In _International conference on machine learning_ , 805–813. PMLR.
  * Houthooft et al. (2016) Houthooft, R.; Chen, X.; Duan, Y.; Schulman, J.; De Turck, F.; and Abbeel, P. 2016\.  Vime: Variational information maximizing exploration.  _arXiv preprint arXiv:1605.09674_.
  * Lakshminarayanan, Pritzel, and Blundell (2016) Lakshminarayanan, B.; Pritzel, A.; and Blundell, C. 2016.  Simple and scalable predictive uncertainty estimation using deep ensembles.  _arXiv preprint arXiv:1612.01474_.
  * Lanctot et al. (2009) Lanctot, M.; Waugh, K.; Zinkevich, M.; and Bowling, M. 2009.  Monte Carlo sampling for regret minimization in extensive games.  _Advances in neural information processing systems_ , 22: 1078–1086.
  * Li et al. (2020) Li, H.; Hu, K.; Zhang, S.; Qi, Y.; and Song, L. 2020.  Double Neural Counterfactual Regret Minimization.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Littlestone and Warmuth (1994) Littlestone, N.; and Warmuth, M. K. 1994.  The Weighted Majority Algorithm.  _Inf. Comput._ , 108(2): 212–261.
  * Mohamed and Rezende (2015) Mohamed, S.; and Rezende, D. J. 2015.  Variational information maximisation for intrinsically motivated reinforcement learning.  _arXiv preprint arXiv:1509.08731_.
  * Nash et al. (1950) Nash, J. F.; et al. 1950.  Equilibrium points in n-person games.  _Proceedings of the national academy of sciences_ , 36(1): 48–49.
  * Neto (2005) Neto, G. 2005.  From single-agent to multi-agent reinforcement learning: Foundational concepts and methods.  _Learning theory course_ , 2.
  * Osband, Aslanides, and Cassirer (2018) Osband, I.; Aslanides, J.; and Cassirer, A. 2018.  Randomized prior functions for deep reinforcement learning.  _arXiv preprint arXiv:1806.03335_.
  * Osband and Van Roy (2017) Osband, I.; and Van Roy, B. 2017.  Why is posterior sampling better than optimism for reinforcement learning?  In _International conference on machine learning_ , 2701–2710. PMLR.
  * Osborne and Rubinstein (1994) Osborne, M. J.; and Rubinstein, A. 1994.  _A course in game theory_.  MIT press.
  * Rezende, Mohamed, and Wierstra (2014) Rezende, D. J.; Mohamed, S.; and Wierstra, D. 2014.  Stochastic backpropagation and approximate inference in deep generative models.  In _International conference on machine learning_ , 1278–1286. PMLR.
  * Roughgarden (2010) Roughgarden, T. 2010.  Algorithmic game theory.  _Commun. ACM_ , 53(7): 78–86.
  * Russo and Van Roy (2014) Russo, D.; and Van Roy, B. 2014.  Learning to optimize via information-directed sampling.  _Advances in Neural Information Processing Systems_ , 27: 1583–1591.
  * Shojaee and Mashhadi (2017) Shojaee, G. K.; and Mashhadi, H. R. 2017.  Optimistic initial value analysis in a greedy selection approach to MAB problems.  In _2017 7th International Conference on Computer and Knowledge Engineering (ICCKE)_ , 419–424. IEEE.
  * Silver et al. (2014) Silver, D.; Lever, G.; Heess, N.; Degris, T.; Wierstra, D.; and Riedmiller, M. 2014\.  Deterministic policy gradient algorithms.  In _International conference on machine learning_ , 387–395. PMLR.
  * Southey et al. (2012) Southey, F.; Bowling, M.; Larson, B.; Piccione, C.; Burch, N.; Billings, D.; and Rayner, D. C. 2012.  Bayes’ Bluff: Opponent Modelling in Poker.  _CoRR_ , abs/1207.1411.
  * Still and Precup (2012) Still, S.; and Precup, D. 2012.  An information-theoretic approach to curiosity-driven reinforcement learning.  _Theory in Biosciences_ , 131(3): 139–148.
  * Sutton and Barto (2018) Sutton, R. S.; and Barto, A. G. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Zhou, Li, and Zhu (2020) Zhou, Y.; Li, J.; and Zhu, J. 2020.  Posterior sampling for multi-agent reinforcement learning: solving extensive games with imperfect information.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Zinkevich et al. (2007) Zinkevich, M.; Johanson, M.; Bowling, M.; and Piccione, C. 2007.  Regret minimization in games with incomplete information.  _Advances in neural information processing systems_ , 20: 1729–1736.