Introduction

Credal sets, a special case of infradistributions^[1] in infra-Bayesianism and classical objects in imprecise probability theory, provide a means of describing uncertainty without assigning exact probabilities to events as in Bayesianism. This is significant because as argued in the introduction to this sequence, Bayesianism is inadequate as a framework for AI alignment research. We will focus on credal sets rather than general infradistributions for simplicity of the exposition.

Defining Credal Sets

Recall that the total-variation metric is one example of a metric on $\Delta X,$ the set of probability distributions over a finite set $X.$ A set is closed with respect to a metric if it contains all of its limit points with respect to the metric. For example, let $X_0=\{0,1\}.$ The set of probability distributions over $X_0$ is given by

There is a bijection between $\Delta X_0$ and the closed interval $[0,1],$ which is the map that sends a distribution to the probability of zero. More generally, recall from the proof of Lemma 1 in the preceding post, that if $X$ is a finite set with $n$ elements, then there is a bijection between $\Delta X$ and the closed $(n-1)-$simplex 

Consider the following subset of $\Delta X_0:$

The set $S_{(0,1)}$ is an open subset of $\Delta X_0$ in the same way that the open interval $(0,1)$ is an open subset of the closed interval $[0,1].$ (See Figure 1.) In particular, $S_{(0,1)}$ does not contain the distributions $P_0$ and $P_1$ defined by $P_0\left(0\right)=0$ and $P_1\left(0\right)=1,$ which are limit points of $S.$ For example, given $ϵ>0,$ the distribution $P_{ϵ}$ defined by $P_{ϵ}\left(0\right)=ϵ$ is an element $S$, and the total variation distance between $P_0$ and $P_{ϵ}$ is $d_{TV}(P_0,P_{ϵ})={max}_{x\in \{0,1\}}\left\{|P_0\right(x)-P_{ϵ}(x\left)|\right\}=ϵ.$ 

In contrast,

are all examples of closed subsets of $\Delta X_0.$

We now consider the meaning of convexity in this context.

Definition: Convex set of probability distributions

A convex combination of probability distributions $P_i$ is a linear combination ${\sum }_{i=1}^n{\alpha }_i{P}_i$ such that ${\alpha }_i\in R,$  ${\alpha }_i\ge 0,$ and ${\sum }_{i=1}^n{\alpha }_i=1.$ A set of probability distributions is convex if it closed under convex combinations.

If a distribution $P$ is written as a convex combination of a set of distributions, then it is called a mixture distribution. Note that the definition of a convex combination ensures that mixture distributions are indeed probability distributions. Sampling from the mixture distribution ${\sum }_{i=1}^n{\alpha }_i{P}_i$ can be thought of as first determining an index $i$ by sampling from the distribution $\tau$ over $\{1,...,n\}$ defined by $\tau \left(i\right)={\alpha }_i$ and then sampling from the corresponding $P_i.$

As defined above, $S_{[0,1/4]}$ and $S_{[3/4,1]}$ are convex sets, analogous to how $[0,1/4]$ and $[3/4,1]$ are convex subsets of $R$. However, $S_{[0,1/4]}\cup S_{[3/4,1]}$ is not a convex set. To see this, let $P_{1/4}\left(0\right)=1/4$ and $P_{3/4}\left(0\right)=3/4.$ Note that $P_{1/4}$ is an element of $S_{[0,1/4]}$ and $P_{3/4}$ is an element of $S_{[3/4,1]}.$ The distribution defined by $P_{1/2}\left(0\right)=1/2$ can be written as the mixture distribution $P_{1/2}=\frac{1}{2}{P}_{1/4}+\frac{1}{2}{P}_{3/4}.$ However, as shown in Figure 1, $P_{1/2}$ is not an element of  $S_{[0,1/4]}\cup S_{[3/4,1]},$ so $S_{[0,1/4]}\cup S_{[3/4,1]}$ is not closed under convex combinations. 

If a set of probability distributions is both closed and convex, it is called a credal set. Among the examples we have seen, $S_{[0,1/4]},$ $S_{[3/4,1]}$, and $\Delta X$ are credal sets. See Figure 2 for another example. Since $S_{[0,1/4]}\cup S_{[3/4,1]}$ fails to satisfy convexity, it is not a credal set. 

