A Strongly Asymptotically Optimal Agent in General Environments

1 Introduction

"Efforts to solve [an instance of the explorationexploitation problem] so sapped the energies and minds of Allied analysts that the suggestion was made that the problem be dropped over Germany, as the ultimate instrument of intellectual sabotage." -Peter Whittle [Whittle, 1979]

The Allied analysts were considering the simplest possible problem in which there is a trade-off to be made between exploiting, taking the apparently best option, and exploring, choosing a different option to learn more. We tackle what we consider the most difficult instance of the explorationexploitation trade-off problem: when the environment could be any computable probability distribution, not just a multiarmed bandit, how can one achieve optimal performance in the limit?

⇤Contact Author

Our work is within the Reinforcement Learning (RL) paradigm: an agent selects an action, and the environment responds with an observation and a reward. The interaction may end, or it may continue forever. Each interaction cycle is called a timestep. The agent has a discount function that weights its relative concern for the reward it achieves at various future timesteps. The agent's job is to select actions that maximize the total expected discounted reward it achieves in its lifetime. The "value" of an agent's policy at a certain point in time is the expected total discounted reward it achieves after that time if it follows that policy. One formal specification of the exploration-exploitation problem is: what policy can an agent follow so that the policy's value approaches the value of the optimal informed policy with probability 1, even when the agent doesn't start out knowing the true dynamics of its environment?

Most work in RL makes strong assumptions about the environment-that the environment is Markov, for instance. Impressive recent development in the field of reinforcement learning often makes use of the Markov assumption, including Deep Q Networks [Mnih et al., 2015], A3C [Mnih et al., 2016], Rainbow [Hessel et al., 2018], and AlphaZero [Silver et al., 2017]. Another example of making strong assumptions in RL comes from some model-based algorithms that implicitly assume that the environment is representable by, for example, a fixed-size neural network, or whatever construct is used to model the environment. We do not make any such assumptions.

Many recent developments in RL are largely about tractably learning to exploit; how to explore intelligently is a separate problem. We address the latter problem. Our approach, inquisitiveness, is based on Orseau et al.'s [2013] Knowledge Seeking Agent for Stochastic Environments, which selects the actions that best inform the agent about what environment it is in. Our Inquisitive Reinforcement Learner (Inq) explores like a knowledge seeking agent, and is more likely to explore when there is apparently (according to its current beliefs) more to be learned. Sometimes exploring well requires "expeditions," or many consecutive exploratory actions. Inq entertains expeditions of all lengths, although it follows the longer ones less often, and it doesn't resolutely commit in advance to seeing the expedition through.

This is a very human approach to information acquisition.

When we spot an opportunity to learn something about our natural environment, we feel inquisitive. We get distracted. We are inclined to check it out, even if we don't see directly in advance how this information might help us better achieve our goals. Moreover, if we can tell that the opportunity to learn something requires a longer term project, we may find ourselves less inquisitive.

For the class of computable environments (stochastic environments that follow a computable probability distribution), it was previously unknown whether any policy could achieve strong asymptotic optimality (convergence of the value to optimality with probability 1). Lattimore et al. [2011] showed that no deterministic policy could achieve this. The key advantage that stochastic policies have is that they can let the exploration probability go to 0 while still exploring infinitely often. (For example, an agent that explores with probability 1◁t at time t still explores infinitely often).

There is a weaker notion of optimality-"weak asymptotic optimality"-for which positive results already exist; this condition requires that the average value over the agent's lifetime approach optimality. Lattimore et al. [2011] identified a weakly asymptotically optimal agent for deterministic computable environments; the agent maintains a list of environments consistent with its observations, exploiting as if it is in the first such one, and exploring in bursts. A recent algorithm for a Thompson Sampling Bayesian agent was shown, with an elegant proof, to be weakly asymptotically optimal in all computable environments, but not strongly asymptotically optimal [Leike et al., 2016].

