Introduction

The goal of this post is to give a summary of classical reinforcement learning theory that primes the reader to learn about infra-Bayesianism, which is a new framework for reinforcement learning that aims to solve problems related to AI alignment. We will concentrate on basic aspects of the classical theory that have analogous concepts in infra-Bayesianism, and explain these concepts using infra-Bayesianism conventions. The more technical proofs are contained in the proof section.

For the first part of this sequence and for links to other writings, see What is Inadequate about Bayesianism for AI Alignment: Motivating Infra-Bayesianism.

One special case of reinforcement learning is the case of stochastic bandits. For example, a bird may have a choice of three levers. When the bird steps on a lever, either some tasty seeds come tumbling out of a feeder or nothing happens. A mechanical system that the bird cannot observe delivers these seeds according to probabilities that are fixed for each lever.

An all-knowing bird can devise a strategy to maximize the expected number of seeds they will obtain. Some natural questions include: If a bird doesn’t have any knowledge of the mechanical system, what is a good algorithm to follow to learn how to gather lots of seeds? How much worse off is this bird compared to the all-knowing bird? These are the types of questions that can be mathematically formalized and studied using stochastic bandits.

Actions, Observations, and Environments

The formal set-up for reinforcement learning starts with time-steps, actions, observations, and environments:

• At discrete time-steps indexed by natural numbers, an agent performs an action $a$, chosen from a set $A$ of actions.
• The agent then receives an observation from a set $O$ of observations.

Assumption: Finiteness of actions and observations

For simplicity, we assume that the set of actions and the set of observations are both finite and non-empty.

The time-horizon of a problem is the number of time-steps after which the alternation of action and observations terminates, which may be finite or infinite. In the infra-Bayesianism sequence, time-horizons are assumed to be infinite, which is arguably the more realistic assumption for modeling open-world agents. We will similarly assume infinite time-horizons, in contrast to episodic reinforcement learning, in which the time-horizon is finite and the action-observation process sequentially repeats in episodes, such as in repeated games of Go.

In the bird example from the introduction, we have

Time-steps correspond to sequential opportunities to step on levers.

An element of the cartesian product $A\times O$ is a pair of an action $a$ and the following observation $o$, which is written as $(a,o)$.

Definition: Histories and destinies

The set $(A\times O{)}^{\ast }$ denotes the set of finite sequences of action-observation pairs. Elements of $(A\times O{)}^{\ast }$ are called histories.

The set $(A\times O{)}^{\omega }$ denotes the set of infinite sequences of action-observation pairs. Elements of $(A\times O{)}^{\omega }$ are called destinies.

Cantor's diagonal argument proves that the set of infinite binary sequences is an uncountable set. If either $A$ or $O$ has at least two elements, then there exists a bijection from a subset of $(A\times O{)}^{\omega }$ to the set of infinite binary sequences, and thus $(A\times O{)}^{\omega }$ is also uncountable. For example, if $A$ contains $a_0$ and $a_1$ and $O$ contains $o$, then the subset of $(A\times O{)}^{\omega }$ of sequences with actions equal to $a_0$ or $a_1$ and observations all equal to $o$ is in bijection with the set of infinite binary sequences.

The levers in the bird example are what we intuitively might want to call the “environment,” which responds to agent actions by sending back or providing observations. An environment is formally defined as follows:

Definition: Probabilistic environment

A probabilistic environment $\mu :(A\times O{)}^{\ast }\times A\to \Delta O$ is a function that takes in a history and an action and returns a probability distribution over observations.

Here is a concrete example of an environment. Let $h\in (A\times O{)}^{\ast }$ denote a history. Define $\mu :(A\times O{)}^{\ast }\times A\to \Delta O$ by 

We’ll use the notation $\mu (o|h,a)$ to denote the probability of $o\in O$ according to the distribution that the environment outputs when given $(h,a)\in (A\times O{)}^{\ast }\times A.$

Notice that in this example, $\mu$ does not depend on $h.$ However, in full generality, an environment may depend on $h$. For example, a lever could give seeds with probability 1 only if it was not the most recently visited lever, and otherwise it could give seeds with probability 0.5.

