# Exploration Potential

Jan Leike
Future of Humanity Institute
University of Oxford

###### Abstract

We introduce _exploration potential_ , a quantity that measures how much a
reinforcement learning agent has explored its environment class. In contrast
to information gain, exploration potential takes the problem’s reward
structure into account. This leads to an exploration criterion that is both
necessary and sufficient for asymptotic optimality (learning to act optimally
across the entire environment class). Our experiments in multi-armed bandits
use exploration potential to illustrate how different algorithms make the
tradeoff between exploration and exploitation.

##  1 Introduction

Good exploration strategies are currently a major obstacle for reinforcement
learning (RL). The state of the art in deep RL (Mnih et al., 2015, 2016)
relies on $\varepsilon$-greedy policies: in every time step, the agent takes a
random action with some probability. Yet $\varepsilon$-greedy is a poor
exploration strategy and for environments with sparse rewards it is quite
ineffective (for example the Atari game ‘Montezuma’s Revenge’): it just takes
too long until the agent randomwalks into the first reward.

More sophisticated exploration strategies have been proposed: using
information gain about the environment (Sun et al., 2011; Orseau et al., 2013;
Houthooft et al., 2016) or pseudo-count (Bellemare et al., 2016). In practice,
these exploration strategies are employed by adding an exploration bonus
(‘intrinsic motivation’) to the reward signal (Schmidhuber, 2010). While the
methods above require the agent to have a model of its environment and
formalize the strategy ‘explore by going to where the model has high
uncertainty,’ there are also model-free strategies like the automatic
discovery of options proposed by Machado and Bowling (2016). However, none of
these explicit exploration strategies take the problem’s reward structure into
account. Intuitively, we want to explore more in parts of the environment
where the reward is high and less where it is low. This is readily exposed in
optimistic policies like UCRL (Jaksch et al., 2010) and stochastic policies
like PSRL (Strens, 2000), but these do not make the exploration/exploitation
tradeoff explicitly.

In this paper, we propose _exploration potential_ , a quantity that measures
reward-directed exploration. We consider _model-based_ reinforcement learning
in partially or fully observable domains. Informally, exploration potential is
the Bayes-expected absolute deviation of the value of optimal policies.
Exploration potential is similar to information gain about the environment,
but explicitly takes the problem’s reward structure into account. We show that
this leads to a exploration criterion that is both _necessary_ and
_sufficient_ for asymptotic optimality (learning to act optimally across an
environment class): a reinforcement learning agent learns to act optimal in
the limit _if and only if_ the exploration potential converges to $0$. As
such, exploration potential captures the essence of what it means to ‘explore
the right amount’.

Another exploration quantity that is both necessary and sufficient for
asymptotic optimality is information gain about the optimal policy (Russo and
Van Roy, 2014; Reddy et al., 2016). In contrast to exploration potential, it
is not measured on the scale of rewards, making an explicit value-of-
information tradeoff more difficult.

For example, consider a 3-armed Gaussian bandit problem with means $0.6$,
$0.5$, and $-1$. The information content is identical in every arm. Hence an
exploration strategy based on maximizing information gain about the
environment would query the third arm, which is easily identifiable as
suboptimal, too frequently (linearly versus logarithmically). This arm
provides information, but this information is not very useful for solving the
reinforcement learning task. In contrast, an exploration potential based
exploration strategy concentrates its exploration on the first two arms.

##  2 Preliminaries and Notation

A reinforcement learning agent interacts with an environment in cycles: at
time step $t$ the agent chooses an _action_ $a_{t}$ and receives a _percept_
$e_{t}=(o_{t},r_{t})$ consisting of an _observation_ $o_{t}$ and a _reward_
$r_{t}\in[0,1]$; the cycle then repeats for $t+1$. We use
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}$
to denote a history of length $t-1$. With abuse of notation, we treat
histories both as outcomes and as random variables.

A _policy_ is a function mapping a history
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}$
and an action $a$ to the probability
$\pi(a\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})$
of taking action $a$ after seeing history
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}$.
An _environment_ is a function mapping a history
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{1:t}$
to the probability
$\nu(e_{t}\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}a_{t})$
of generating percept $e_{t}$ after this history
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}a_{t}$.
A policy $\pi$ and an environment $\nu$ generate a probability measure
$\nu^{\pi}$ over infinite histories, the expectation over this measure is
denoted with ${\mathbb{E}}^{\pi}_{\nu}$. The _value_ of a policy $\pi$ in an
environment $\nu$ given history
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}$
is defined as