Definition: Credal set

Let $X$ be a set, and let $\Delta X$ denote the set of probability distributions over $X.$ A credal set over $X$ is a closed, convex subset of $\Delta X,$ where closedness is defined with respect to some metric on $\Delta X.$ The set of credal sets over $X$ is denoted by $\square X.$

Credal sets are a natural tool for describing situations in which uncertainty cannot be reduced to probabilities. These situations are said to have Knightian uncertainty^[2]. Knightian uncertainty is notably distinct from situations in which probabilities can be assigned with low confidence. 

For example, in Risk, Ambiguity, and the Savage Axioms (1961), Daniel Ellsberg writes of the "Knightian urn," an urn with 100 balls in which an observer is ignorant of the proportion of black and red balls. We would say that an observer of this urn has Knightian uncertainty with respect to the events of drawing either a red or black ball. Corresponding red to 0 and black to 1, this Knightian uncertainty can be captured by the credal set $\Delta X_0$ as above. On the other hand, an observer may gain partial information while remaining ignorant about the remaining possibilities, such as learning that there are no more than 25 red balls. The credal set $S_{[0,1/4]}$ captures this partial information. In this case, we would say that the observer then has Knightian uncertainty over the elements of this credal set.

Convexity is a natural condition in the presence of Knightian uncertainty. If an observer considers some distributions as all possible and furthermore does not hold any beliefs about which distributions are more likely than others, then they should also consider any mixture distribution as possible. When the possible set of distributions is finite, this is equivalent to taking the convex hull of a finite set of points, which yields a convex polytope. 

Furthermore, the decision rule discussed below makes the same recommendation for a set of probability distributions and its closed convex hull. Therefore, we can always without loss of generality assume that a set of distributions is a credal set.

Infrakernels

In machine learning classification, neural networks learn functions from sets (e.g. sets representing images) to probability distributions over possible classes; this kind of function of type $X\to \Delta Y$ for sets $X$ and $Y$ is called a probability kernel. In this case, X is called the source of the kernel and $Y$ is called the target of the kernel.

An infrakernel^[3] is the infra-Bayesian analogue of a probability kernel. A special case of infrakernels in which the target is a set of credal sets is called a crisp infrakernel.

Definition: Crisp infrakernel
Let $X$ be a topological space, and let $\square Y$ denote the set of credal sets over a set $Y$. A crisp infrakernel is a continuous function of type $X\to \square Y.$

For example, every continuous probability kernel is a crisp infrakernel since a single probability distribution is a credal set with one element.

An example of a crisp infrakernel that is not a probability kernel is shown in Figure 3. Let $X=\{\text{William},\text{Carl},\text{Amalie}\}$, and let $Y=\{0,1,2\}$, with the elements of $Y$ referring to numbers of cats. We can define $\kappa :X\to \square Y$ as follows: $\kappa \left(\text{William}\right)$ is the set containing only the distribution that is one at two, $\kappa \left(\text{Carl}\right)$ is the set of distributions that assign zero to two, and $\kappa \left(\text{Amalie}\right)$ is the set of all distributions over $Y.$ This infrakernel represents certainty that William has two cats and Carl does not have two cats, and complete uncertainty about how many cats Amalie has. Since $X$ is finite, $\kappa$ is automatically continuous.

Deterministic Versus Stochastic Policies

In the preceding post, we discussed stochastic policies, maps of the form $\pi :(A\times O{)}^{\ast }\to \Delta A$. Deterministic policies are a special case of stochastic policies, and can be written as partial functions of the form $\pi :(A\times O{)}^{\ast }\rightharpoonup A.$ By partial function, we mean that the domain of the policy $\pi$ is restricted to those histories consistent with it. We previously observed that under some mild assumptions in the classical setting, an optimal policy exists. Furthermore, the optimal policy may be chosen to be deterministic. As we argue below, deterministic policies can be represented by stochastic policies and thus from this point forward, we will assume that policies are deterministic.