Most work in RL regards (Partially Observable) Markov Decision Processes (PO)MDPs. However, environments that enter completely novel states infinitely often render (PO)MDP algorithms helpless. For example, an RL agent acting as a chatbot, optimizing a function, or proving mathematical theorems would struggle to model the environment as an MDP, and would likely require an exploration mechanism like ours. In the chatbot case, for instance, as a conversation with a person progresses, the person never returns to the same state.

If we formally compare Inq to existing algorithms in MDPs, we find that many achieve asymptotic optimality. Epsilon-greedy, upper confidence bound, and Thompson sampling exploration strategies suffice in MDPs. Our primary motivation is for the sorts of environments described above. To discriminate between exploratory approaches in ergodic MDPs, one can formally bound regret, and we would like to do this for Inq in the future.

For comparison, some algorithms which use the MDP formalism also consider information-theoretic approaches to exploration, such as VIME [Houthooft et al., 2016], the agent in [Still, 2009], and TEXPLORE-VANIR [Hester and Stone, 2012].

In Section 2, we formally describe the RL setup and present notation. In Section 3, we present the algorithm for Inq. In Section 4, we prove our main result: that Inq is strongly asymptotically optimal. In Section 5, we present experimental results comparing Inq to weakly asymptotically optimal agents. Finally, we discuss the relevance of this exploration regime to tractable algorithms. Appendix A collates notation and definitions for quick reference. Appendix B contains the proofs of the lemmas. Both of these, along with the full paper, may be found at https://arxiv.org/abs/1903.01021.

2 Notation

We follow the notation of Orseau, et al. [2013]. The reinforcement learning setup is as follows: A is a finite set of actions available to the agent; O is a finite set of observations it might observe, and R = [0↪ 1] \ Q is the set of possible rewards. The set of all possible interactions in a timestep is H := A ⇥ O ⇥ R. At every timestep, one element from this set occurs. A reinforcement learner's policy ⇡ is a stochastic function which outputs an action given an interaction history, denoted by ⇡ : H⇤ A. (X ⇤ := S1i=0 X i represents all finite strings from an alphabet X). An environment is a stochastic function which outputs an observation and reward given an interaction history and an action: ⌫ : H⇤ ⇥A O⇥R. For a stochastic function f : X !Y, f(y♣x) denotes the probability that f outputs y 2 Y when x 2 X is input.

A policy and an environment induce a probability measure over H1, the set of all possible infinite histories: for h 2 H⇤ , P⇡⌫ (h) denotes the probability that an infinite history begins with h when actions are sampled from the policy ⇡, and observations and rewards are sampled from the environment ⌫. Formally, we define this inductively: P⇡⌫ (✏) 7! 1, where ✏ is the empty history, and for h 2 H⇤ , a 2 A, o 2 O, r 2 R, we define P⇡⌫ (haor) 7! P⇡⌫ (h)⇡(a♣h)⌫(or♣ha). In an infinite history h1:1 2 H1, at, ot, and rt refer to the tth action, observation and reward, and ht refers to the tth timestep: atotrt. h<t refers to the first t - 1 timesteps, and ht:k refers to the string of timesteps t through k (inclusive). Strings of actions, observations, and rewards are notated similarly.