$V_{\nu}^{\pi}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}):=(1-\gamma){\mathbb{E}}_{\nu}^{\pi}\left[\sum_{k=t}^{\infty}\gamma^{k}r_{k}\,\middle|\,\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}\right],$

where $\gamma\in(0,1)$ is the discount factor. The _optimal value_ is defined
as
$V^{*}_{\nu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}):=\sup_{\pi}V^{\pi}_{\nu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})$,
and the _optimal policy_ is
$\pi^{*}_{\nu}:=\operatorname*{arg\,max}_{\pi}V^{\pi}_{\nu}$. We use $\mu$ to
denote the true environment.

We assume the nonparametric setting: let $\mathcal{M}$ denote a countable
class of environments containing the true environment $\mu$. Let
$w\in\Delta\mathcal{M}$ be a prior probability distribution on $\mathcal{M}$.
After observing the history
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}$
the prior $w$ is updated to the posterior
$w(\nu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}):=w(\nu)\nu(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})/(\sum_{\rho\in\mathcal{M}}w(\rho)\rho(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}))$.
A policy $\pi$ is _asymptotically optimal in mean_ iff for every
$\mu\in\mathcal{M}$,
${\mathbb{E}}_{\mu}^{\pi}[V^{*}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-V^{\pi}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})]\to
0$ as $t\to\infty$.

##  3 Exploration Potential

We consider _model-based_ reinforcement learning where the agent learns a
model of its environment. With this model, we can estimate the value of any
candidate policy. Concretely, let $\hat{V}_{t}^{\pi}$ denote our estimate of
the value of the policy $\pi$ at time step $t$. We assume that the agent’s
learning algorithm satisfies _on-policy value convergence_ (OPVC):

$V^{\pi}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-\hat{V}_{t}^{\pi}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\to
0\text{ as $t\to\infty$ $\mu^{\pi}$-almost surely.}$ (1)

This does _not_ imply that our model of the environment converges to the
truth, only that we learn to predict the value of the policy that we are
following. On-policy value convergence does not require that we learn to
predict off-policy, i.e., the value of other policies. In particular, we might
not learn to predict the value of the $\mu$-optimal policy $\pi^{*}_{\mu}$.

For example, a Bayesian mixture or an MDL-based estimator both satisfy OPVC if
the true environment is the environment class; for more details, see Leike
(2016, Sec. 4.2.3).

We define the $\hat{V}_{t}$-greedy policy as
$\pi^{*}_{\hat{V}}:=\operatorname*{arg\,max}_{\pi}\hat{V}^{\pi}_{t}$.

###  3.1 Definition

######  Definition 1 (Exploration Potential).

Let $\mathcal{M}$ be a class of environments and let
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}$
be a history. The _exploration potential_ is defined as

$\mathrm{EP}_{\mathcal{M}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}):=\sum_{\nu\in\mathcal{M}}w(\nu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\left|V_{\nu}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-\hat{V}_{t}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\right|.$

Intuitively, $\mathrm{EP}$ captures the amount of exploration that is still
required before having learned the entire environment class. Asymptotically
the posterior concentrates around environments that are compatible with the
current environment. EP then quantifies how well the model $\hat{V}_{t}$
understands the value of the compatible environments’ optimal policies.

######  Remark 2 (Properties of $\mathrm{EP}$).

  1. (i)

$\mathrm{EP}_{\mathcal{M}}$ depends neither on the true environment $\mu$, nor
on the agent’s policy $\pi$.

  2. (ii)

$\mathrm{EP}_{\mathcal{M}}$ depends on the choice of the prior $w$ and on the
agent’s model of the world $\hat{V}_{t}$.

  3. (iii)

$0\leq\mathrm{EP}_{\mathcal{M}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\leq
1$ for all histories
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}$.

The last item follows from the fact that the posterior
$w(\,\cdot\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})$
and the value function $V$ are bounded between $0$ and $1$.