To emulate a stochastic policy using a deterministic policy, an agent can choose an element of $\Delta A$ and use a random number generator (RNG) to sample it. The output of the RNG then dictates an action. An observation from the environment then follows as usual. To formalize this, if $A$ and $O$ are the sets of actions and observations respectively from the stochastic setting, we can define a new set of observations equal to $A\times O$. This new set records both the action dictated by the RNG and the usual observation that follows. The new action space would be $\Delta A,$ with each element of $\Delta A$ corresponding to an RNG that encodes the distribution.^[4]

Importantly, this allows the random number generator to be insecure, biased, or influenced by the environment. In comparison, assuming that the set of policies is stochastic implicitly invokes an assumption that the agent can access a source of true randomness that is inaccessible by the environment. The deterministic theory not only encompasses the stochastic theory, but it is also applicable to embedded agency and can be used to solve Newcombian problems.

Topologies on policies and destinies

In this section, we review several important topologies. These topologies are relevant to how we define credal sets over the set of destinies $(A\times O{)}^{\omega }$, as we require a notion of closure in the abstract space that is $\Delta (A\times O{)}^{\omega }.$

The topology on the set of deterministic policies

Recall that the set of deterministic policies $\Pi$ is a set of partial functions $\pi :(A\times O{)}^{\ast }\rightharpoonup A.$ The set of deterministic policies $\Pi$ can be written as a subset of the product space ${\prod }_{i\in (A\times O{)}^{\ast }}{A}_i$ where $A_i=A$ for all $i\in (A\times O{)}^{\ast }.$ 

We assume that $A$ is finite, and thus the natural topology on $A$ is the discrete topology. Then $\Pi$ is naturally endowed with the (subspace topology of the) product topology that comes from the topology on $A.$ This means that a basis element of the topology on $\Pi$ has the form ${\prod }_{i\in (A\times O{)}^{\ast }}{U}_i$ where $U_i\subseteq A$ for all $i\in (A\times O{)}^{\ast }$ and $U_i\subset A$ for only finitely many $i\in (A\times O{)}^{\ast }.$ An open set is then an arbitrary union of basis elements.

Recall from Lemma 2 of the preceding post that $\Pi$ is compact.

The topology on the set of destinies

The set of countably infinite histories $(A\times O{)}^{\omega }$, referred to as destinies, is a metric space under the metric $d(h,h^{\prime })={\gamma }^{t(h,h^{\prime })}$ where $\gamma \in (0,1)$ and $t(h,h^{\prime })$ is the time (index) of first difference between $h$ and $h^{\prime }.$ In the proof section, we show that $(A\times O{)}^{\omega }$ is compact under this metric. 

Lemma 1: Suppose $A$ and $O$ are finite. Then the set of destinies $(A\times O{)}^{\omega }$ is a compact metric space.

The topology on the set of credal sets over destinies

Recall that the total-variation distance between probability distributions $P_1$ and $P_2$ is given by $d_{TV}(P_1,P_2):=\frac{1}{2}{\sum }_{x\in X}|P_1\left(x\right)-P_2\left(x\right)|.$ A natural way to extend any metric on probability distributions to credal sets is to use the Hausdorff metric. The Hausdorff metric is a metric that can be defined on the closed, non-empty subsets of a metric space. When restricted to one-element sets, the Hausdorff metric is equivalent to the metric of the original space.

Definition: Hausdorff total-variation distance between credal sets
Let ${\Theta }_1$ and ${\Theta }_2\in \square X$ be two non-empty credal sets. For a credal set $\Theta \in \square X$ and distribution $\theta \in \Delta X,$ let $d(\theta ,\Theta ):={inf}_{{\theta }^{\prime }\in \Theta }{d}_{TV}(\theta ,{\theta }^{\prime }).$ The Hausdorff distance between ${\Theta }_1$ and ${\Theta }_2$ is given by 

$$d_H({\Theta }_1,{\Theta }_2):=max\left\{\underset{{\theta }_1\in {\Theta }_1}{sup}d\right({\theta }_1,{\Theta }_2),\underset{{\theta }_2\in {\Theta }_2}{sup}d({\theta }_2,{\Theta }_1\left)\right\}.$$