A Bayesian agent deems a class of environments a priori feasible. Its "beliefs" take the form of a probability distribution over which environment is the true one. We call this the agent's belief distribution. In our formulation, Inq considers any computable environment feasible, and starts with a prior belief distribution based on the environments' Kolmogorov complexities: that is, the length of the shortest program that computes the environment on some reference machine. However, all our results hold as long as the true environment is contained in the class of environments that are considered feasible, and as long as the prior belief distribution assigns nonzero probability to each environment in the class. We take M to be the class of all computable environments, and w(⌫) := 2-K(⌫)(1+") ◁N to be the prior probability of the environment ⌫, where K is the Kolmogorov complexity, " > 0, and N is a normalization constant. (" > 0 ensures the prior has finite entropy, which facilitates analysis.) A smaller class with a different prior probability could easily be substituted for M and w(⌫).

We use ⇠ to denote the agent's beliefs about future observations. Together with a policy ⇡ it defines a Bayesian mixture measure: P⇡⇠ (·) := P⌫2M w(⌫)P⇡⌫ (·). The posterior belief distribution of the agent after observing a history h 2 H⇤ is w(⌫♣h) := w(⌫)P⇡0 ⌫ (h)◁P⇡0 ⇠ (h). This definition is independent of the choice of ⇡0 as long as P⇡0 ⇠ (h) > 0;

we can fix a reference policy ⇡0 just for this definition if we like. We sometimes also refer to the conditional distribution ⇠(or♣ha) := P⌫2M w(⌫♣h)⌫(or♣ha).

The agent's discount at a timestep is denoted γt. To normalize the agent's policy's value to [0↪ 1], we introduce Γt := P1k=t γk. (Normalization makes value convergence nontrivial). We consider an agent with a bounded horizon: 8" > 0 9m 8t : Γt+m◁Γt  ". Intuitively, this means that the agent does not become more and more farsighted over time. Note this does not require a finite horizon. A classic discount function giving a bounded horizon is a geometric one: for 0  γ < 1, γt = γ t . The value of a policy ⇡ in an environment ⌫, given a history h<t 2 Ht-1 , is

Here, the expectation is with respect to the probability measure P⇡⌫ . Reinforcement Learning is the attempt to find a policy that makes this value high, without access to ⌫.

3 Inquisitive Reinforcement Learner

We first describe how Inq exploits, then how it explores. It exploits by maximizing the discounted sum of its reward in expectation over its current beliefs, and it explores by following maximally informative "exploratory expeditions" of various lengths.

An optimal policy with respect to an environment ⌫ is a policy that maximizes the value.

where ⇧ = H⇤ A is the space of all policies. An optimal deterministic policy always exists [Lattimore and Hutter, 2014b]. When exploiting, Inq simply maximizes the value according to its belief distribution ⇠. Since this policy is deterministic, we write a⇤ (h<t) to mean the unique action at time t for which ⇡⇤ ⇠ (a♣h<t) = 1. That is the exploitative action.

The most interesting feature of Inq is how it gets distracted by the opportunity to explore. Inq explores to learn. An agent has learned from an observation if its belief distribution w changes significantly after making that observation. If the belief distribution has hardly changed, then the observation was not very informative. The typical information-theoretic measure for how well a distribution Q approximates a distribution P is the KL-divergence, KL(P♣♣Q). Thus, a principled way to quantify the information that an agent gains in a timestep is the KL-divergence from the belief distribution at time t+1 to the belief distribution at time t. This is the rationale behind the construction of Orseau, et al.'s [2013] Knowledge Seeking Agent, which maximizes this expected information gain.

Letting h<t 2 Ht-1 and h0 2 H⇤ , the information gain at time t is defined:

Recall that w(⌫♣h) is the posterior probability assigned to ⌫ after observing h.

An m-step expedition, denoted ↵m, represents all contingencies for how an agent will act for the next m timesteps. It is a deterministic policy that takes history-fragments of length less than m and returns an action:

P↵m ⇠ (h<t+k♣h<t) is a conditional distribution defined for 0  k  m, which represents the conditional probability of observing h<t+k if the expedition ↵m is followed starting at time t, after observing h<t. Now we can consider the information-gain value of an m-step expedition. It is the expected information gain upon following that expedition:

At a time t, one might consider many expeditions: the one-step expedition which maximizes expected information gain, the two-step expedition doing the same, etc. Or one might consider carrying on with an expedition that began three timesteps ago.

Definition 1. At time t, the m-k expedition is the m-step expedition beginning at time t-k which maximized the expected information gain from that point. 1

Example expeditions are diagrammed in Figure 1.

Expeditions are functions which return an action given what has been seen so far on the expedition. The m-k exploratory action is the action to take at time t according to the m-k expedition:

Naturally, this is only defined for k < m↪ t, since the expedition function can't accept a history fragment of length ≥ m, and t - k must be positive. Note also that if k = 0, ht-k:t-1 evaluates to the empty string, ✏.

1 Ties in the argmax are broken arbitrarily.

The reason Inq doesn't ignore expeditions that started in the past is that Inq must have some chance of actually executing the whole expedition (for every expedition). If the probability of completing an expedition is 0, one cannot use it for a bound on Inq's belief-accuracy.

Definition 2. Let ⇢(h<t↪m↪ k) be the probability of taking the m-k exploratory action after observing a history h<t.

where ⌘ is an exploration constant.

Note in the definition of ⇢(h<t↪m↪ k) that the probability of following an expedition goes to 0 if the expected information gain from that expedition goes to 0. The first term in the min ensures the probabilities will not sum to more than 1. The total probability of exploration is defined:

The feature that makes Inq inquisitive is that ⇢(h<t↪m↪ k) is proportional to the expected information gain from the mk expedition, V IG(↵IG m↪k (h<t)↪ h<t-k). Note that completing an m-step expedition requires randomly deciding to explore in that way on m separate occasions. While this may seem inefficient, if the agent always got boxed into long expeditions, the value of its policy would plummet infinitely often.

Finally, Inq's policy ⇡ , defined in Algorithm 1, takes the m-k exploratory action with probability ⇢(·↪ m↪ k), and takes the exploitative action otherwise. 2

Algorithm 1 Inquisitive Reinforcement Learner's Policy ⇡

• 1: while True do
• 2: calculate ⇢(h<t↪m↪ k) for all m and for all k < min¶m↪ t♦
• 3: take action aIG m↪k (h<t) with probability ⇢(h<t↪ m↪ k)
• 4: take action a⇤ (h<t) with probability 1 - β(h<t)

4 Strong Asymptotic Optimality

Here we present our central result: that the value of ⇡ approaches the optimal value. We present the theorem, motivate the result, and proceed to the proof. We recommend the reader have Appendix A at hand for quickly looking up definitions and notation.

2 This algorithm is written in a simplified way that does not halt, but if a real number in [0↪ 1] is sampled first, the actions can be assigned to disjoint intervals successively until the sampled real number lands in one of them.

Before presenting the theorem, we clarify an assumption, and define the optimal value. We call the true environment θ, and we assume that θ 2 M. For M the class of computable environments, this is a very unassuming assumption. The optimal value is simply the value of the optimal policy with respect to the true environment:

Recall also that we have assumed the agent has a bounded horizon in the sense that 8" 9m 8t : Γt+m◁Γt  ". The Strong Asymptotic Optimality theorem is that under these conditions, the value of Inq's policy approaches the optimal value with probability 1, when actions are sampled from Inq's policy and observations and rewards are sampled from the true environment θ.

Theorem 3 (Strong Asymptotic Optimality). As t !1,

where θ 2 M is the true environment.

For a Bayesian agent, uncertainty about on-policy observations goes to 0. Since "on-policy" for Inq includes, with some probability, all maximally informative expeditions, Inq eventually has little uncertainty about the result of any course of action, and can therefore successfully select the optimal course. For any fixed horizon, Inq's mixture measure ⇠ approaches the true environment θ.

We use the following notation for a particular KLdivergence that plays a central role in the proof:

This quantifies the difference between the expected observations of two different environments that would arise in the next n timesteps when following policy ⇡. KLh<t↪1 denotes the limit of the above as n !1, which exists by [Orseau et al., 2013, proof of Theorem 3].

In dealing with the KL-divergence, we simplify matters by asserting that 0 log 0 := 0, and 0 log 00 := 0.

We begin with a lemma that equates the information gain value of an expedition with the expected prediction error. The KL-divergence on the right hand side represents how different ⌫ and ⇠ appear when following the expedition in question.

Lemma 4.

Proofs of Lemmas appear in Appendix B.

Recall that w(⌫♣h<t) is the posterior weight that Inq assigns to the environment ⌫ after observing h<t. We show that the infimum of this value is strictly positive with probability 1.

Next, we show that every exploration probability ⇢(h<t↪m↪ k) goes to 0. From here, all "w.p.1" statements mean with P⇡ θ -probability 1, if not otherwise specified.

Lemma 6.

The essence of the proof is that with a finite-entropy prior, there is only a finite amount of information to gain, so the expected information gain (and the exploration probability) goes to 0.

Next, we show that the total exploration probability goes to 0:

Lemma 7.

Lemma 8 shows that the probabilities assigned by ⇠ converge to those of θ.

Lemma 8. 8m 2 N, ht:t+m-1 2 Hm, ↵m : Sm-1 i=0 Hi !

The proof of Lemma 8 roughly follows the following argument: if all exploration probabilities go to 0, then the informativeness of the maximally informative expeditions goes to 0, so the informativeness of all expeditions goes to 0, meaning the prediction error goes to 0.

Finally, we prove the Strong Asymptotic Optimality Theorem: V ⇤ θ (h<t) -V ⇡ θ (h<t) ! 0 with P⇡ θ -prob. 1.

Proof of Theorem 3. Let " > 0. Since the agent has a bounded horizon, there exists an m such that for all t, Γt+m Γt  ". Recall

Using the m from above, let

Since rt 2 [0↪ 1],

We continue from there:

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

(a), (e), (f), and (g) all hold with probability 1. (a) follows from Lemma 8: for all m, P⇡⇠ (·♣h<t) ! P⇡θ (·♣h<t) for all conditional probabilities of histories of length m, with probability 1, and the countable sum is bounded (by Γt). (b) follows from adding more non-negative terms to the sum. (c) follows ⇡⇤ ⇠ being the ⇠-optimal policy, and therefore it accrues at least as much expected reward in environment ⇠ as ⇡⇤θ does. (d) follows from P1k=t+m γk◁Γt = Γt+m◁Γt  ", and rt 2 [0↪ 1]. (e) follows from Lemma 8 just as (a) did. (f) follows because the product in the denominator is the probability that ⇡ mimics ⇡⇤ ⇠ for m consecutive timesteps, and by Lemma 7 there is a time after which this probability is uniformly strictly positive. (g) follows from Lemma 7: β(h<k) ! 0 with probability 1. (h) follows from adding more non-negative terms to the sum. Finally, (i) follows from the value being normalized to [0↪ 1] by Γt.

8δ > 0 9" > 0↪ "0 > 0 : 4" + ( 1 (1-"0 )m - 1) < δ. Letting T = max¶T1↪ T2↪ T3↪ T4♦, we can combine the equations above to give