Formalizing Preferences: Loss Functions and Momentary Loss

One motivation for reinforcement learning as a framework for artificial intelligence is that many—or perhaps all—"intelligence-requiring" tasks can be formulated by means of an agent who prefers some observations over others and seeks to take actions that bring about their preferred observations. This preference is captured numerically with loss or reward functions.

For example, we can define a function $L:O\to R$ that captures the bird’s preference for seeds over no seeds and thus the lost value when no seeds are received by:

This is an example of a loss function.

Definition: Loss function

A deterministic loss function is a function $L$ of type $(A\times O{)}^{\ast }\to [0,1]$. For a given history $h$ ending in observation $o\in O,$ $L\left(h\right)$ is the momentary loss of $o.$

Rather than focusing on lost value, we could measure gained value with a reward function $R:O\to R$ such that $R\left(\text{Seeds}\right)=1$ and $R\left(\text{No Seeds}\right)=0.$ In this post, we will use loss functions, but everything can be reformulated in terms of reward functions.

Total loss: What is an agent optimizing for?

Imagine that in the bird example, a bird steps on Lever 3, and receives seeds. This gives some evidence that Lever 3 is a good choice, but a bird would be much happier in the long run knowing that, in expectation, Lever 1 delivers more seeds. Any such bird has a tradeoff between exploring to gain a better idea of how good the various levers are versus exploiting their current knowledge, i.e. stepping on the lever that looks best with the current information. This is called the exploration versus exploitation tradeoff.

Suppose a bird is famished, and therefore cares strongly about obtaining seeds in the short-term. This bird might step on the lever that looks best under the current information. As a result, a famished bird might not discover a better lever, getting stuck stepping on a worse lever forever, exploiting too much and exploring too little. So, “famished bird” doesn’t seem like the best model of a rational learning agent.

Suppose the time-horizon is theoretically infinite, but the bird is mortal and has no knowledge about when they will die. Such a bird should value seeds in the short-term and the long-term unequally. Furthermore, a bird will get hungry without enough seeds in the short-term. This motivates the notion of discounting, which is weighting the momentary loss of observations unequally over time when it comes to calculating the sum of the momentary losses. This sum is defined as total loss.

Definition: Total loss of a history (with geometric time discount)

Let $\gamma \in [0,1)$ and let $N$ denote the time-horizon, which may be infinite. The total loss of a given history $(a_t,o_t{)}_{t=0}^N$ with time discount $\gamma$ is defined by $L^{\gamma }\left(\right(a_t,o_t{)}_{t=0}^N)=(1-\gamma \left){\sum }_{t=0}^N{\gamma }^{t}L\right(o_t).$

Note that the coefficient $(1-\gamma )$ on the total loss ensures that it is upper-bounded by 1. This fact is used in various proofs. The time discount is especially important when $N$ is infinite, since without it, the total loss of various histories can diverge, making it impossible to meaningfully compare them. So, the time-discount is (1) a choice that makes strategies more or less farsighted, and (2) a mathematical trick that ensures that the total loss is finite.

Formalizing “Strategies”: Policies

We eluded that a bird could develop a strategy for gathering lots of seeds; such a strategy is formally called a policy. For example, one valid, albeit bad, policy is to choose Lever 3 with probability one without regard to past actions and observations.

As another example, before the bird has stepped on any levers, they could flip a coin to decide whether to step on Lever 1 or 2. At later time-steps, the bird could calculate the past percentage of times that each lever yielded seeds, and step on the lever with the best seed percentage 2/3 of the time, taking a random action otherwise. In the case of ties, the bird could also make a random choice.

By using the seed percentages, which are determined by past actions and observations, this strategy is a function of $(A\times O{)}^{\ast }.$ The range is $\Delta A$ because the policy outputs a probability distribution over actions. Formally defined, a policy is exactly a function of this type:

Definition: Policy

A policy is a function $\pi :(A\times O{)}^{\ast }\to \Delta A$. We denote the set of policies by $\Pi$. We say that a policy is deterministic if it can be written as $\pi :(A\times O{)}^{\ast }\to A$. Otherwise, the policy is said to be stochastic.