Because credal sets are closed by definition, the Hausdorff total variation distance between non-empty credal sets is a well-defined metric.

The topology of $\square (A\times O{)}^{\omega }$ is then given by the metric topology induced by the Hausdorff distance between credal sets.

Crisp Causal Laws

Causal laws^[5] are a special type of infrakernel used to analyze sets of environments.

Given a set of environments $E$ and a policy $\pi$, we can consider the set of distributions over destinies that arise from the interaction of each environment and the policy, which we denote by $\{{\mu }^{\pi }:\mu \in E\}$ (for details see the preceding post).

Wrapping this into a function results in an infrakernel as follows.

Definition: The infrakernel generated from a set of environments
A set of environments $E$ generates the infrakernel ${\Lambda }_E\left(\pi \right):\Pi \to \square (A\times O{)}^{\omega }$ defined by ${\Lambda }_E\left(\pi \right)=\overline{\text{ch}\left(\right\{{\mu }^{\pi }:\mu \in E\left\}\right)},$ where $\text{ch}$ denotes convex hull and $\overline{\cdot }$ denotes closure.

This leads to the definition of crisp causal laws, which take the role of hypotheses in infra-Bayesianism, as opposed to environments in classical reinforcement learning theory.

Definition: Crisp causal law
A crisp causal law is an infrakernel $\Lambda :\Pi \to \square (A\times O{)}^{\omega }$ generated by a set of environments.

For example, let $A=\{a_0,a_1\}$ and $O=\{o_0,o_1\}$ denote a set of actions and a set of observations respectively. Let $\pi$ be a policy such that $\pi \left(ϵ\right)=a_0$ where $ϵ$ denotes the empty history. Let ${\mu }_1$ denote an environment such that ${\mu }_1\left(o_0|a_0\right)=\frac{1}{12}$. Let ${\mu }_2$ denote a second environment such that ${\mu }_2\left(o_0|a_0\right)=1$. A calculation as in Figure 2 of the preceding post shows that ${\mu }_1^{\pi }$ is given by $(\frac{1}{12},\frac{11}{12},0,0),$ with each index of the tuple corresponding to one of the four possible histories of length one. Furthermore, ${\mu }_2^{\pi }$ is given by $(1,0,0,0).$

By disregarding the last two irrelevant coordinates, we can visualize ${\mu }_1^{\pi }$ and ${\mu }_2^{\pi }$ as points in the 1-dimensional simplex. Let $E$ be the convex closure of $\{{\mu }_1,{\mu }_2\}$. Then ${\Lambda }_E\left(\pi \right)$ corresponds to a line segment on the 1-dimensional simplex as shown in Figure 4. 

The next proposition states that crisp causal laws are continuous with respect to the topologies discussed in the previous section. Since we are working with topological spaces, a function $\sigma :T_1\to T_2$ between topological spaces $T_1$ and $T_2$ is continuous if for every open set $U$ in $T_2$, $f^{-1}\left(U\right)$ is open in $T_1.$ It is well known that this definition is equivalent to the epsilon-delta definition of continuity when $T_1$ and $T_2$ are metric spaces. 

Proposition 1: Every crisp causal law $\Lambda :\Pi \to \square (A\times O{)}^{\omega }$ is continuous with respect to the product topology on $\Pi$ and the Hausdorff topology on $\square (A\times O{)}^{\omega }.$

The Minimax Decision Rule

In the classical setting, given a set of policies and a prior over a class of environments, a natural rule for choosing a policy is expected loss minimization in which a policy is chosen to minimize expected loss with respect to the prior. Recall that crisp causal laws take the place of environments as hypotheses in infra-Bayesianism. Even if a prior over hypotheses (crisp causal laws) is given, it is impossible to carry out expected loss minimization because there is Knightian uncertainty over the distributions that make up a credal set.

Because expected loss minimization is impossible, it is necessary to use a different decision rule. In the context of AI alignment, it is of interest to have guarantees on agent behavior that hold even in the worst-case scenarios. Given a set of environments, worst-case reasoning describes a decision-making heuristic in which an agent assumes that the true environment is the environment that would be worst with respect to some measure. The minimax decision rule stipulates that an agent should choose a policy so that the maximum expected loss over the set of possible environments is minimized.^[6] Other decision rules can be reduced to minimax^[7], and furthermore, there are natural classes of hypotheses that are learnable with respect to minimax, a notion that we define below.^[8] 