Strong Asymptotic Optimality is not a guarantee of efficacy; consider an agent that "commits suicide" on the first timestep, and thereafter receives a reward of 0 no matter what it does. This agent is asymptotically optimal, but not very useful. In general, when consideringmany environmentswith many different "traps," bounded regret is impossible to guarantee [Hutter, 2005], but one can still demand from a reinforcement learner that it make the best of whatever situation it finds itself in by correctly identifying (in the limit) the optimal policy.

We suspect that strong asymptotic optimality would not hold if Inq had an unbounded horizon, since its horizon of concern may grow faster than it can learn about progressively more long-term dynamics of the environment. Going more into the technical details, let ∆kt be, roughly "at time t, how much does ⇠ differ from θ regarding predictions about the next k timesteps?" A lemma in our proof is that 8k limt!1∆kt = 0, but this does not imply, for example, that limz!1∆zz = 0. If the horizon which is necessary to predict is growing over time, Inq might not be strongly asymptotically optimal.

Indeed, we tenuously suspect that it is impossible for an agent with an unbounded time horizon to be strongly asymptotically optimal in the class of all computable environments. If that is true, then the assumptions that our result relies on (namely that the true environment is computable, and the agent has a bounded horizon) are the bare minimum for strong asymptotic optimality to be possible.