Real-valued sequences are formally defined as functions from $N$ to $R,$ with the notation $(a_0,a_1,\dots )$ meaning that $a_i\in R$ is the image of $i\in N$. For example, a sequence of zeros is the constant function that sends every natural number to zero. The set of real-valued-sequences can then be written as ${\prod }_{N}R:=\{\alpha :N\to R\},$ which is known as the product of $R$ over $N$. In the same way, the set of stochastic policies is the product space ${\prod }_{(A\times O{)}^{\ast }}\Delta A.$

Lemma 2 below states that the set of policies can be given a topology in which it is compact. For our purposes, topology provides generalized notions of continuity and convergence in spaces that are not the real numbers. Compactness is a significant property for a topological space to have in the context of optimization, because if a space is compact, then any continuous function from that space to the real numbers attains both a maximum and a minimum in the space.

The proof of Lemma 2 depends on Lemma 1, which states that $\Delta A$ is a compact metric space. In the infra-Bayesianism sequence, the metric used on $\Delta A$ is the Kantorovich-Rubinstein metric, but in the case when $A$ is finite, the Kantorovich-Rubinstein metric is equivalent to a more simple metric known as the total-variation metric.

Definition: Total-variation metric

Let $P_1$ and $P_2$ denote probability distributions over a finite set $X.$ The total variation metric, which we denote by $d_{TV}$ is defined by $d_{TV}(P_1,P_2):=\frac{1}{2}{\sum }_{x\in X}|P_1\left(x\right)-P_2\left(x\right)|.$ 

It is straightforward to check that $d_{TV}$ satisfies the definition of a metric. As a simple case, if $X=\{0,1\}$, then given $P_1$ and $P_2$ in $\Delta X,$ $d_{TV}(P_1,P_2)=\frac{1}{2}\left(|P_1\right(0)-P_2(0)|+|P_1(1)-P_2(1\left)|\right)$ but $|P_1\left(1\right)-P_2\left(1\right)|=|1-P_1\left(0\right)-(1-P_2(0\left)\right)|=|P_1\left(0\right)-P_2\left(0\right)|.$ Observe then that in this simple example, $d_{TV}(P_1,P_2)=|P_1\left(0\right)-P_2\left(0\right)|.$

Lemma 1: Compactness of $\Delta A$ under the total-variation metric
If $A$ is finite, then the set $\Delta A$ is compact under the total-variation metric.

Proof:  By assumption, $A$ is finite, so we can enumerate $A$ as $A=\{a_1,a_2,\dots ,a_n\}.$Elements of $\Delta A$, which are probability distributions over $A,$ can be written as vectors in $R^n$ of the form $(x_1,x_2,\dots ,x_n)$ such that $x_i$ denotes the probability of $a_i.$ By definition of a probability distribution, ${\sum }_{i=1}^n{x}_i=1$ and $x_i\ge 0$ for all $i.$ Therefore, there is a bijection between $\Delta A$ and the standard $(n-1)-$dimensional simplex, which is defined as the set${\Delta }_{n-1}:=\left\{\right(x_1,x_2,\dots ,x_n)\in R^n:{\sum }_{i=1}^n{x}_i=1,x_i\ge 0\text{for all}i\}.$ (See Figure 1 for a depiction of the standard 1-dimensional and 2-dimensional simplices.)

The total-variation metric is induced by the Euclidean norm on $R^n,$ and thus both induce the same topology on $\Delta A$. Under the Euclidean metric, the $n$-simplex is compact by the Heine-Borel theorem since it is closed and bounded. Thus, $\Delta A$ is compact. $\square$

Visualizing $\Delta A$ as ${\Delta }_{n-1}$ as in Figure 1, computing the total-variation distance between two elements of $\Delta A$ can be conceptualized as locating the corresponding points in $R^n,$projecting the points to each of the coordinate axes, then connecting the projections with a line segment and computing $1/2$ of the sum of the line segment lengths. As the earlier calculation (and Euclidean geometry) suggest, in the special case of ${\Delta }_1,$ the two segments drawn for any two elements of ${\Delta }_1$ will have the same length.