Worst-case reasoning is implicitly built into the following definition.

Definition: Expected loss of a policy with respect to a crisp causal law
Let $L:(A\times O{)}^{\omega }\to [0,1]$ denote a continuous loss function. The expected loss of a policy $\pi \in \Pi$ with respect to a crisp causal law $\Lambda$ is defined by 

$$E_{\Lambda \left(\pi \right)}\left[L\right]:=\underset{\theta \in \Lambda \left(\pi \right)}{max}{E}_{\theta }\left[L\right].$$

​Using the assumption that $L$ is continuous, Lemma 1 and Lemma 4 of the proof section imply that $E_{\Lambda \left(\pi \right)}\left[L\right]$ is well defined.

Choosing a policy that minimizes expected loss with respect to a crisp causal law is equivalent to choosing a policy that minimizes the maximum possible loss over the distributions obtained from the interaction of the policy and each environment. Therefore, the infra-Bayesian version of expected loss minimization is exactly a minimax decision.

Infra-Regret

Now that we have established the definition of expected loss in this setting, we can define the infra-Bayesian analogue to the regret of a policy with respect to an environment.

Definition: Infra-regret of a policy with respect to a crisp causal law
Let $L:(A\times O{)}^{\omega }\to [0,1]$ denote a continuous loss function. The infra-regret of a policy $\pi \in \Pi$ with respect to a crisp causal law $\Lambda$ is defined by 

$$\text{Reg}(\pi ,\Lambda ,L):=E_{\Lambda \left(\pi \right)}\left[L\right]-\underset{{\pi }^{\prime }\in \Pi }{min}{E}_{\Lambda \left({\pi }^{\prime }\right)}\left[L\right].$$

It is natural to ask whether this notion of regret is well-defined. A proof can be given using Lemma 2 of the preceding post, which states that $\Pi$ is compact, and the following proposition.

Proposition 2^[9]: Let $\pi \in \Pi$ be a policy, $\Lambda$ a crisp causal law, and $L:(A\times O{)}^{\omega }\to [0,1]$ a continuous function. Then the map $\pi \mapsto E_{\Lambda \left(\pi \right)}\left[L\right]$ is continuous.

In the classical theory, a prior over environments quantifies uncertainty about the true environment. The analogue in infra-Bayesianism is a prior over crisp causal laws. The expected regret with respect to a prior of this type is called the infra-regret.

Definition: Infra-regret of a policy with respect to a prior
Let $\zeta$ denote a prior over a set of crisp causal laws. The infra-regret of a policy $\pi$ with respect to $\zeta$ is defined by 

$$\text{IBReg}(\pi ,\zeta ,L):=E_{\Lambda \sim \zeta }\left[\text{Reg}\right(\pi ,\Lambda ,L\left)\right].$$

Infra-Bayes Optimality and Learnability

In this section, we introduce some elementary results on learnability in infra-Bayesianism. The analogue to a Bayes optimal policy with respect to a prior over environments is an infra-Bayes optimal policy, defined as follows.

Definition: Infra-Bayes optimal policy
An infra-Bayes optimal policy with respect to a prior $\zeta$ over crisp causal laws is a policy 

$${\pi }^{\ast }\in {\text{argmin}}_{\pi \in \Pi }{E}_{\Lambda \sim \zeta }\left[E_{\Lambda \left(\pi \right)}\right[L\left]\right].$$

A family of policies $\{{\pi }^{\gamma }{\}}_{\gamma \in [0,1)}$ is said to be infra-Bayes optimal if for all $\gamma \in [0,1),$ ${\pi }^{\gamma }$ is infra-Bayes optimal for the $\gamma$-dependent loss function $L^{\gamma }.$

A natural question is: Does an infra-Bayes optimal policy always exist? The answer is yes; this is a corollary of Proposition 2 and the compactness of $\Pi$. A standard continuity argument can also be used to show that the set of infra-Bayes optimal policies is closed, as stated in the following corollary.^[10]