Inq is not computable; in fact, no computable policy can be strongly asymptotically optimal in the class of all computable environments (Lattimore, et al. [2011] show this for deterministic policies, but a simple modification extends this to stochastic policies). For many smaller environment classes, however, Inq would be computable, for example if M is finite, and perhaps for decidable M in general. The central result, that inquisitiveness is an effective exploration strategy, applies to any Bayesian agent.

5 Experimental Results

We compared Inq with other known weakly asymptotically optimal agents, Thompson sampling and BayesExp [Lattimore and Hutter, 2014a], in the grid-world environment using AIXIjs [Aslanides, 2017] which has previously been used to compare asymptotically optimal agents [Aslanides et al., 2017]. We tested in 10 ⇥ 10 grid-worlds, and 20 ⇥ 20 gridworlds, both with a single dispenser with probability of dispensing reward 0▷75; that is, if the agent enters that cell, the probability of a reward of 1 is 0.75. Following the conventions of [Aslanides et al., 2017] we averaged over 50 simulations, used discount factor γ = 0▷99, 600 MCTS samples, and planning horizon of 6. The planning horizon restricts m, and the number of MCTS samples is an input to ⇢UCT [Silver and Veness, 2010], which we use instead of expectimax. The algorithm for the approximate version of Inq is in Appendix C.