Lemma 2: Compactness of the set of policies
The set of policies $\Pi$ is compact with respect to the product topology.

Proof: By Lemma 1, $\Delta A$ is compact. Then $\Pi ={\prod }_{(A\times O{)}^{\ast }}\Delta A$ is compact with respect to the product topology by Tychonoff’s Theorem, a theorem that states that the product of compact topological spaces is compact with respect to the product topology. $\square$

Lemma 2 remains true if we restrict attention to the set of deterministic policies.

Expected Total Loss of a Policy

Suppose we have a policy, an environment, and a history of the form: “Lever 1, No seeds.” How likely is this history to occur compared to other histories of length one? This question is fundamental to comparing various policies. To calculate the answer, we would want to know:

• The probability of stepping on Lever 1 at the start according to the policy
• The probability of no seeds conditional on stepping on Lever 1 according to the environment

For example, consider the previously described policy:

Before the bird has stepped on any levers, they could flip a coin to decide whether to step on Lever 1 or 2. At later time-steps, the bird could calculate the past percentage of times that each lever yielded seeds, and step on the lever with the best seed percentage 2/3 of the time, taking a random action otherwise. In the case of ties, the bird could also make a random choice.

We will examine how this policy interacts with the environment given by:

Let $ϵ$ denote the empty history, so that $\pi \left(\text{Lever 1}|ϵ\right)$ denotes the probability that Lever 1 is the first action. Using the definition of conditional probability, the probability of “Lever 1, no seeds” among length-one histories is:

We could repeat this process to calculate the probability of any history of length one: the policy and environment determine everything we need to do that. The resulting distribution over histories of length one is represented as the tree in Figure 2. 

We can further calculate the probability of a specific history of length $l+1>1$ among all length-$(l+1)$ histories. By the chain rule of probabilities, $P\left(\right(a_o,o_o),...,(a_l,o_l\left)\right)$ is given by 

Note that for all $t,$ $P(a_t|a_0,o_0,...,a_{t-1},o_{t-1})$ is determined by a chosen policy, whereas $P(o_t|o_0,a_0,...,a_t)$ is determined by a given environment. So pairing together a policy and an environment produces a distribution over histories of a fixed length.^[1] We denote all such distributions by ${\mu }^{\pi }$, since the length will hopefully always be clear from context. This is formally stated in the next definition. As a convention, a sequence written with an ellipsis such that the final index is negative denotes an empty sequence.

Definition: Probability distributions on histories induced by a policy and environment

Let $(a_t,o_t{)}_{t=0}^l\in (A\times O{)}^{\ast }$. The probability distribution ${\mu }^{\pi }\in \Delta (A\times O{)}^{\ast }$ is defined by ${\mu }^{\pi }\left(\right(a_t,o_t{)}_{t=0}^l)={\prod }_{t=0}^l\pi (a_t|a_0,o_0,\dots ,a_{t-1},o_{t-1}\left)\mu \right(o_t|a_0,o_0,\dots ,a_t).$ 

Recall that we previously defined the total loss of a history $h=(a_t,o_t{)}_{t=0}^N$ by $L^{\gamma }\left(h\right)=(1-\gamma ){\sum }_{t=0}^N{\gamma }^{t}L\left(o_t\right)$. Since ${\mu }^{\pi }$ is a distribution over the domain of $L^{\gamma },$ we can now calculate the expected total loss of a policy for a given environment.

Definition: Expected total loss of policy

The expected total loss of a policy $\pi$ in the environment $\mu$ is $E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]$.

The distribution ${\mu }^{\pi }$ gives another way to describe an environment: For a fixed environment, we can construct a function $\tilde{\mu }$ that takes in a policy and outputs a probability distribution over histories. This function is an example of a Markov kernel. We will repeat a similar construction to define crisp causal laws in the next post.

Optimal and Bayes-Optimal Policies

In this section, we will pin down what we mean by a “best” policy, which provides a benchmark to which we can compare other policies. One choice is to compare the performance of an agent learning about the environment to a hypothetical agent who “knows” the environment ahead of time and therefore acts as if to achieve minimum loss in expectation. The policy of this “all-knowing” agent is the optimal policy. Given uncertainty about the true environment, we could consider the policy that achieves minimum loss in expectation with respect to a distribution over possible environments and with respect to the environments. This is called the Bayes-optimal policy.