###  3.2 Sufficiency

######  Proposition 3 (Bound on Optimality).

For all $\mu\in\mathcal{M}$,

$V^{*}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-V^{\pi^{*}_{\hat{V}}}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})~{}\leq~{}\hat{V}_{t}^{*}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-V^{\pi^{*}_{\hat{V}}}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})~{}+~{}\frac{\mathrm{EP}_{\mathcal{M}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}{w(\mu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}.$

###### Proof.

$\displaystyle\left|V^{*}_{\mu}-\hat{V}_{t}^{\pi^{*}_{\mu}}\right|=\frac{w(\mu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}{w(\mu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}\left|V^{*}_{\mu}-\hat{V}_{t}^{\pi^{*}_{\mu}}\right|\leq\sum_{\nu\in\mathcal{M}}\frac{w(\nu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}{w(\mu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}\left|V^{*}_{\nu}-\hat{V}_{t}^{\pi^{*}_{\nu}}\right|=\frac{\mathrm{EP}_{\mathcal{M}}}{w(\mu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}$

Therefore

$V^{*}_{\mu}-V^{\pi^{*}_{\hat{V}}}_{\mu}~{}~{}~{}=\underbrace{V^{*}_{\mu}-\hat{V}_{t}^{\pi^{*}_{\mu}}}_{\leq\mathrm{EP}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})/w(\mu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}+~{}~{}~{}\underbrace{\hat{V}_{t}^{\pi^{*}_{\mu}}-\hat{V}_{t}^{*}}_{\leq
0}~{}~{}+~{}~{}~{}\hat{V}^{*}_{t}-V^{\pi^{*}_{\hat{V}}}_{\mu}.\qed$

The bound of subsection 3.2 is to be understood as follows.

$\underbrace{V^{*}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-V^{\pi^{*}_{\hat{V}}}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}_{\text{optimality
of the greedy
policy}}~{}~{}\leq~{}~{}\underbrace{\hat{V}^{*}_{t}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-V^{\pi^{*}_{\hat{V}}}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}_{\text{OPVC}}~{}~{}~{}+\underbrace{\mathrm{EP}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}_{\text{exploration
potential}}/\underbrace{w(\mu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}_{\text{posterior}}$

If we switch to the greedy policy $\pi^{*}_{\hat{V}}$, then
$\hat{V}_{t}^{*}-V^{\pi^{*}_{\hat{V}}}_{\mu}\to 0$ due to on-policy value
convergence (1). This reflects how well the agent learned the environment’s
response to the Bayes-optimal policy. Generally, following the greedy policy
does not yield enough exploration for $\mathrm{EP}$ to converge to $0$. In
order to get a policy $\pi$ that is asymptotically optimal, we have to combine
an exploration policy which ensures that $\mathrm{EP}\to 0$ and then gradually
phase out exploration by switching to the $\pi^{*}_{\hat{V}}$-greedy policy.
Because of property (i), the agent can compute its current $\mathrm{EP}$ value
and thus check how close it is to $0$. The higher the prior belief in the true
environment $\mu$, the smaller this value will be (in expectation).

###  3.3 Necessity

######  Definition 4 (Policy Convergence).

Let $\pi$ and $\pi^{\prime}$ be two policies. We say the policy $\pi$
_converges to $\pi^{\prime}$ in $\mu^{\pi}$-probability_ iff
$|\hat{V}^{\pi}_{t}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-\hat{V}^{\pi^{\prime}}_{t}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})|\to
0$ as $t\to\infty$ in $\hat{V}$.

We assume that $\hat{V}_{t}$ is continuous in the policy argument. If $\pi$
converges to $\pi^{\prime}$ in total variation in the sense that
$\pi(a\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<k})-\pi^{\prime}(a\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<k})\to
0$ for all actions $a$ and $k\geq t$, then $\pi$ converges to $\pi^{\prime}$
in $\hat{V}$.

######  Definition 5 (Strongly Unique Optimal Policy).

An environment $\mu$ admits a _strongly unique optimal policy_ iff there is a
$\mu$-optimal policy $\pi^{*}_{\mu}$ such that for all policies $\pi$ if

$V^{*}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-V^{\pi}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\to
0\text{ in $\mu^{\pi}$-probability,}$

then $\pi$ converges to $\pi^{*}_{\mu}$ in $\hat{V}$.

Assuming that $\hat{V}_{t}^{\pi}$ is continuous is $\pi$, an environment $\mu$
has a unique optimal policy if there are no ties in
$\operatorname*{arg\,max}_{a}V^{*}_{\mu}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}a)$.
Admitting a strongly unique optimal policy is an even stronger requirement
because it requires that there exist no other policies that approach the
optimal value asymptotically but take different actions (i.e., there is a
constant gap in the argmax). For any finite-state (PO)MDP with a unique
optimal policy that policy is also strongly unique.

######  Proposition 6 (Asymptotic Optimality $\Rightarrow\mathrm{EP}\to 0$).

If the policy $\pi$ is asymptotically optimal in mean in the environment class
$\mathcal{M}$ and each environment $\nu\in\mathcal{M}$ admits a strongly
unique optimal policy, then $\mathrm{EP}_{\mathcal{M}}\to 0$ in
$\mu^{\pi}$-probability for all $\mu\in\mathcal{M}$.

###### Proof.

Since $\pi$ is asymptotically optimal in mean in $\mathcal{M}$, we have that
$V^{*}_{\mu}-V^{\pi}_{\mu}\to 0$ and since $\mu$ admits a strongly unique
optimal policy, $\pi$ converges to $\pi^{*}_{\mu}$ in $\mu^{\pi}$-probability,
thus $\hat{V}_{t}^{\pi}-\hat{V}_{t}^{\pi^{*}_{\mu}}\to 0$. By on-policy value
convergence $V^{\pi}_{\mu}-\hat{V}_{t}^{\pi}\to 0$. Therefore

$V^{*}_{\mu}-\hat{V}_{t}^{\pi^{*}_{\mu}}=V^{*}_{\mu}-V^{\pi}_{\mu}+V^{\pi}_{\mu}-\hat{V}_{t}^{\pi}+\hat{V}_{t}^{\pi}-\hat{V}_{t}^{\pi^{*}_{\mu}}\to
0$

and thus

${\mathbb{E}}^{\pi}_{\mu}\left|V_{\mu}^{\pi^{*}_{\mu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-\hat{V}_{t}^{\pi^{*}_{\mu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\right|\to
0\text{ for all $\mu\in\mathcal{M}$.}$ (2)

Now

$\displaystyle{\mathbb{E}}^{\pi}_{\mu}[\mathrm{EP}_{\mathcal{M}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})]$
$\displaystyle={\mathbb{E}}^{\pi}_{\mu}\left[\sum_{\nu\in\mathcal{M}}w(\nu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\left|V_{\nu}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-\hat{V}_{t}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\right|\right]$
$\displaystyle\leq\frac{1}{w(\mu)}{\mathbb{E}}^{\pi}_{\xi}\left[\sum_{\nu\in\mathcal{M}}w(\nu\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\left|V_{\nu}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-\hat{V}_{t}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\right|\right]$
$\displaystyle=\frac{1}{w(\mu)}\sum_{\nu\in\mathcal{M}}w(\nu){\mathbb{E}}^{\pi}_{\xi}\left[\frac{\nu^{\pi}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}{\xi^{\pi}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})}\left|V_{\nu}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-\hat{V}_{t}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\right|\right]$
$\displaystyle=\frac{1}{w(\mu)}\sum_{\nu\in\mathcal{M}}w(\nu){\mathbb{E}}^{\pi}_{\nu}\left|V_{\nu}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})-\hat{V}_{t}^{\pi^{*}_{\nu}}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})\right|\to
0$