The code used for this experiment is available online at https: //github.com/ejcatt/aixijs, and this version of Inq can be run in the browser at https://ejcatt.github.io/aixijs/demo.html#inq. We found that using small values for ⌘, specifically ⌘  1 worked well. For our experiments we chose ⌘ = 1.

In the 10 ⇥ 10 grid-worlds Inq performed comparably to both BayesExp and Thompson sampling. However in the 20⇥20 grid-worlds Inq performed comparably to BayesExp, and outperformed Thompson sampling. This is likely because when the Thomspon Sampling Agent samples an environment with a reward dispenser that is inaccessible within its planning horizon, the agent acts randomly rather than seeking new cells. This is contrast to Inq and BayesExp which always have an incentive to explore the frontier of cells that have not been visited. This is especially relevant in the larger grid where the Thomspon sampling agent is more likely to act as if the dispenser is deep in uncharted territory, rather than nearby. In a grid-world, good exploration is just about visiting new states, which both Inq and BayesExp successfully seek.

6 Conclusion

We have shown that it is possible for an agent with a bounded horizon to be strongly asymptotically optimal in the class of all computable environments. No existing RL agent has as strong an optimality guarantee as Inq. The nature of the exploration regime that accomplishes this is perhaps of wider interest. We formalize an agent that gets distracted from reward maximization by its inquisitiveness: the more it expects to learn from an expedition, the more inclined it is to take it.

We have confirmed experimentally that inquisitiveness is a practical and effective exploration strategy for Bayesian agents with manageable model classes.

There are two main avenues for future work we would like to see. The first regards possible extensions of inquisitiveness: we have defined inquisitiveness for Bayesian agents with countable model-classes, but inquisitiveness could also be defined for a Bayesian agent with a continuous model class, such as a Q-learner using a Bayesian Neural Network. The second avenue regards the theory of strong asymptotic optimality itself: is Inq strongly asymptotically optimal for more farsighted discounters? If not, can it be modified to accomplish that? Or is it indeed impossible for an agent with an unbounded horizon to be strongly asymptotically optimal in the class of computable environments? Answers to these questions, besides being interesting in their own right, will likely inform the design of tractable exploration strategies, in the same way that this work has done.

Acknowledgements

This work was supported by the Open Philanthropy Project AI Scholarship and the Australian Research Council Discovery Projects DP150104590.