Definition: Optimal policy for an environment $\mu$

Let an environment $\mu$ be fixed. We say that ${\pi }^{\ast }$ is an optimal policy for $\mu$ if ${\pi }^{\ast }\in {\text{arg min}}_{\pi \in \Pi }{E}_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]$.

So, the optimal policy for a given environment is the policy that minimizes the expected total loss in that environment. There is something to prove, which we do later in this section, in order to say that the optimal policy exists, namely that 

Note that the optimal policy isn’t necessarily unique, as different observations could have the same momentary loss, or different actions could lead to a certain observation with equal probability.

If you understand the expression 

 you can skip the next example and go straight to the section where we prove that the optimal policy is well-defined. Otherwise, read the next section to understand the notation through an example.

Example of an optimal policy in the HeavenHell environment:

To understand the definition of the optimal policy, we’ll walk through an example of an optimal policy for the HeavenHell environment described by Marcus Hutter in Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability.

Let the set of actions be $A=\{l,r\}$ for left and right and $O=\{V,H\}$ for heaven and hell. The loss function is defined by $L\left(V\right)=0$ and $L\left(H\right)=1.$ We will use an infinite time horizon. If the first action is $l$, then the agent is in heaven and receives loss of zero at each time step forever. If the first action is $r$, then the agent is in hell and receives loss of one at each time step forever. 

One optimal policy ${\pi }^{\ast }$ is to go left with probability one at every time step, which is denoted by ${\pi }^{\ast }\left(l|h\right)=1$ and ${\pi }^{\ast }\left(r|h\right)=0$ for all $h\in (A\times O{)}^{\ast }.$

Given any history that starts with $l$, at every time-step, the environment outputs a distribution over $\{V,H\}$ that is one at $V$. So ${\mu }^{{\pi }_{\mu }^{\ast }}$ is a distribution that is one on histories of the form $(l,V,l,V,...)$ and zero otherwise.

The loss of any history $h$ starting with $l$ is $L^{\gamma }\left(h\right)=(1-\gamma ){\sum }_{t=0}^{\infty }0\cdot {\gamma }^t=0$. So the expected total loss is $E_{h\sim {\mu }^{{\pi }_{\mu }^{\ast }}}\left[L^{\gamma }\right(h\left)\right]=1\cdot 0=0.$ Since expected loss is bounded between 0 and 1, ${\pi }^{\ast }$ is an optimal policy.

We can check that the loss of any history that starts with $r$ is $(1-\gamma ){\sum }_{t=0}^{\infty }1\cdot {\gamma }^t=(1-\gamma )\frac{1}{1-\gamma }=1$. So then a policy ${\pi }_p$ that says to go right with probability $p\in (0,1]$ at the first time-step has expected loss $E_{h\sim {\mu }^{{\pi }_p}}\left[L^{\gamma }\right(h,a\left)\right]=1\cdot p+(1-p)\cdot 0=p>0.$

Existence of an optimal policy

Proposition 1: Existence of an optimal policy

If $A$ and $O$ are finite, an optimal policy for a given environment $\mu$ exists; namely, ${\text{arg min}}_{\pi \in \Pi }{E}_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]\ne \varnothing .$ Furthermore, the optimal policy can be chosen to be deterministic.

We start this section with a summary of the main idea of the existence proof. The full proof is in the proof section. A restatement of Proposition 1 is that the function $\pi \mapsto E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]$ attains a minimum. The usual technique to show that a function attains a minimum or maximum over some domain is to prove that the domain is compact and the function is continuous: then the result follows from the fact that a continuous function over a compact domain attains a maximum and a minimum. We have compactness of $\Pi$ by Lemma 2.