by (2) and Hutter (2005, Lem. 5.28ii). ∎

If we don’t require the condition on strongly unique optimal policies, then
the policy $\pi$ could be asymptotically optimal while $\mathrm{EP}\not\to 0$:
there might be another policy $\pi^{\prime}$ that is very different from any
optimal policy $\pi^{*}_{\mu}$, but whose $\mu$-value approaches the optimal
value: $V^{*}_{\mu}-V^{\pi^{\prime}}_{\mu}\to 0$ as $t\to\infty$. Our policy
$\pi$ could converge to $\pi^{\prime}$ without $\mathrm{EP}$ converging to
$0$.

##  4 Exploration Potential in Multi-Armed Bandits

Figure 1:  Exploration potential over time for different bandit algorithms in
the Bernoulli bandit with arms $0.6,0.5,0.4,0.4$ (double logarithmic plot);
shaded regions correspond to one standard deviation. Lower exploration
potential means more exploration. The notable change in slope in around time
steps 20–80 stems from the fact that it takes about that long to reliably
distinguish the first two arms. The dashed line corresponds to the optimal
asymptotic rate of $t^{-1/2}$.

In this section we use experiments with multi-armed Bernoulli bandits to
illustrate the properties of exploration potential. The class of Bernoulli
bandits is $\Theta=[0,1]^{k}$ (the arms’ means). In each time step, the agent
chooses an action (arm) $i\in\\{1,\ldots,k\\}$ and receives a reward
$r_{t}\sim Bernoulli(\theta_{i}^{*})$ where $\theta^{*}\in\Theta$ is the true
environment. Since $\Theta$ is uncountable, exploration potential is defined
with an integral instead of a sum:

$\mathrm{EP}_{\Theta}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}):=\int_{\Theta}p(\theta\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})|\theta_{j(\theta)}-\hat{\theta}_{j(\theta)}|d\theta$

where
$p(\theta\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})$
is the posterior distribution given the history
$\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}$,
$\hat{\theta}:=\int_{\Theta}\theta
p(\theta\mid\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t})d\theta$
is the Bayes-mean parameter, and
$j(\theta):=\operatorname*{arg\,max}_{i}\theta_{i}$ is the index of the best
arm accoding to $\theta$.

Figure 1 shows the exploration potential of several bandit algorithms,
illustrating how much each algorithm explores. Notably, optimally confident
UCB (Lattimore, 2015) stops exploring around time step 700 and focuses on
exploitation (because in contrast to the other algorithms it knows the
horizon). Thompson sampling, round robin (alternate between all arms), and
$\varepsilon$-greedy explore continuously (but $\varepsilon$-greedy is less
effective). The optimal strategy (always pull the first arm) never explores
and hence its exploration potential decreases only slightly.

Exploration potential naturally gives rise to an exploration strategy:
greedily minimize Bayes-expected exploration potential (MinEP); see Algorithm
1. This strategy unsurprisingly explores more than all the other algorithms
when measured on exploration potential, but in bandits it also turns out to be
a decent exploitation strategy because it focuses its attention on the most
promising arms. For empirical performance see Figure 2. However, MinEP is
generally not a good exploitation strategy in more complex environments like
MDPs.

1:for $t\in\mathbb{N}$ do

2:
$a_{t}:=\operatorname*{arg\,min}_{a\in\mathcal{A}}\mathbb{E}_{e_{t}\sim\text{posterior}}[\mathrm{EP}(\mathchoice{\mbox{{\ae}}}{\mbox{{\ae}}}{\mbox{\scriptsize{\ae}}}{\mbox{\scriptsize{\ae}}}_{<t}ae_{t})]$

3: take action $a_{t}$

4: observe percept $e_{t}$

Algorithm 1 The MinEP Algorithm Figure 2:  Average regret over time for
different bandit algorithms in the Bernoulli bandit with arms
$0.6,0.5,0.4,0.4$. MinEP outperforms UCB1 (Auer et al., 2002) after 10 000
steps, but neither Thompson sampling nor OCUCB.

##  5 Discussion

Several variants on the definition exploration potential given in subsection
3.1 are conceivable. However, often they do not satisfy at least one of the
properties that make our definition appealing. Either they break the necessity
(subsection 3.2), sufficiency (subsection 3.3), our proofs thereof, or they
make $\mathrm{EP}$ hard to compute. For example, we could replace
$|V^{*}_{\nu}-\hat{V}^{\pi^{*}_{\nu}}_{t}|$ by $|V^{*}_{\nu}-V^{\pi}_{\nu}|$
where $\pi$ is the agent’s future policy. This preserves both necessesity and
sufficiency, but relies on computing the agent’s future policy. If the agent
uses exploration potential for taking actions (e.g., for targeted
exploration), then this definition becomes a self-referential equation and
might be very hard to solve. Following Dearden et al. (1999), we could
consider $|V^{*}_{\nu}-\hat{V}^{*}_{t}|$ which has the convenient side-effect
that it is model-free and therefore applies to more reinforcement learning
algorithms. However, in this case the necessity guarantee (subsection 3.3)
requires the additional condition that the agent’s policy converges to the
greedy policy $\pi^{*}_{\hat{V}}$. Moreover, this does not remove the
dependence on a model since we still need a model class $\mathcal{M}$ and a
posterior.