Corollary 1: Existence of the infra-Bayes optimal policy
Let $\pi \in \Pi$ denote a policy, $\Lambda$ a crisp causal law, and $L:(A\times O{)}^{\omega }\to [0,1]$ a continuous function. Then ${\text{argmin}}_{\pi \in \Pi }{E}_{\Lambda \sim \zeta }\left[E_{\Lambda \left(\pi \right)}\right[L\left]\right]$ is non-empty and closed.

The analogue of a learnable class of environments is a learnable class of causal laws.

Definition: Non-anytime learnable class of infra-Bayesian hypotheses
Let $I$ denote an indexing set. A class of crisp causal laws (hypotheses) $\{{\Lambda }_i{\}}_{i\in I}$ is non-anytime learnable if there exists a set of policies $\{{\pi }^{\gamma }{\}}_{\gamma \in [0,1)}$ such that for all $i\in I,$ ${lim}_{\gamma \to 1}\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })=0.$ In this case, we say that $\{{\pi }^{\gamma }{\}}_{\gamma \in [0,1)}$ learns $\{{\Lambda }_i{\}}_{i\in I}.$

Furthermore, we have the analogue of a non-anytime learnable prior over environments.

Definition: Non-anytime learnable prior over crisp causal laws
A prior $\zeta$ over a set of causal laws is non-anytime learnable if there exists a set of policies $\{{\pi }^{\gamma }{\}}_{\gamma \in [0,1)}$ such that 

$$\underset{\gamma \to 1}{lim}\left(E_{\Lambda \sim \zeta }\right[E_{\Lambda \left({\pi }^{\gamma }\right)}\left[L^{\gamma }\right]-\underset{\pi \in \Pi }{min}{E}_{\Lambda \left(\pi \right)}\left[L^{\gamma }\right]\left]\right)=0.$$

In this case, we say that $\{{\pi }^{\gamma }{\}}_{\gamma \in [0,1)}$ learns $\zeta .$

Proposition 2 of the preceding post states the classical result from learning theory that if a countable class of environments is learnable, given a non-dogmatic prior over the class, then any family of policies that is Bayes-optimal with respect to the prior must also learn the class. We end with the following corresponding result for crisp causal laws. The proof is contained in the proof section.

Proposition 3: For any non-dogmatic prior $\zeta$ over a learnable and countable collection of crisp causal laws $\{{\Lambda }_i{\}}_{i=0}^{\infty }$,  if a family $\{{\pi }^{\ast \gamma }{\}}_{\gamma \in [0,1)}$ of policies is infra-Bayes optimal with respect to $\zeta$, then $\{{\pi }^{\ast \gamma }{\}}_{\gamma \in [0,1)}$ learns $\{{\Lambda }_i{\}}_{i=0}^{\infty }.$

Acknowledgements

I'm grateful to Vanessa Kosoy and Alexander Appel for insightful discussions, and Marcus Ogren and Mateusz Bagiński for their valuable feedback on the initial draft.

1. ^{^}

   In the original infra-Bayesianism sequence, credal sets are called crisp infradistributions.

2. ^{^}

   First called "unmeasurable uncertainty" by economist Frank Knight in his 1921 book Risk, Uncertainty, and Profit. 

3. ^{^}

   As defined in The Many Faces of Infra-Belief.

4. ^{^}

   This requires dealing with infinite action spaces, which is typically not a problem as long as the action space is compact Polish.

5. ^{^}

   Previously called belief functions, e.g. as in The Many Faces of Infra-Belief.

6. ^{^}

   If using reward rather than loss, this rule can be equivalently formulated as a maximin rule (c.f. Infra-Bayesianism Distillation: Realizability and Decision Theory).

7. ^{^}

   See Vanessa Kosoy's Shortform. 

8. ^{^}

   See Vanessa Kosoy's Shortform.

9. ^{^}

   This proposition is a special case of Proposition 5 from Belief Functions And Decision Theory.

10. ^{^}

    These two statements were written as Proposition 12 in Belief Functions And Decision Theory.