To show continuity, we take a convergent sequence ${\pi }_n\to \pi \in \Pi$, aiming to show that $E_{h\sim {\mu }^{{\pi }_n}}\left[L^{\gamma }\right(h\left)\right]\to E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]$ as $n\to \infty .$ In other words, we need to show that for large enough $n,$ $|E_{h\sim {\mu }^{{\pi }_n}}\left[L^{\gamma }\right(h\left)\right]-E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]|$ becomes arbitrarily small. The key idea of the proof for the infinite time-horizon case is to define $L^{\gamma }{|}_N$ for $N\in N$ as 

which we can conceptualize as the restriction of $L^{\gamma }$ to a finite time-horizon. We can show that uniformly over all probability distribution, the expectation of $L^{\gamma }{|}_N$ gets close to the expectation of $L^{\gamma }$ as $N$ becomes large. Furthermore, for any fixed $N<\infty ,$ $|E_{h\sim {\mu }^{{\pi }_n}}\left[L^{\gamma }{|}_N\right(h\left)\right]-E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }{|}_N\right(h\left)\right]|$ becomes arbitrarily small as $n$ becomes large. By applying the triangle inequality, these two statements are enough to complete the proof for infinite time-horizons.

It is natural to do an approximation argument using a finite time horizon because of the definition of the product topology. Recall that $\Pi ={\prod }_{(A\times O{)}^{\ast }}\Delta A$. A set is open under the product topology on $\Pi$ if it is the product of open sets in $\Delta A$ not equal to $\Delta A$ in finitely many components. Convergence of ${\pi }_n\to \pi$ in the product topology then means that for all open sets $U$ containing $\pi$, we can find find an $M$ large enough such that for all $n\ge M,{\pi }_n\in U$. For any open set $U$, this only puts a condition on ${\pi }_n$ that is relevant to finitely many histories because $U$ is not equal to $\Delta A$ in finitely many components.

Bayes Optimal Policy

Since the problem of reinforcement learning is about agents learning in an unknown environments, we now define a different notion of optimality — the Bayes optimal policy — that is relevant when we have a prior over environments rather than certainty about the true environment. To simplify the definition, we can write a prior over environments as a new environment called a Bayes mixture of environments.

Bayes Mixture of Environments

Consider for example an environment, HeavenHell Opp $\left(H\text{\&}H\text{Opp}\right),$ which does the opposite of HeavenHell $\left(H\text{\&}H\right).$ A possible prior $\zeta$ over these environments specifies probability 0.4 of being in HeavenHell and probability 0.6 of being in HeavenHell Opp. This prior represents a new environment, ${\mu }_{\zeta },$ that takes in a history and action and returns a distribution over observations in the following way.

Given a history, Bayes' rule produces a posterior distribution over the environments. For example, given the history $(l,V),$ the probability of $H\text{\&}H$ is 

This calculation can be conceptualized using the tree in Figure 3. To calculate $p(l,V|H\text{\&}H),$ we use the path starting at $H\text{\&}H$ and ending at $V.$ To calculate $p(l,V),$ we start from the base node of the tree, and find all paths that go through $l$ then $V.$ We then sum together the probabilities of these paths, which gives a weighted sum with weights determined by the prior. The value of $p\left(H\text{\&}H\right)$ is determined by the prior $\zeta .$

Observe that this calculation agrees with the fact that the history $(l,V)$ is impossible in $H\text{\&}H\text{Opp}.$

Now we define the Bayes optimal policy with respect to a prior over environments.

Definition: Bayes optimal policy

Let $\zeta$ be a prior over environments, which can be written as an environment ${\mu }_{\zeta }$. A policy ${\pi }_{\zeta }^{\ast }$ is said to be Bayes optimal with respect to the prior $\zeta$ if it is the optimal policy for ${\mu }_{\zeta }.$ Equivalently, ${\pi }_{\zeta }^{\ast }\in {\text{argmin}}_{\pi \in \Pi }{E}_{\mu \sim \zeta }\left[E_{h\sim {\mu }^{\pi }}\right[L^{\gamma }\left(h\right)\left]\right]$.

The existence of the Bayes optimal policy given a prior over environments follows from the existence of the optimal policy for the environment formed out of that prior. Note that these optimality definitions depend on the choice of time-discount $\gamma .$ A Bayes-optimal family of policies is a set of policies that depend on $\gamma ,$ each of which are optimal for the corresponding $\gamma .$