Based on the recent successes in approximating information gain (Houthooft et
al., 2016), we are hopeful that exploration potential can also be approximated
in practice. Since computing the posterior is too costly for complex
reinforcement learning problems, we could (randomly) generate a few
environments and estimate the sum in subsection 3.1 with them.

In this paper we only scratch the surface on exploration potential and leave
many open questions. Is this the correct definition? What are good rates at
which EP should converge to 0? Is minimizing EP the most efficient exploration
strategy? Can we compute EP more efficiently than information gain?

#### Acknowledgments

We thank Tor Lattimore, Marcus Hutter, and our coworkers at the FHI for
valuable feedback and discussion.

## References

  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2-3):235–256, 2002.
  * Bellemare et al. (2016) Marc G Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos.  Unifying count-based exploration and intrinsic motivation.  Technical report, 2016.  http://arxiv.org/abs/1606.01868.
  * Dearden et al. (1999) Richard Dearden, Nir Friedman, and David Andre.  Model based Bayesian exploration.  In _Uncertainty in Artificial Intelligence_ , pages 150–159, 1999\.
  * Houthooft et al. (2016) Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel.  Curiosity-driven exploration in deep reinforcement learning via bayesian neural networks.  Technical report, 2016.  http://arxiv.org/abs/1605.09674.
  * Hutter (2005) Marcus Hutter.  _Universal Artificial Intelligence_.  Springer, 2005.
  * Jaksch et al. (2010) Thomas Jaksch, Ronald Ortner, and Peter Auer.  Near-optimal regret bounds for reinforcement learning.  _Journal of Machine Learning Research_ , 11(Apr):1563–1600, 2010.
  * Lattimore (2015) Tor Lattimore.  Optimally confident UCB: Improved regret for finite-armed bandits.  Technical report, 2015.  http://arxiv.org/abs/1507.07880.
  * Leike (2016) Jan Leike.  _Nonparametric General Reinforcement Learning_.  PhD thesis, Australian National University, 2016.
  * Machado and Bowling (2016) Marlos C Machado and Michael Bowling.  Learning purposeful behaviour in the absence of rewards.  Technical report, 2016.  http://arxiv.org/abs/1605.07700.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Mnih et al. (2016) Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In _International Conference on Machine Learning_ , 2016.
  * Orseau et al. (2013) Laurent Orseau, Tor Lattimore, and Marcus Hutter.  Universal knowledge-seeking agents for stochastic environments.  In _Algorithmic Learning Theory_ , pages 158–172. Springer, 2013\.
  * Reddy et al. (2016) Gautam Reddy, Antonio Celani, and Massimo Vergassola.  Infomax strategies for an optimal balance between exploration and exploitation.  _Journal of Statistical Physics_ , 163(6):1454–1476, 2016.
  * Russo and Van Roy (2014) Dan Russo and Benjamin Van Roy.  Learning to optimize via information-directed sampling.  In _Advances in Neural Information Processing Systems_ , pages 1583–1591, 2014.
  * Schmidhuber (2010) Jürgen Schmidhuber.  Formal theory of creativity, fun, and intrinsic motivation (1990–2010).  _IEEE Transactions on Autonomous Mental Development_ , 2(3):230–247, 2010.
  * Strens (2000) Malcolm Strens.  A Bayesian framework for reinforcement learning.  In _International Conference on Machine Learning_ , pages 943–950, 2000.
  * Sun et al. (2011) Yi Sun, Faustino Gomez, and Jürgen Schmidhuber.  Planning to be surprised: Optimal bayesian exploration in dynamic environments.  In _Artificial General Intelligence_ , pages 41–51. Springer, 2011\.