Definition: Bayes-optimal family of policies

Let $\zeta$ be a prior over environments. A family of policies $\{{\pi }^{\gamma }{\}}_{\gamma \in [0,1)}$ is a Bayes-optimal family with respect to $\zeta$ if for all $\gamma \in [0,1),$ ${\pi }^{\gamma }$ is Bayes-optimal with respect to $\zeta$.

Regret and Bayesian Regret

One way to evaluate a policy given an environment is to measure the difference between the expected loss for that policy and the expected loss of the optimal policy. Informally speaking, this quantifies how much an agent “regrets” using a policy that is not the optimal one for some environment.

Definition: Regret of a policy $\pi$ with respect to an environment $\mu$
Let an environment $\mu$ and continuous loss function $L^{\gamma }$ be given, and let ${\pi }_{\mu }^{\ast }$ be the optimal policy. Then the regret of a policy $\pi$ is $\text{Reg}(\pi ,\mu ,L^{\gamma }):=E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]-E_{h\sim {\mu }^{{\pi }_{\mu }^{\ast }}}\left[L^{\gamma }\right(h\left)\right]$.

Since the optimal policy minimizes expected loss, an equivalent definition of the regret of a policy $\pi$ is $\text{Reg}(\pi ,\mu ,\gamma ):=E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]-{min}_{{\pi }^{\ast }\in \Pi }{E}_{h\sim {\mu }^{{\pi }^{\ast }}}\left[L^{\gamma }\right(h\left)\right]$. Note that regret is always nonnegative.

Similarly to how we define a Bayes optimal policy for a prior, Bayesian regret is defined for a prior over environments:

Definition: Bayesian regret of a policy $\pi$ given a prior $\zeta$ over environments (Bayes risk)
Let $\zeta$ denote a prior over environments and $L^{\gamma }$ denote a continuous loss function. Then the Bayesian regret of a policy $\pi$ is $\text{BReg}(\pi ,\zeta ,L^{\gamma }):=E_{\mu \sim \zeta }\text{Reg}(\pi ,\mu ,L^{\gamma }).$

In the next section, we will use regret and Bayesian regret to define a property of priors and classes of environments called learnability.

Traps and Learnability

Recall that $\gamma \in [0,1)$ is a time discount factor in the definition of the loss function. The closer $\gamma$ is to one, the slower the weights decay when proceeding through time. A time discount near one is called a low time-discount, since future rewards are weighted similarly to rewards at the start.

Different choices of time discounts result in different loss functions. Therefore, it might be desirable to construct a set of policies that depend on the time discount. This is denoted by a family of policies $\{{\pi }^{\gamma }{\}}_{\gamma \in [0,1)}$ that is indexed by $\gamma \in [0,1).$

Learning requires acquiring information and therefore takes time. One way to judge a time-indexed family of policies while taking this into account is to judge the performance of the policies as the time-discount goes to one. This is captured below in the definition of non-anytime learnability.

Low loss in the $\gamma$-to-one limit necessitates avoiding traps; in the case when total loss is normalized to be less than or equal to one, a trap is a state that forces the regret to be bounded away from zero. (In the case when total loss is not normalized, a trap is a state that forces the regret to grow linearly with time.)

An example of a trap is the hell state of HeavenHell and HeavenHell Opp, where the momentary regret is one at each time-step. There is no policy that can be used in both HeavenHell and HeavenHell Opp such that the regret of a policy goes to zero in the low-time-discount limit. In particular, we could only design a policy that has this property in one of these environments, but not both. To say that no such policy exists means that HeavenHell and HeavenHell Opp, when considered together as one class of environments, is not “learnable” to the agent, which we now define:

Definition: Non-anytime learnable class of environments
A class of environments (hypotheses) $\{{\mu }_i{\}}_{i\in I}$ is non-anytime learnable if there exists a family of policies ${\pi }^{\gamma }$ indexed by $\gamma \in [0,1)$ such that for all $i\in I$, ${lim}_{\gamma \to 1}\text{Reg}({\pi }^{\gamma },{\mu }_i,\gamma )=0$. In this case, we say that ${\pi }^{\gamma }$ learns the class of environments.

In this definition, “non-anytime” refers to the fact that we have a different policy for each time discount. The definition does not require that any particular element of the family is actually optimal in any of the environments. Instead, it requires that the family converges to optimal in all the environments as the time discount goes to one.

We can write an analogous definition for a learnable prior.

Definition: Non-anytime learnable prior over environments
A prior $\zeta$ over environments is non-anytime learnable if there exists a family of policies ${\pi }^{\gamma }$ indexed by $\gamma \in [0,1)$ such that ${lim}_{\gamma \to 1}\text{BReg}({\pi }^{\gamma },\zeta ,\gamma )=0$. In this case, we say that ${\pi }^{\gamma }$ learns the prior.

We now consider the connection between learnability of a class of environments to Bayes-optimality of a prior on that class. The condition on the prior is that it is non-dogmatic, defined as follows:

Definition: Non-dogmatic prior
A prior $\zeta$ on a countable class of environments $\{{\mu }_i{\}}_{i\in I}$ is non-dogmatic if for all $i\in I,$ $\zeta \left({\mu }_i\right)\ne 0.$

The next proposition states that if a countable class of environments is learnable, given any non-dogmatic prior over it, then any family of policies that is Bayes-optimal with respect to the prior must also learn the class. As is demonstrated in the proof (in the proof section), countability is an important hypothesis. The non-dogmatic prior condition is also essential because if the prior assigns probability zero to some environment, the performance of the family on that environment does not affect the Bayesian-regret; this means that the policy could perform arbitrarily badly with respect to that environment and still be Bayes-optimal.

Proposition 2: If a countable class of environments $\{{\mu }_i{\}}_{i\in I}$ is non-anytime learnable, then the Bayes-optimal family of policies for any non-dogmatic prior $\zeta$ on $\{{\mu }_i{\}}_{i\in I}$ learns the class.

Markov Decision Processes

A Markov decision process (MDP) is a commonly-used model for sequential decision making. In this section, we discuss how every environment can be modeled as an MDP in which the set of states is the set of histories from the domain of the environment.

Definition: Markov decision process

A Markov decision process $M$ is a tuple $M=(S,A,T,L,\gamma )$ where

$S$ is a set of states;

$A$ is a set of actions;

$T:S\times A\to \Delta S$ is a transition kernel;

$L:S\times A\to [0,1]$ is a momentary loss function; and

$\gamma \in [0,1)$ is a time discount.

Intuitively, the transition kernel of the MDP that models an environment must ensure that the agent can only transition to a history that is equal to a single observation appended to the end of the current history. Furthermore, the transition kernel should agree with the environment about the various probabilities of those valid transitions. To ensure this, the probability of a valid transition can be taken to be equal to the probability of the corresponding observation that is appended. This is formalized in the proof of the following proposition.

Proposition 3: Every probabilistic environment can be modeled as an MDP with at most countably infinitely many states.

Proof: Recall that a probabilistic environment is defined to be a function $\mu :(A\times O{)}^{\ast }\times A\to \Delta O$. Define $S=(A\times O{)}^{\ast },$ which is countable since by assumption, $A$ and $O$ are finite. Define $T:S\times A\to \Delta S$ by 

This is a valid transition kernel. $\square$

In the following post, we consider the infra-Bayesian analogues to the machinery we have developed so far.

Acknowledgements

I am grateful to Vanessa Kosoy for her valuable comments and suggestions on initial drafts. I also thank Vanessa and Alex Appel for addressing numerous questions, Hannah Gabor, whose feedback improved the writing and clarity of ideas, and Mateusz Bagiński for correcting several typos. 

1. ^{^}The space of destinies is a measurable space with respect to the cylindrical $\sigma -$algebra. By Carathéodory's extension theorem, there exists a unique probability measure on this space that agrees on cylinder sets with the probability measure on histories. For more detail, see Theorem 3.1 in Probability and Measure by Patrick Billingsley (1995) or remarks of Eilon Solan on page 8 of A Course in Stochastic Game Theory (2022).