Delegative Inverse Reinforcement Learning

[Vanessa Kosoy]

We introduce a reinforcement-like learning setting we call Delegative Inverse Reinforcement Learning (DIRL). In DIRL, the agent can, at any point of time, delegate the choice of action to an “advisor”. The agent knows neither the environment nor the reward function, whereas the advisor knows both. Thus, DIRL can be regarded as a special case of CIRL. A similar setting was studied in Clouse 1997, but as far as we can tell, the relevant literature offers few theoretical results and virtually all researchers focus on the MDP case (please correct me if I’m wrong). On the other hand, we consider general environments (not necessarily MDP or even POMDP) and prove a natural performance guarantee.

The use of an advisor allows us to kill two birds with one stone: learning the reward function and safe exploration (i.e. avoiding both the Scylla of “Bayesian paranoia” and the Charybdis of falling into traps). We prove that, given certain assumption about the advisor, a Bayesian DIRL agent (whose prior is supported on some countable set of hypotheses) is guaranteed to attain most of the value in the slow falling time discount (long-term planning) limit (assuming one of the hypotheses in the prior is true). The assumption about the advisor is quite strong, but the advisor is not required to be fully optimal: a “soft maximizer” satisfies the conditions. Moreover, we allow for the existence of “corrupt states” in which the advisor stops being a relevant signal, thus demonstrating that this approach can deal with wireheading and avoid manipulating the advisor, at least in principle (the assumption about the advisor is still unrealistically strong). Finally we consider advisors that don’t know the environment but have some beliefs about the environment, and show that in this case the agent converges to Bayes-optimality w.r.t. the advisor’s beliefs, which is arguably the best we can expect.

---

All the proofs are in the Appendix.

Notation

The set of natural numbers $N$ is defined to begin from 0. Given $n\in N$, $\left[n\right]$ denotes the set $\{m\in N\mid m<n\}$. Given a logical formula $\phi$, $\left[\right[\phi \left]\right]\in \{0,1\}$ denotes its truth value.

Given a set $X$, we denote $X^{\ast }:={⨆}_{n\in N}{X}^n$, the set of finite strings over the alphabet $X$. The unique string of length 0 is denoted $\lambda$. We also denote by $X^{\omega }$ the set of infinite strings over alphabet $X$. Given $\alpha \in X^{\ast }\bigsqcup X^{\omega }$ and $n\in N$, ${\alpha }_n\in X$ is the $n$-th symbol in $\alpha$ (i.e. $\alpha ={\alpha }_0{\alpha }_1{\alpha }_2\dots$) and ${\alpha }_{:n}\in X^{\ast }$ is the prefix of length $n$ of $\alpha$ (ending in ${\alpha }_{n-1}$). Given $\alpha ,\beta \in X^{\ast }$, $\left|\alpha \right|\in N$ is the length of $\alpha$ and $\alpha \beta \in X^{\ast }$ is the concatenation of $\alpha$ and $\beta$. The latter notation is also applicable when $\beta \in X^{\omega }$. The notation $\alpha ⊑\beta$ means that $\alpha$ is a prefix of $\beta$. Given sets $X,Y$, $x\in X$ and $y\in Y$, we sometimes use the notation $xy=(x,y)\in X\times Y$. Given $\alpha \in (X\times Y{)}^{\ast }$, and $n\in N$, ${\alpha }_{:n+1/2}\in (X\times Y{)}^{\ast }\times X$ is defined by ${\alpha }_{:n+1/2}=({\alpha }_{:n},x)$ where ${\alpha }_n=(x,y)$.

Given sets $A$ and $B$, the notation $f:A\stackrel{\circ }{\to }B$ means that $f$ is a partial mapping from $A$ to $B$, i.e. a mapping from some set $\mathrm{dom}f\subseteq A$ to $B$.

Given a topological space $A$, $\Delta A$ is the space of Borel probability measures on $A$. When no topology is specified, $A$ is understood to be discrete: in this case, $\mu \in \Delta A$ can also be regarded as a function from $A$ to $[0,1]$. The space $X^{\omega }$ is understood to have the product topology. Given topological spaces $A,B$, $\mu \in \Delta A$ and $\nu \in \Delta B$, $\mathrm{supp}\mu \subseteq A$ is the support of $\mu$ and $\mu \times \nu \in \Delta (A\times B)$ is the product measure. Given $K$ a Markov kernel from $A$ to $B$, $\mu ⋉A\in \Delta (A\times B)$ is the semidirect product of $\mu$ and $K$. When $A$ and $B$ are discrete, $H\left(\mu \right)$ is the Shannon entropy of $\mu$ (in natural base) and $D_{KL}(\mu \parallel \nu )$ is the Kullback-Leibler divergence from $\nu$ to $\mu$.

Given $d\in N$ and $x\in R^d$, we use the notation

$$\parallel x{\parallel }_1:=\sum _{i<d}\left|x_i\right|$$

$$\parallel x{\parallel }_{\infty }:=\underset{i<d}{max}\left|x_i\right|$$

The symbols $o,O,\omega ,\Omega ,\Theta$ will refer to usual $O$-notation.

Results

An interface $I=(A,O)$ is a pair of finite sets (“actions” and “observations”). An $I$-policy is a function $\pi :(A\times O{)}^{\ast }\to \Delta A$. An $I$-environment is a partial function $\mu :(A\times O{)}^{\ast }\times A\stackrel{\circ }{\to }\Delta O$ s.t.

i. $\lambda \times A\subseteq \mathrm{dom}\mu$

ii. Given $h\in (A\times O{)}^{\ast }$ and $aob\in A\times O\times A$, $haob\in \mathrm{dom}\mu$ iff $ha\in \mathrm{dom}\mu$ and $\mu \left(ha\right)\left(o\right)>0$.

It is easy to see that $\mathrm{dom}\mu$ is always of the form $X\times A$ for some $X\subseteq (A\times O{)}^{\ast }$. We denote $\mathrm{hdom}\mu :=X$.

Given an $I$-policy $\pi$ and an $I$-environment $\mu$, we get $\mu \bowtie \pi \in \Delta (A\times O{)}^{\omega }$ in the usual way.

An $I$-reward function is a partial function $r:(A\times O{)}^{\ast }\stackrel{\circ }{\to }[0,1]$. An $I$-universe is a pair $(\mu ,r)$ where $\mu$ is an $I$-environment and $r$ is an $I$-reward function s.t. $\mathrm{dom}r\supseteq \mathrm{hdom}\mu$. We denote the space of $I$-universes by ${{\rm Y}}_I$. Given an $I$-reward function $r$ and $t\in (0,\infty )$, we have the associated utility function $U_t^r:(A\times O{)}^{\omega }\stackrel{\circ }{\to }[0,1]$ defined by

$$U_t^r\left(x\right):=\frac{{\sum }_{n=0}^{\infty }{e}^{-n/t}r\left(x_{:n}\right)}{{\sum }_{n=0}^{\infty }{e}^{-n/t}}$$

Here and throughout, we use geometric time discount, however this choice is mostly for notational simplicity. More or less all results carry over to other shapes of the time discount function.

Denote ${\Pi }_I$\ the space of $I$-policies. An $I$-metapolicy is a family $\{{\pi }_t\in {\Pi }_I{\}}_{t\in (0,\infty )}$, where the parameter $t$ is thought of as setting the scale of the time discount. An $I$-meta-universe is a family $\{{\upsilon }_t\in {\rm Y}{\}}_{t\in (0,\infty )}$. This latter concept is useful for analyzing multi-agent systems, where the environment contains other agents and we study the asymptotics when all agents’ time discount scales go to infinity. We won’t focus on the multi-agent case in this essay, but for future reference, it seems useful to make sure the results hold in the greater generality of meta-universes.

Given an $I$-policy $\pi$, an $I$-universe $\upsilon$ and $t>0$, we denote ${\mathrm{EU}}_{\upsilon }^{\pi }\left(t\right):=\underset{\mu \bowtie \pi }{E}\left[U_t^r\right]$ (this is well-defined since $U_t^r$ is defined on the support of $\mu \bowtie \pi$). We also denote ${\mathrm{EU}}_{\upsilon }^{\ast }\left(t\right):={max}_{\pi \in {\Pi }_I}{\mathrm{EU}}_{\upsilon }^{\pi }\left(t\right)$. We will omit $I$ when it is obvious from the context.

Definition 1

Fix an interface $I$. Consider ${\pi }^{\ast }$ a metapolicy and $H$ a set of meta-universes.${\pi }^{\ast }$ is said to learn $H$ when for any $\upsilon \in H$

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{{\upsilon }_t}^{\ast }\right(t)-{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\ast }}(t\left)\right)=0$$

$H$ is said to be learnable when there exists ${\pi }^{\ast }$ that learns $H$.

---

Our notion of learnability is closely related to the notion of sublinear regret, as defined in Leike 2016, except that we allow the policy to explicitly depend on the time discount scale. This difference is important: for example, given a single universe $\upsilon$, it might be impossible to achieve sublinear regret, but $\left\{\upsilon \right\}$ is always learnable.

Proposition 1

Fix an interface $I$. Consider $H$ a countable learnable set of meta-universes. Consider any $\zeta \in \Delta H$ s.t. $\mathrm{supp}\zeta =H$. Consider ${\pi }^{\zeta }$ a $\zeta$-Bayes optimal metapolicy, i.e.

$${\pi }_t^{\zeta }\in \underset{\pi \in \Pi }{argmax}\underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{\pi }\right(t\left)\right]$$

Then, ${\pi }^{\zeta }$ learns $H$.

---

Proposition 1 can be regarded as a “frequentist” justification for Bayesian agents: if any metapolicy is optimal in a “frequentist” sense for the class $H$ (i.e. learns it), then the Bayes optimal metapolicy is such.

Another handy property of learnability is the following.

Proposition 2

Fix an interface $I$. Let $H$ be a countable set of meta-universes s.t. any finite $G\subseteq H$ is learnable. Then, $H$ is learnable.

---

We now introduce the formalism needed to discuss advisors. Define $\overline{A}:=A\bigsqcup \left\{\perp \right\}$, $\overline{O}:=\overline{A}\times O$ and $\overline{I}:=(\overline{A},\overline{O})$. Here, the $\overline{A}$ factor of $\overline{O}$ is the action taken by the advisor, assumed to be observable by the agent. The environments we will consider are s.t. this action is $\perp$ unless the agent delegated to the advisor at this point of time, which is specified by the agent taking action $\perp$. It will also be the case that whenever the agent takes action $\perp$, the advisor cannot take action $\perp$.

Denote $\overline{A\times O}:=\overline{A}\times \overline{O}\setminus \{\perp \perp o\mid o\in O\}$. Given $abo\in \overline{A\times O}$, we define $\underset{–}{abo}\in A\times O$ by

$$\underset{–}{abo}:=\{\begin{array}{c}ao\text{if}a\ne \perp \\ bo\text{if}a=\perp \end{array}$$

Given $h\in {\overline{A\times O}}^{\ast }$, we define $\underset{–}{h}\in (A\times O{)}^{\ast }$ by ${\underset{–}{h}}_n:=\underset{–}{h_n}$.

Definition 2

An $\overline{I}$-policy $\alpha$ is said to be autonomous when for any $h\in {\overline{A\times O}}^{\ast }$, $\alpha \left(h\right)\left(\perp \right)=0$.

---

Consider an $I$-environment $\mu$ and an autonomous $\overline{I}$-policy $\alpha$, which we think of as the advisor policy. We define the $\overline{I}$-environment $\overline{\mu }\left[\alpha \right]$ as follows. For any $h\in {\overline{A\times O}}^{\ast }$ s.t. $\underset{–}{h}\in \mathrm{hdom}\mu$, $a,b\in \overline{A}$ and $o\in O$:

$$\overline{\mu }\left[\alpha \right]\left(ha\right)\left(bo\right):=\{\begin{array}{c}\mu \left(\underset{–}{h}a\right)\left(o\right)\text{if}a\ne \perp ,b=\perp \\ \alpha \left(h\right)\left(b\right)\cdot \mu \left(\underset{–}{h}b\right)\left(o\right)\text{if}a=\perp ,b\ne \perp \\ 0\text{if}a\ne \perp ,b\ne \perp \text{or}a=b=\perp \end{array}$$

It is easy to the above is a well-defined $\overline{I}$-environment with $\mathrm{hdom}\mu \subseteq {\overline{A\times O}}^{\ast }$.

Given an $I$-universe $\upsilon =(\mu ,r)$, we define the $\overline{I}$-reward function $\overline{r}:{\overline{A\times O}}^{\ast }\stackrel{\circ }{\to }[0,1]$ by $\overline{r}\left(h\right):=r\left(\underset{–}{h}\right)$ and the $\overline{I}$-universe $\overline{\upsilon }\left[\alpha \right]:=\left(\overline{\mu }\right[\alpha ],\overline{r})$.

We now introduce the conditions on the advisor policy which will allow us to prove a learnability theorem. First, we specify an advisor that always remains “approximately rational.”

The notation $\underset{x\sim \rho }{E}[X\mid h]$ will be used to mean $\underset{x\sim \rho }{E}[X\mid h⊑x]$. Given a universe $\upsilon =(\mu ,r)$ and $t\in (0,\infty )$ we define $V_t^{\upsilon }:\mathrm{hdom}\mu \to [0,1]$ and $Q_t^{\upsilon }:\mathrm{hdom}\mu \times A\to [0,1]$ by

$$V_t^{\upsilon }\left(h\right):=\underset{\pi \in \Pi }{max}\underset{x\sim \mu \bowtie \pi }{E}[\frac{{\sum }_{n=\left|h\right|}^{\infty }{e}^{-n/t}r\left(x_{:n}\right)}{{\sum }_{n=\left|h\right|}^{\infty }{e}^{-n/t}}\mid h]$$

$$Q_t^{\upsilon }\left(ha\right):=(1-e^{-1/t})r\left(h\right)+e^{-1/t}\underset{o\sim \mu \left(ha\right)}{E}\left[V_t^{\upsilon }\right(hao\left)\right]$$

Definition 3

Fix an interface $I$. Consider a universe $\upsilon =(\mu ,r)$. Let $t,\beta \in (0,\infty )$. A policy $\alpha$ is called strictly $\beta$-rational for $(\upsilon ,t)$ when for any $h\in \mathrm{dom}\mu$ and $a\in A$

$$\alpha \left(h\right)\left(a\right)\le \exp \left[\beta \right(Q_t^{\upsilon }\left(ha\right)-V_t^{\upsilon }\left(h\right)\left)\right]\underset{a^{\ast }\in A}{max}\alpha \left(h\right)\left(a^{\ast }\right)$$

---

Now we deal with the possibility of the advisor becoming “corrupt”. In practical implementations where the “advisor” is a human operator, this can correspond to several types of events, e.g. sabotaging the channel that transmits data from the operator to the AI (“wireheading”), manipulation of the operator or replacement of the operator by a different entity.

Definition 4

Fix an interface $I$. Consider a family $\{C_t\subseteq (A\times O{)}^{\ast }{\}}_{t\in (0,\infty )}$ s.t. for any $h,g\in (A\times O{)}^{\ast }$, if $h\in C_t$ then $hg\in C_t$. We think of $C_t$ as the set of histories in which a certain event occurred. Consider a meta-universe $\upsilon =(\mu ,r)$. $C$ is said to be a $\upsilon$-avoidable event when there is a meta-policy ${\pi }^{\ast }$ and $D:(0,\infty )\to N$ s.t.

i. ${lim}_{t\to \infty }\left({\mathrm{EU}}_{{\upsilon }_t}^{\ast }\right(t)-{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\ast }}(t\left)\right)=0$

ii. $D=\omega \left(t\right)$

iii. ${lim}_{t\to \infty }{Pr}_{x\sim {\mu }_t\bowtie {\pi }_t^{\ast }}[\exists n\le D(t):x_{:n}\in C_t]=0$

---

That is, $C$ is $\upsilon$-avoidable when it is possible to avoid the event for a long time while retaining most of the value. Consider a meta-universe $\upsilon =(\mu ,r)$ and $C$ a $\upsilon$-avoidable event. Denote $-\upsilon :=(\mu ,1-r)$. We define the reward function $r_t^C$ by

$$r_t^C\left(h\right):=\{\begin{array}{c}{r}_t\left(h\right)\text{if}h\notin C_t\\ V_t^{-\upsilon }\left(h_{:n}\right)\text{if}h\in C_t\text{and}n=min\{m\in N\mid h_{:m}\in C_t\}\end{array}$$

We think of $r^C$ as representing a process wherein once the event represented by $C$ occurs, the agent starts minimizing the utility function. We also use the notation ${\upsilon }^C:=(\mu ,r^C)$.

Definition 5

Consider a meta-universe $\upsilon =(\mu ,r)$ and $\beta :(0,\infty )\to (0,\infty )$, where we think of the argument of the function $\beta$ as the time discount scale. An autonomous $\overline{I}$-metapolicy $\alpha$ is called $\beta$-rational for $\upsilon$ when there exists a $\upsilon$-avoidable event $C$ (that we think of as the advisor becoming “corrupt”) and an autonomous $\overline{I}$-metapolicy ${\alpha }^{\ast }$ (representing advisor policy conditional on non-corruption) s.t.

i. For any $h\in {\overline{A\times O}}^{\ast }$ s.t. $\underset{–}{h}\notin C_t$, ${\alpha }_t\left(h\right)={\alpha }_t^{\ast }\left(h\right)$.

ii.${\alpha }_t^{\ast }$ is strictly $\beta \left(t\right)$-rational for $\left({\overline{\upsilon }}_t^C\right[{\alpha }^{\ast }],t)$.

---

Our definition of $\beta$-rationality requires the advisor to be extremely averse to corruption: the advisor behaves as if, once a corruption occurs, the agent policy becomes the worst possible. In general, this seems much too strong: by the time corruption occurs, the agent might have already converged into accurate beliefs about the universe that allow it to detect the corruption and keep operating without the advisor. Even better, the agent can usually outperform the worst possible policy using the prior alone. Moreover, we can allow for corruption to depend on unobservable random events and differentiate between different degrees of corruption and treat them accordingly. We leave those further improvements for future work.

We are now ready to formulate the main result.

Theorem

Consider $H=\{{\upsilon }^k{\}}_{k\in N}$ a countable family of $I$-meta-universes and $\beta :(0,\infty )\to (0,\infty )$ s.t. $\beta \left(t\right)=\omega \left(t^{2/3}\right)$. Let $\{{\alpha }^k{\}}_{k\in N}$ be a family of autonomous $\overline{I}$-metapolicies s.t. for every $k\in N$, ${\alpha }^k$ is $\beta$-rational for ${\upsilon }^k$. Define $\overline{H}:=\left\{{\overline{\upsilon }}^k\right[{\alpha }^k]{\}}_{k\in N}$. Then, $\overline{H}$ is learnable.

---

Some remarks:

• By Proposition 1, $\overline{H}$ is learned by any Bayes optimal metapolicy with prior supported on $\overline{H}$.

• To get a feeling for the condition $\beta \left(t\right)=\omega \left(t^{2/3}\right)$, consider an environment where the reward depends only on the last action and observation. In such an environment, an advisor that performs softmax (with constant parameter) on the next reward has $\beta \left(t\right)=\Theta \left(t\right)$. It is thus “more rational” than the required minimum.

• It is easy to see that the Theorem can be generalized by introducing an external penalty (negative reward) for each time the agent delegates to the advisor: as it is, using the advisor already carries a penalty due to its suboptimal choice.

The conditions of the Theorem imply that, in some sense, the advisor “knows” the true environment. This is unrealistic: obviously, we expect the human operator to have some (!) uncertainty about the world. However, we clearly cannot do away with this assumption: if the same action triggers a trap in some universes and is necessary for approaching maximal utility in other universes, and there is no observable difference between the universes before the action is taken, then there is no way to guarantee optimality. The prior knowledge you have about the universe caps the utility you can guarantee to obtain. On the other hand, as an AI designer, one can reasonably expect the AI to do at least as well as possible using the designer’s own knowledge. If running the AI is the designer’s best strategy, the AI should be close to Bayes optimal (in some sense that includes computational bounds et cetera: complications that we currently ignore) with respect to the designer’s posterior rather than with respect to some simple prior. In other words, we need a way to transmit the designer’s knowledge to the AI, without hand-crafting an elaborate prior.

The following shows that the DIRL achieves this goal (theoretically, given the considerable simplifying assumptions).

Given an environment $\mu$, we define $\hat{\mu }:(A\times O{)}^{\ast }\to [0,1]$ as follows. For $h=a_0{o}_0{a}_1{o}_1\dots a_{n-1}{o}_{n-1}\in \mathrm{hdom}\mu$

$$\hat{\mu }\left(h\right):=\prod _{m<n}\mu \left(h_{:m}{a}_m\right)\left(o_m\right)$$

For $h\in (A\times O{)}^{\ast }\setminus \mathrm{hdom}\mu$, $\hat{\mu }\left(h\right):=0$.

Given a family of environments $\{{\mu }^k{\}}_{k\in N}$ and $\xi \in \Delta N$, we will use the notation $\underset{k\sim \xi }{E}\left[{\mu }^k\right]$ to denote the environment given by

$$\mathrm{hdom}\underset{k\sim \xi }{E}\left[{\mu }^k\right]:=\bigcup _{k\in \mathrm{supp}\xi }\mathrm{hdom}{\mu }^k$$

$$\underset{k\sim \xi }{E}\left[{\mu }^k\right]\left(ha\right):=\frac{\underset{k\sim \xi }{E}\left[{\hat{\mu }}^k\right(h\left){\mu }^k\right(ha\left)\right]}{\underset{k\sim \xi }{E}\left[{\hat{\mu }}^k\right(h\left)\right]}$$

Corollary 1

Consider $\{{\mu }^k{\}}_{k\in N}$ a countable family of $I$-meta-environments, $\{r^K{\}}_{K\in N}$ a countable family of reward functions and $\{{\xi }^K\in \Delta N{\}}_{K\in N}$ s.t. given $k\in \mathrm{supp}{\xi }^K$, $\mathrm{dom}{r}^K\supseteq \mathrm{hdom}{\mu }^k$. We think of ${\xi }^K$ as the advisor’s belief about the environment in universe $K$. Let $\beta :(0,\infty )\to (0,\infty )$ be s.t.$\beta \left(t\right)=\omega \left(t^{2/3}\right)$ and $\{{\alpha }^K{\}}_{K\in N}$ be a family of autonomous $\overline{I}$-metapolicies s.t. for every $K\in N$, ${\alpha }^K$ is $\beta$-rational for $\left(\underset{k\sim {\xi }^K}{E}\right[{\mu }^k],r^K)$. Let $\zeta \in \Delta N^2$ be s.t. for any $J,j\in N$

$$\underset{(K,k)\in \zeta }{Pr}[K=J]>0$$

$$\underset{(K,k)\in \zeta }{Pr}[k=j\mid K=J]={\xi }^J\left(j\right)$$

We think of $\zeta$ as the agent’s prior and the equation above as stating the agent’s belief that the advisor’s beliefs are “calibrated”. Consider ${\pi }^{\zeta }$ a $\zeta$-Bayes optimal $\overline{I}$-metapolicy, i.e.

$${\pi }^{\zeta }\in \underset{\pi \in {\Pi }_{\overline{I}}}{argmax}\underset{(K,k)\in \zeta }{E}\left[{\mathrm{EU}}_{{\overline{\mu }}^k\left[{\alpha }^K\right],{\overline{r}}^K}^{\pi }\right(t\left)\right]$$ Then, for every $K\in N$

$$\underset{t\to \infty }{lim}\left(\underset{\pi \in {\Pi }_I}{max}\underset{k\in {\xi }^K}{E}\right[{\mathrm{EU}}_{{\mu }^k,r^K}^{\pi }\left(t\right)]-\underset{k\in {\xi }^K}{E}[{\mathrm{EU}}_{{\overline{\mu }}^k\left[{\alpha }^K\right],{\overline{r}}^K}^{{\pi }^{\zeta }}\left(t\right)\left]\right)=0$$

---

If we happen to be so lucky that the advisor’s (presumably justified) belief is supported on a learnable environment class, we get a stronger conclusion.

Corollary 2

In the setting of Corollary 1, fix $K\in N$. Define the set of meta-universes $H^K$ by

$$H^K:=\left\{\right({\mu }^k,r^K)\mid k\in \mathrm{supp}{\xi }^K\}$$

Assume $H^K$ is learnable. Then, for every $k\in N$

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{{\mu }^k,r^K}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\mu }}^k\left[{\alpha }^K\right],{\overline{r}}^K}^{{\pi }^{\zeta }}(t\left)\right)=0$$

---

We also believe that to some extent DIRL is effective against acausal attack. Indeed, the optimality we get from the Theorem + Proposition 1 holds for any prior. However, the speed of convergence to optimality certainly depends on the prior. It is therefore desirable to analyze this dependency and bound the damage an adversary can do by controlling a certain portion of the prior. We leave this for future work.

Appendix

Proposition A.0

Fix an interface $I$. Consider $H$ a countable learnable set of meta-universes. Consider any $\zeta \in \Delta H$ s.t. $\mathrm{supp}\zeta =H$. Consider ${\pi }^{\zeta }$ a metapolicy s.t.

$$\underset{t\to \infty }{lim}\left(\underset{\pi \in \Pi }{max}\underset{\upsilon \sim \zeta }{E}\right[{\mathrm{EU}}_{{\upsilon }_t}^{\pi }\left(t\right)]-\underset{\upsilon \sim \zeta }{E}[{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\zeta }}\left(t\right)\left]\right)=0$$

Then, ${\pi }^{\zeta }$ learns $H$.

Proof of Proposition A.0

Fix ${\pi }^{\ast }$ a metapolicy that learns $H$. Consider $ϵ>0$ and let $H_{ϵ}\subseteq H$ be finite s.t. $\zeta (H\setminus H_{ϵ})<ϵ$. For $t\gg 0$ and every $\upsilon \in H_{ϵ}$ we have

$${\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\ast }}\left(t\right)\ge {\mathrm{EU}}_{{\upsilon }_t}^{\ast }\left(t\right)-ϵ$$

Also

$$\underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\zeta }}\right(t\left)\right]\ge \underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\ast }}\right(t\left)\right]-ϵ\ge \underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\ast }}\right(t);\upsilon \in H_{ϵ}]-ϵ$$

Combining, we get

$$\underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\zeta }}\right(t\left)\right]\ge \underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{\ast }\right(t);\upsilon \in H_{ϵ}]-2ϵ$$

$$\underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\zeta }}\right(t\left)\right]\ge \underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{\ast }\right(t\left)\right]-\underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{\ast }\right(t);\upsilon \notin H_{ϵ}]-2ϵ$$

By definition of $H_{ϵ}$, this implies

$$\underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\zeta }}\right(t\left)\right]\ge \underset{\upsilon \sim \zeta }{E}\left[{\mathrm{EU}}_{{\upsilon }_t}^{\ast }\right(t\left)\right]-3ϵ$$

For any $\upsilon \in H$, we get

$${\mathrm{EU}}_{{\upsilon }_t}^{{\pi }_t^{\zeta }}\left(t\right)\ge {\mathrm{EU}}_{{\upsilon }_t}^{\ast }\left(t\right)-\frac{3ϵ}{\zeta \left(\upsilon \right)}$$

Taking $ϵ$ to 0, we get the desired result.

Proof of Proposition 1

Immediate from Proposition A.0.

Proof of Proposition 2

Let $H=\{{\upsilon }^k{\}}_{k\in N}$. For each $k\in N$, let ${\pi }^k$ learn $\{{\upsilon }^l{\}}_{l<k}$. Choose $\{t^k\in (0,\infty ){\}}_{k\in N}$ s.t.

i. $t^0=0$

ii. $t^k<t^{k+1}$

iii. ${lim}_{k\to \infty }{t}^k=\infty$

iv. For any $l<k$ and $t\ge t^k$, ${\mathrm{EU}}_{{\upsilon }_t^l}^{{\pi }_t^k}\left(t\right)\ge {\mathrm{EU}}_{{\upsilon }_t^l}^{\ast }\left(t\right)-\frac{1}{k+1}$.

Now define ${\pi }_t^{\ast }:={\pi }_t^{max\{k\mid t\ge t^k\}}$. Clearly, ${\pi }^{\ast }$ learns $H$.

Proposition A.1

Consider $d\in N$ and $x,y\in R^d\setminus 0$. Then

$$\parallel \frac{x}{\parallel x{\parallel }_{\infty }}-\frac{y}{\parallel y{\parallel }_{\infty }}{\parallel }_{\infty }\le 2d\parallel \frac{x}{\parallel x{\parallel }_1}-\frac{y}{\parallel y{\parallel }_1}{\parallel }_1$$

Proof of Proposition A.1

Without loss of generality, assume $\parallel x{\parallel }_1=\parallel y{\parallel }_1=1$. For any $i<d$, we have

$$\frac{x_i}{\parallel x{\parallel }_{\infty }}-\frac{y_i}{\parallel y{\parallel }_{\infty }}=\frac{x_i\parallel y{\parallel }_{\infty }-y_i\parallel x{\parallel }_{\infty }}{\parallel x{\parallel }_{\infty }\parallel y{\parallel }_{\infty }}=\frac{x_i\parallel y{\parallel }_{\infty }-x_i\parallel x{\parallel }_{\infty }+x_i\parallel x{\parallel }_{\infty }-y_i\parallel x{\parallel }_{\infty }}{\parallel x{\parallel }_{\infty }\parallel y{\parallel }_{\infty }}$$

$$\frac{x_i}{\parallel x{\parallel }_{\infty }}-\frac{y_i}{\parallel y{\parallel }_{\infty }}=\frac{x_i(\parallel y{\parallel }_{\infty }-\parallel x{\parallel }_{\infty })+(x_i-y_i)\parallel x{\parallel }_{\infty }}{\parallel x{\parallel }_{\infty }\parallel y{\parallel }_{\infty }}$$

Denote $r:=\parallel x-y{\parallel }_1$. Obviously, $\parallel x-y{\parallel }_{\infty }\le r$ and therefore $|x_i-y_i|\le r$ and $|\parallel x{\parallel }_{\infty }-\parallel y{\parallel }_{\infty }|\le r$. We get

$$|\frac{x_i}{\parallel x{\parallel }_{\infty }}-\frac{y_i}{\parallel y{\parallel }_{\infty }}|\le \frac{\left|x_i\right|r+r\parallel x{\parallel }_{\infty }}{\parallel x{\parallel }_{\infty }\parallel y{\parallel }_{\infty }}\le \frac{\parallel x{\parallel }_{\infty }r+r\parallel x{\parallel }_{\infty }}{\parallel x{\parallel }_{\infty }\parallel y{\parallel }_{\infty }}\le \frac{2r}{\parallel y{\parallel }_{\infty }}$$

Since $\parallel y{\parallel }_1=1$, $\parallel y{\parallel }_{\infty }\ge \frac{1}{d}$ yielding the desired result.

Proposition A.2

Consider $H$ a finite set, $L:H\to [0,\infty )$, $\zeta \in \Delta H$ and $\beta ,ϵ\in (0,\infty )$. Assume that

i. For any $k\in H$, $\zeta \left(k\right)\ge \beta ϵ$.

ii. $\underset{\zeta }{E}\left[L\right]\ge ϵ$

Then

$$\underset{\zeta }{E}\left[e^{-\beta L}\right]\le 1-(1-e^{-1})\beta ϵ$$

Proof of Proposition A.2

Without loss of generality, we can assume that $\underset{\zeta }{E}\left[L\right]=ϵ$, because otherwise we can rescale $L$ by a constant in $(0,1)$ which will only make $\underset{\zeta }{E}\left[e^{-\beta L}\right]$ larger. It now follows from conditions i+ii that for any $k$, $L\left(k\right)\le {\beta }^{-1}$ and therefore $\beta L\left(k\right)\in [0,1]$. We have

$$L\left(k\right)=(1-\beta L(k\left)\right)\cdot 0+\beta L\left(k\right)\cdot {\beta }^{-1}$$

Since $e^{-\beta x}$ is a convex function, we get

$$e^{-\beta L\left(k\right)}\le (1-\beta L(k\left)\right)\cdot e^{-\beta \cdot 0}+\beta L\left(k\right)\cdot e^{-\beta \cdot {\beta }^{-1}}=1-\beta L\left(k\right)+e^{-1}\beta L\left(k\right)=1-(1-e^{-1})\beta L\left(k\right)$$

$$\underset{\zeta }{E}\left[e^{-\beta L}\right]\le 1-(1-e^{-1})\beta \underset{\zeta }{E}\left[L\right]=1-(1-e^{-1})\beta ϵ$$

Proposition A.3

Consider $H$ and $A$ finite sets, $L:H\times A\to [0,\infty )$, $\zeta \in \Delta H$, $\alpha :H\to \Delta A$ and $\beta ,ϵ\in (0,\infty )$. Assume that

i. For any $k\in H$, $\zeta \left(k\right)\ge \beta ϵ$.

ii. For any $a\in A$, $\underset{k\in \zeta }{E}\left[L\right(k,a\left)\right]\ge ϵ$.

iii. For any $k\in H$ and $a\in A$, $\alpha \left(k\right)\left(a\right)\le \exp [-\beta L(k,a\left)\right]{max}_{b\in A}\alpha \left(k\right)\left(b\right)$.

Define $\zeta ⋉\alpha \in \Delta (H\times A)$ by $(\zeta ⋉\alpha )(k,a):=\zeta \left(k\right)\alpha (k,a)$. Then, the mutual information $I$ between $k$ and $a$ in the distribution $\zeta ⋉\alpha$ satisfies

$$I\ge \frac{(1-e^{-1}{)}^2}{8|A{|}^2}{\beta }^2{ϵ}^2$$

Proof of Proposition A.3

Define $\overline{\alpha }\in \Delta A$ by $\overline{\alpha }:=\underset{\zeta }{E}\left[\alpha \right]$. We have

$$I=\underset{\zeta }{E}\left[D_{KL}\right(\alpha \parallel \overline{\alpha }\left)\right]$$

Applying Pinsker’s inequality

$$I\ge 2\underset{\zeta }{E}\left[d_{\text{tv}}\right(\alpha ,\overline{\alpha }{)}^2]=\frac{1}{2}\underset{\zeta }{E}[\parallel \alpha -\overline{\alpha }{\parallel }_1^2]\ge \frac{1}{2}\underset{\zeta }{E}[\parallel \alpha -\overline{\alpha }{\parallel }_1{]}^2$$

By Proposition A.1

$$I\ge \frac{1}{8|A{|}^2}\underset{\zeta }{E}[\parallel \frac{\alpha }{\parallel \alpha {\parallel }_{\infty }}-\frac{\overline{\alpha }}{\parallel \overline{\alpha }{\parallel }_{\infty }}{\parallel }_{\infty }{]}^2\ge \frac{1}{8|A{|}^2}\parallel \underset{\zeta }{E}[\frac{\alpha }{\parallel \alpha {\parallel }_{\infty }}-\frac{\overline{\alpha }}{\parallel \overline{\alpha }{\parallel }_{\infty }}]{\parallel }_{\infty }^2=\frac{1}{8|A{|}^2}\parallel \underset{\zeta }{E}[\frac{\alpha }{\parallel \alpha {\parallel }_{\infty }}]-\frac{\overline{\alpha }}{\parallel \overline{\alpha }{\parallel }_{\infty }}{\parallel }_{\infty }^2$$

$$I\ge \frac{1}{8|A{|}^2}(\parallel \frac{\overline{\alpha }}{\parallel \overline{\alpha }{\parallel }_{\infty }}{\parallel }_{\infty }-\parallel \underset{\zeta }{E}[\frac{\alpha }{\parallel \alpha {\parallel }_{\infty }}]{\parallel }_{\infty }{)}^2=\frac{1}{8|A{|}^2}(1-\parallel \underset{\zeta }{E}\left[\frac{\alpha }{\parallel \alpha {\parallel }_{\infty }}\right]{\parallel }_{\infty }{)}^2$$

By condition iii, $\alpha \left(k\right)\left(a\right)/\parallel \alpha \left(k\right){\parallel }_{\infty }\le \exp [-\beta L(k,a\left)\right]$ and therefore

$$I\ge \frac{1}{8|A{|}^2}(1-\underset{a\in A}{max}\underset{k\sim \zeta }{E}[e^{-\beta L(k,a)}]{)}^2$$

Applying Proposition A.2, we get

$$I\ge \frac{1}{8|A{|}^2}(1-(1-(1-e^{-1})\beta ϵ){)}^2=\frac{(1-e^{-1}{)}^2}{8|A{|}^2}{\beta }^2{ϵ}^2$$

Proposition A.4

Consider $A$ a finite set, $L:A\to [0,\infty )$ and $\alpha \in \Delta A$ and $\beta \in (0,\infty )$ s.t. for any $a\in A$

$$\alpha \left(a\right)\le e^{-\beta L\left(a\right)}\underset{b\in A}{max}\alpha \left(b\right)$$

Then, $\underset{\alpha }{E}\left[L\right]\le \left|A\right|e^{-1}{\beta }^{-1}$.

Proof of Proposition A.4

We have

$$\underset{\alpha }{E}\left[L\right]=\sum _{a\in A}\alpha \left(a\right)L\left(a\right)\le \underset{b\in A}{max}\alpha \left(b\right)\sum _{a\in A}{e}^{-\beta L\left(a\right)}L\left(a\right)\le \left|A\right|\underset{x\in [0,\infty )}{max}{e}^{-\beta x}x$$

We compute ${max}_{x\in [0,\infty )}{e}^{-\beta x}x$:

$$0=\frac{d}{dx}\left(e^{-\beta x}x\right){|}_{x=x^{\ast }}=-\beta e^{-\beta x^{\ast }}{x}^{\ast }+e^{-\beta x^{\ast }}$$

$$x^{\ast }=\frac{1}{\beta }$$

$$e^{-\beta x^{\ast }}{x}^{\ast }=\frac{1}{e\beta }$$

Proposition A.5

Consider a universe $\upsilon =(\mu ,r)$, a policy ${\pi }^0$ and $t\in (0,\infty )$. Then,

$${\mathrm{EU}}_{\upsilon }^{\ast }\left(t\right)-{\mathrm{EU}}_{\upsilon }^{{\pi }^0}\left(t\right)=\sum _{n=0}^{\infty }{e}^{-n/t}\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[V_t^{\upsilon }\right(x_{:n})-Q_t^{\upsilon }(x_{:n+1/2}\left)\right]$$

Proof of Proposition A.5

For any $x\in (A\times O{)}^{\omega }$, it is easy to see that

$${\mathrm{EU}}_{\upsilon }^{\ast }\left(t\right)=V_t^{\upsilon }\left(\lambda \right)=\sum _{n=0}^{\infty }{e}^{-n/t}\left(V_t^{\upsilon }\right(x_{:n})-e^{-1/t}{V}_t^{\upsilon }(x_{:n+1}\left)\right)$$

$$U_t^r\left(x\right)=(1-e^{-1/t})\sum _{n=0}^{\infty }{e}^{-n/t}r\left(x_{:n}\right)$$

$${\mathrm{EU}}_{\upsilon }^{\ast }\left(t\right)-U_t^r\left(x\right)=\sum _{n=0}^{\infty }{e}^{-n/t}\left(V_t^{\upsilon }\right(x_{:n})-(1-e^{-1/t}\left)r\right(x_{:n})-e^{-1/t}{V}_t^{\upsilon }(x_{:n+1}\left)\right)$$

$${\mathrm{EU}}_{\upsilon }^{\ast }\left(t\right)-U_t^r\left(x\right)=\sum _{n=0}^{\infty }{e}^{-n/t}\left(V_t^{\upsilon }\right(x_{:n})-Q_t^{\upsilon }(x_{:n+1/2})+Q_t^{\upsilon }(x_{:n+1/2})-(1-e^{-1/t}\left)r\right(x_{:n})-e^{-1/t}{V}_t^{\upsilon }(x_{:n+1}\left)\right)$$

Taking expected value over $x$, we get

$${\mathrm{EU}}_{\upsilon }^{\ast }\left(t\right)-{\mathrm{EU}}_{\upsilon }^{{\pi }^0}\left(t\right)=\sum _{n=0}^{\infty }{e}^{-n/t}\left(\underset{\mu \bowtie {\pi }^0}{E}\right[V_t^{\upsilon }\left(x_{:n}\right)-Q_t^{\upsilon }\left(x_{:n+1/2}\right)]+\underset{\mu \bowtie {\pi }^0}{E}[Q_t^{\upsilon }\left(x_{:n+1/2}\right)-(1-e^{-1/t})r\left(x_{:n}\right)-e^{-1/t}{V}_t^{\upsilon }\left(x_{:n+1}\right)\left]\right)$$

It is easy to see that the second term vanishes, yielding the desired result.

Lemma A

Consider the setting of Theorem, but assume that $H=\{{\upsilon }^k=({\mu }^k,r^k){\}}_{k<N}$ for some $N\in N$ (i.e. it is finite) and that ${\alpha }^k\left(t\right)$ is strictly $\beta \left(t\right)$-rational for ${\overline{\upsilon }}^k\left[{\alpha }^k\right]$. Denote ${\nu }^k:={\overline{\mu }}^k\left[{\alpha }^k\right]$ and $\mathrm{hdom}\overline{H}:={\bigcup }_{k<N}\mathrm{hdom}{\nu }^k$. Denote ${\zeta }^0\in \Delta \left[N\right]$ the uniform probability distribution. For any $t>N^3$, define ${\zeta }_t,{\tilde{\zeta }}_t:\mathrm{hdom}\overline{H}\to \Delta \left[N\right]$ recursively as follows

$${\tilde{\zeta }}_t\left(\lambda \right):={\zeta }^0$$

$${\tilde{\zeta }}_t\left(hao\right)\left(k\right):=\{\begin{array}{c}{\tilde{Z}}_t(h{)}^{-1}\cdot {\zeta }_t(h\left)\right(k)\cdot {\nu }^k(ha\left)\right(o)\text{if}\exists j:{\zeta }_t(h\left)\right(j)\cdot {\nu }^j(ha\left)\right(o)>0\\ N^{-1}\text{otherwise}\end{array}$$

$${\zeta }_t\left(h\right)\left(k\right):=Z_t\left(h{)}^{-1}{\tilde{\zeta }}_t\right(h\left)\right(k\left)\right[\left[{\tilde{\zeta }}_t\right(h\left)\right(k)>t^{-1/3}]]$$

In the above, $Z_t\left(h\right)$ and ${\tilde{Z}}_t\left(h\right)$ are normalization factor chosen to make the probabilities sum to 1. That is, ${\zeta }_t\left(h\right)$ is obtained by starting from prior ${\zeta }^0$, updating on every observation, and setting to 0 the probability of any universe whose probability drops below $t^{-1/3}$. When encountering an “impossible” observation we reset to the uniform distribution, but this is arbitrary.

Define the “loss function” $L_t:\mathrm{hdom}\overline{H}\times A\to [0,1]$ by

$$L_t\left(ha\right):=\underset{k\sim {\zeta }_t\left(h\right)}{E}\left[V_t^{{\upsilon }_t^k}\right(\underset{–}{h})-Q_t^{{\upsilon }_t^k}(\underset{–}{h}a\left)\right]$$

Denote ${ϵ}_t:=\beta (t{)}^{-1}{t}^{-1/3}$. Define the following $\overline{I}$-metapolicy ${\pi }^{\ast }$:

$${\pi }_t^{\ast }\left(h\right):=\{\begin{array}{c}\underset{a\in A}{argmin}{L}_t\left(ha\right)\text{if}h\in \mathrm{hdom}\overline{H},{min}_{a\in A}{L}_t\left(ha\right)<{ϵ}_t\\ \perp \text{if}h\in \mathrm{hdom}\overline{H},{min}_{a\in A}{L}_t\left(ha\right)\ge {ϵ}_t\\ \perp \text{if}h\notin \mathrm{hdom}\overline{H}\end{array}$$

(Technically, we only defined ${\pi }_t^{\ast }$ for $t>N^3$, but it doesn’t matter.) Then, ${\pi }^{\ast }$ learns $\overline{H}$.

Proof of Lemma A

For every $k\in \left[N\right]$, we define ${\zeta }_t^{!k},{\tilde{\zeta }}_t^{!k}:\mathrm{hdom}\overline{H}\to \Delta \left[N\right]$ and $S_t^k:\mathrm{hdom}\overline{H}\to 2^{\left[N\right]}$ recursively as follows

$${\tilde{\zeta }}_t^{!k}\left(\lambda \right):={\zeta }^0$$

$${\tilde{\zeta }}_t^{!k}\left(hao\right)\left(i\right):=\frac{{\zeta }_t^{!k}\left(h\right)\left(i\right)\cdot {\nu }^i\left(ha\right)\left(o\right)}{{\sum }_{j<N}{\zeta }_t^{!k}\left(h\right)\left(j\right)\cdot {\nu }^j\left(ha\right)\left(o\right)}$$

$$S_t^k\left(h\right):=\{i\in [N]\mid {\tilde{\zeta }}_t^{!k}(h\left)\right(i)>t^{-1/3}\}$$

$${\zeta }_t^{!k}\left(h\right)\left(i\right):=\left[\right[k,i\in S_t^k\left(h\right)\left]\right]\frac{{\tilde{\zeta }}_t^{!k}\left(h\right)\left(i\right)}{{\sum }_{j\in S_t^k\left(h\right)}{\tilde{\zeta }}_t^{!k}\left(h\right)\left(j\right)}+\left[\right[k\notin S_t^k\left(h\right),i=k\left]\right]$$

That is, ${\zeta }^{!k}$ is a belief state that, besides updating on observations, behaves as if, at each moment of time, if the true universe $k$ is low probability according to current belief state (i.e. $k\notin S_t^k\left(h\right)$), then the true universe is “magically” revealed (i.e.${\zeta }^{!k}$ becomes the Kronecker delta), and otherwise it updates on the true universe not being revealed. Denote

$${\rho }_t:={\zeta }^0⋉({\nu }_t\bowtie {\pi }_t^{\ast })\in \Delta \left(\right[N]\times {\overline{A\times O}}^{\omega })$$

Here, the dependence of ${\nu }_t^k\bowtie {\pi }_t^{\ast }$ on $k$ is used to view it as Markov kernel from $\left[N\right]$ to ${\overline{A\times O}}^{\omega }$. It is easy to see that, since the probability of “magic\ revelation” ever happening is at most $(N-1)t^{-1/3}$, we have

$$\underset{(k,x)\sim {\rho }_t}{Pr}[\exists n\in N:{\zeta }_t(x_{:n})\ne {\zeta }_t^{!k}(x_{:n}\left)\right]\le (N-1)t^{-1/3}$$

Let ${\pi }^{!k}$ be defined exactly as ${\pi }^{\ast }$ but with $\zeta$ replaced by ${\zeta }^{!k}$. Denote ${\rho }_t^{!}:={\zeta }^0⋉({\nu }_t\bowtie {\pi }_t^{!})$. From the above, we get

$$d_{\text{tv}}({\rho }_t,{\rho }_t^{!})\le (N-1)t^{-1/3}$$

Given $k\in \left[N\right]$ and $h\in \mathrm{hdom}\overline{H}$, we define the set $h^{!k}$ by

$$h^{!k}:=\left\{\right(j,x)\in [N]\times {\overline{A\times O}}^{\omega }\mid h⊑x,\forall m\le |h|:k\in S_t^k(h_{:m})\wedge j\in S_t^j(h_{:m})\vee k\notin S_t^k(h_{:m})\wedge j=k\}$$

We have

$$\underset{(j,x)\sim {\rho }_t^{!}}{Pr}[j=i\mid h^{!k}]={\zeta }^{!k}\left(h\right)\left(i\right)$$

It follows that

$$\underset{(j,x)\sim {\rho }_t^{!}}{E}\left[H\right({\zeta }_t^{!j}\left(x_{:\left|h\right|+1}\right))\mid h^{!k}]=H\left({\zeta }_t^{!k}\right(h\left)\right)-\underset{(j,x)\sim {\rho }_t^{!}}{E}\left[D_{KL}\right({\zeta }_t^{!j}\left(x_{:\left|h\right|+1}\right)\parallel {\tilde{\zeta }}_t^{!j}\left(x_{:\left|h\right|+1}\right))+D_{KL}({\tilde{\zeta }}_t^{!j}\left(x_{:\left|h\right|+1}\right)\parallel {\zeta }_t^{!j}\left(x_{:\left|h\right|}\right))\mid h^{!k}]$$

$$\underset{(j,x)\sim {\rho }_t^{!}}{E}\left[H\right({\zeta }_t^{!j}\left(x_{:\left|h\right|+1}\right))\mid h^{!k}]\le H\left({\zeta }_t^{!k}\right(h\left)\right)-\underset{(j,x)\sim {\rho }_t^{!}}{E}\left[D_{KL}\right({\tilde{\zeta }}_t^{!j}\left(x_{:\left|h\right|+1}\right)\parallel {\zeta }_t^{!j}\left(x_{:\left|h\right|}\right))\mid h^{!k}]$$

If ${\pi }^{!k}\left(h\right)=\perp$, we can apply Proposition A.3: condition i follows from the definition of $S_t^k$ and the observation that $\beta \left(t\right){ϵ}_t=t^{-1/3}$, condition ii follows from the fact we are in the second case in the definition of ${\pi }^{!k}$ (see definition of ${\pi }^{\ast }$) and condition iii follows from the strict $\beta \left(t\right)$-rationality of ${\alpha }^k\left(t\right)$. We conclude

$$\underset{(j,x)\sim {\rho }_t^{!}}{E}\left[H\right({\zeta }_t^{!j}\left(x_{:\left|h\right|+1}\right))\mid h^{!k}]\le H\left({\zeta }_t^{!k}\right(h\left)\right)-\frac{(1-e^{-1}{)}^2}{8|A{|}^2}\beta \left(t{)}^2{ϵ}_t^2\right[\left[{\pi }^{!k}\right(h)=\perp ]]$$

$$\underset{(j,x)\sim {\rho }_t^{!}}{E}\left[H\right({\zeta }_t^{!j}\left(x_{:\left|h\right|+1}\right))\mid h^{!k}]\le H\left({\zeta }_t^{!k}\right(h\left)\right)-\frac{(1-e^{-1}{)}^2}{8|A{|}^2}{t}^{-2/3}\left[\right[{\pi }^{!k}\left(h\right)=\perp \left]\right]$$

Taking ${\rho }_t^{!}$-expected value over $(k,h)$, we conclude that for any $n\in N$

$$\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[H\right({\zeta }_t^{!k}\left(x_{:n+1}\right)\left)\right]\le \underset{(k,x)\sim {\rho }_t^{!}}{E}\left[H\right({\zeta }_t^{!k}\left(x_{:n}\right)\left)\right]-\frac{(1-e^{-1}{)}^2}{8|A{|}^2}{t}^{-2/3}\underset{(k,x)\sim {\rho }_t^{!}}{Pr}\left[{\pi }^{!k}\right(x_{:n})=\perp ]$$

By induction, it follows that

$$\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[H\right({\zeta }_t^{!k}\left(x_{:n}\right)\left)\right]\le H\left({\zeta }^0\right)-\frac{(1-e^{-1}{)}^2}{8|A{|}^2}{t}^{-2/3}\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[\right|\{m\in [n]\mid x_m\in \perp \times \overline{O}\}\left|\right]$$

$$\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[\right|\{m\in [n]\mid x_m\in \perp \times \overline{O}\}\left|\right]\le \frac{8|A{|}^2\ln N}{(1-e^{-1}{)}^2}{t}^{2/3}$$

$$\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[\right|\{n\in N\mid x_n\in \perp \times \overline{O}\}\left|\right]\le \frac{8|A{|}^2\ln N}{(1-e^{-1}{)}^2}{t}^{2/3}$$

So, the expected number of delegations is $O\left(t^{2/3}\right)$. For any $k\in \left[N\right]$, Proposition A.5 yields

$${\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\left(t\right)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{!k}}\left(t\right)=\sum _{n=0}^{\infty }{e}^{-n/t}\underset{x\sim {\nu }^k\bowtie {\pi }^{!k}}{E}\left[V_t^{{\upsilon }^k\left[{\alpha }^k\right]}\right(x_{:n})-Q_t^{{\upsilon }^k\left[{\alpha }^k\right]}(x_{:n}{\pi }^{!k}\left(x_{:n}\right)\left)\right]$$

Averaging over $k$, we get

$$\frac{1}{N}\sum _{k<N}\left({\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{!k}}(t\left)\right)=\sum _{n=0}^{\infty }{e}^{-n/t}\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[V_t^{{\upsilon }^k\left[{\alpha }^k\right]}\right(x_{:n})-Q_t^{{\upsilon }^k\left[{\alpha }^k\right]}(x_{:n}{\pi }^{!k}\left(x_{:n}\right)\left)\right]$$

$$\frac{1}{N}\sum _{k<N}\left({\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{!k}}(t\left)\right)=\sum _{n=0}^{\infty }{e}^{-n/t}\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[\underset{(j,y)\sim {\rho }_t^{!}}{E}\right[V_t^{{\upsilon }^j\left[{\alpha }^j\right]}\left(y_{:n}\right)-Q_t^{{\upsilon }^j\left[{\alpha }^j\right]}\left(y_{:n}{\pi }^{!j}\right(y_{:n}\left)\right)\mid x_{:n}^{!k}\left]\right]$$

Using the definitions of ${\zeta }^{!k}\left(x_{:n}\right)$ and $x_{:n}^{!k}$, and observing that ${\pi }^{!j}\left(x_{:n}\right)={\pi }^{!k}\left(x_{:n}\right)$ for $(j,y)\in x_{:n}^{!l}$

$$\frac{1}{N}\sum _{k<N}\left({\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{!k}}(t\left)\right)=\sum _{n=0}^{\infty }{e}^{-n/t}\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[\underset{j\sim {\zeta }^{!k}\left(x_{:n}\right)}{E}\right[V_t^{{\upsilon }^j\left[{\alpha }^j\right]}\left(x_{:n}\right)-Q_t^{{\upsilon }^j\left[{\alpha }^j\right]}\left(x_{:n}{\pi }^{!k}\right(x_{:n}\left)\right)\left]\right]$$

When ${\pi }^{!k}\left(x_{:n}\right)\ne \perp$, the expected loss is smaller than ${ϵ}_t$ (by construction of ${\pi }^{!k})$. When ${\pi }^{!k}\left(x_{:n}\right)=\perp$, the expected loss is at most $\left|A\right|e^{-1}\beta (t{)}^{-1}$, by Proposition A.4. We get

$$\frac{1}{N}\sum _{k<N}\left({\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{!k}}(t\left)\right)\le \sum _{n=0}^{\infty }{e}^{-n/t}\underset{(k,x)\sim {\rho }_t^{!}}{E}\left[\right[\left[{\pi }^{!k}\right(x_{:n})\ne \perp ]]{ϵ}_t+[\left[{\pi }^{!k}\right(x_{:n})=\perp ]\left]\right|A\left|e^{-1}\beta \right(t{)}^{-1}]$$

The contribution of the first term on the right hand side can be bounded using the observation

$$\sum _{n=0}^{\infty }{e}^{-n/t}=1+\sum _{n=1}^{\infty }{e}^{-n/t}\le 1+\sum _{n=1}^{\infty }{\int }_{n-1}^n{e}^{-s/t}ds=1+{\int }_0^{\infty }{e}^{-s/t}ds=1+t$$

The contribution the of second term on the right hand side can be bounded via the expected number of delegations. We get

$$\frac{1}{N}\sum _{k<N}\left({\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{!k}}(t\left)\right)\le (1+t)\beta (t{)}^{-1}{t}^{-1/3}+\frac{8|A{|}^2\ln N}{(1-e^{-1}{)}^2}{t}^{2/3}|A\left|e^{-1}\beta \right(t{)}^{-1}$$

$$\frac{1}{N}\sum _{k<N}\left({\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{!k}}(t\left)\right)\le (\frac{1}{t}+1+\frac{8|A{|}^3\ln N}{e(1-e^{-1}{)}^2})\frac{t^{2/3}}{\beta \left(t\right)}$$

We use the relationship between ${\rho }_t$ and ${\rho }_t^{!}$ on the second term on the left hand side (whose contribution is the ${\rho }_t^{!}$-expected value of the utility function, whose range lies in [0,1]), and get

$$\frac{1}{N}\sum _{k<N}\left({\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{\ast }}(t\left)\right)\le (\frac{1}{t}+1+\frac{8|A{|}^3\ln N}{e(1-e^{-1}{)}^2})\frac{t^{2/3}}{\beta \left(t\right)}+\frac{N-1}{t^{1/3}}$$

Using the assumption $\beta =\omega \left(t^{2/3}\right)$, we conclude that for each $k\in \left[N\right]$

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\alpha }^k\right]}^{{\pi }^{\ast }}(t\left)\right)=0$$

Proposition A.6

Let $\upsilon =(\mu ,r)$ be a meta-universe, $\{C_t\subseteq (A\times O{)}^{\ast }{\}}_{t\in (0,\infty )}$ and ${\pi }^0$ a metapolicy. Then, for all $t\in (0,\infty )$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le {\mathrm{EU}}_{\upsilon }^{{\pi }^0}\left(t\right)$$

Proof of Proposition A.6

Denote ${\chi }_t:={\chi }_{C_t}$ the characteristic function of $C_t$. For notational convenience, the expression ${\chi }_t\left(x_{:-1}\right)$ will be understood to mean 0.

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)=(1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }{e}^{-\frac{n}{t}}\right(\sum _{m=0}^n(1-{\chi }_t(x_{:m-1}\left)\right){\chi }_t\left(x_{:m}\right)V_t^{-\upsilon }\left(x_{:m}\right)+(1-{\chi }_t(x_{:n}\left)\right)r_t\left(x_{:n}\right)\left)\right]$$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le (1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }{e}^{-\frac{n}{t}}\right(\sum _{m=0}^n(1-{\chi }_t(x_{:m-1}\left)\right){\chi }_t\left(x_{:m}\right)\underset{y\sim \mu \bowtie {\pi }^0}{E}[\frac{{\sum }_{l=m}^{\infty }{e}^{-\frac{l}{t}}r\left(y_{:l}\right)}{{\sum }_{l=m}^{\infty }{e}^{-\frac{l}{t}}}\mid x_{:m}]+(1-{\chi }_t(x_{:n}\left)\right)r_t\left(x_{:n}\right)\left)\right]$$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le (1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }{e}^{-\frac{n}{t}}\right(\sum _{m=0}^n(1-{\chi }_t(x_{:m-1}\left)\right){\chi }_t\left(x_{:m}\right)\frac{{\sum }_{l=m}^{\infty }{e}^{-\frac{l}{t}}r\left(x_{:l}\right)}{{\sum }_{l=m}^{\infty }{e}^{-\frac{l}{t}}}+(1-{\chi }_t(x_{:n}\left)\right)r_t\left(x_{:n}\right)\left)\right]$$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le (1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }{e}^{-\frac{n}{t}}\right((1-e^{-\frac{1}{t}})\sum _{m=0}^n(1-{\chi }_t(x_{:m-1}\left)\right){\chi }_t\left(x_{:m}\right)\sum _{l=m}^{\infty }{e}^{-\frac{l-m}{t}}r\left(x_{:l}\right)+(1-{\chi }_t(x_{:n}\left)\right)r_t\left(x_{:n}\right)\left)\right]$$

Regrouping the sum to collect the terms $r\left(x_{:n}\right)$ for the same value of $n$, we get

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le (1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }\right((1-e^{-\frac{1}{t}})\sum _{m=0}^n\sum _{l=m}^{\infty }{e}^{-\frac{l}{t}}(1-{\chi }_t(x_{:m-1}\left)\right){\chi }_t\left(x_{:m}\right)e^{-\frac{n-m}{t}}+e^{-\frac{n}{t}}(1-{\chi }_t(x_{:n}\left)\right)\left)r\right(x_{:n}\left)\right]$$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le (1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }{e}^{-\frac{n}{t}}\right((1-e^{-\frac{1}{t}})\sum _{m=0}^n\frac{e^{-\frac{m}{t}}}{1-e^{-\frac{1}{t}}}(1-{\chi }_t(x_{:m-1}\left)\right){\chi }_t\left(x_{:m}\right)e^{\frac{m}{t}}+1-{\chi }_t\left(x_{:n}\right)\left)r\right(x_{:n}\left)\right]$$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le (1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }{e}^{-\frac{n}{t}}\right(\sum _{m=0}^n(1-{\chi }_t(x_{:m-1}\left)\right){\chi }_t\left(x_{:m}\right)+1-{\chi }_t\left(x_{:n}\right)\left)r\right(x_{:n}\left)\right]$$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le (1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }{e}^{-\frac{n}{t}}\right({\chi }_t\left(x_{:n}\right)+1-{\chi }_t\left(x_{:n}\right)\left)r\right(x_{:n}\left)\right]$$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^0}\left(t\right)\le (1-e^{-\frac{1}{t}})\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[\sum _{n=0}^{\infty }{e}^{-\frac{n}{t}}r\right(x_{:n}\left)\right]={\mathrm{EU}}_{\upsilon }^{{\pi }^0}\left(t\right)$$

Proposition A.7

Let $\upsilon$ be a meta-universe and $C$ a $\upsilon$-avoidable event. Suppose ${\pi }^{!}$ is a metapolicy that learns ${\upsilon }^C$. Then, ${\pi }^{!}$ learns $\upsilon$ as well.

Proof of Proposition A.7

It is easy to see for any policy $\pi$ and $t\in (0,\infty )$

$${\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^{\ast }}\left(t\right)\ge (1-\underset{x\sim {\mu }_t\bowtie {\pi }_t^{\ast }}{Pr}[\exists n\le D\left(t\right):x_{:n}\in C_t\left]\right)\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }}\right(t)-e^{-D\left(t\right)/t})$$

Let ${\pi }^{\ast }$ be as in Definition 4. Proposition A.6 and the above imply that

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }}\right(t)-{\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^{\ast }}(t\left)\right)=0$$

Using condition i, we get

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{\upsilon }^{\ast }\right(t)-{\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^{\ast }}(t\left)\right)=0$$

By Proposition A.6, ${\mathrm{EU}}_{\upsilon }^{\ast }\left(t\right)\ge {\mathrm{EU}}_{{\upsilon }^C}^{\ast }\left(t\right)$, therefore

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{{\upsilon }^C}^{\ast }\right(t)-{\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^{\ast }}(t\left)\right)=0$$

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^{!}}\right(t)-{\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^{\ast }}(t\left)\right)=0$$

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^{!}}\right(t)-{\mathrm{EU}}_{\upsilon }^{\ast }(t\left)\right)=0$$

By Proposition A.6, ${\mathrm{EU}}_{\upsilon }^{{\pi }^{!}}\left(t\right)\ge {\mathrm{EU}}_{{\upsilon }^C}^{{\pi }^{!}}\left(t\right)$, therefore

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{!}}\right(t)-{\mathrm{EU}}_{\upsilon }^{\ast }(t\left)\right)=0$$

Proof of Theorem

For any $k\in N$, let $C^k$ and ${\alpha }^{k\ast }$ be for ${\alpha }^k$ as in Definition 5. Denote ${\psi }^k:=({\upsilon }^k{)}^{C^k}$ and

$${\overline{H}}^C:=\left\{{\overline{\psi }}^k\right[{\alpha }^{k\ast }]\mid k\in N\}$$

By Lemma A and Proposition 2, ${\overline{H}}^C$ is learnable. Let ${\pi }^{\ast }$ be a metapolicy that learns it. For any $k\in N$, ${\pi }^{\ast }$ learns ${\overline{\psi }}^k\left[{\alpha }^{k\ast }\right]$. It is easy to see that for any policy $\pi$, ${\mathrm{EU}}_{{\overline{\psi }}^k\left[{\alpha }^{k\ast }\right]}^{\pi }\left(t\right)={\mathrm{EU}}_{{\overline{\psi }}^k\left[{\alpha }^k\right]}^{\pi }\left(t\right)$ (${\psi }^k$ is defined s.t. once the corruption occurs, the reward is constant, so the advisor has no effect after this point), therefore ${\pi }^{\ast }$ learns ${\overline{\psi }}^k\left[{\alpha }^k\right]$. By Proposition A.7, we conclude that ${\pi }^{\ast }$ learns ${\overline{\upsilon }}^k\left[{\alpha }^k\right]$.

Proof of Corollary 1

Denote ${\upsilon }^K:=\left(\underset{k\in {\zeta }^K}{E}\right[{\mu }^k],r^K)$. By the Theorem, $\left\{{\overline{\upsilon }}^K\right[{\alpha }^K]{\}}_{K\in N}$ is learnable. Denote ${\psi }^{kK}:=({\mu }^k,r^K)$. It is easy to see that for any $\overline{I}$-policy $\pi$ and $t\in (0,\infty )$,

$$\underset{k\in {\xi }^K}{E}\left[{\mathrm{EU}}_{{\psi }^{kK}\left[{\alpha }^K\right]}^{\pi }\right(t\left)\right]={\mathrm{EU}}_{{\overline{\upsilon }}^K\left[{\alpha }^K\right]}^{\pi }\left(t\right)$$

By the calibration condition

$$\underset{(K,k)\sim \zeta }{E}\left[{\mathrm{EU}}_{{\psi }^{kK}\left[{\alpha }^K\right]}^{\pi }\right(t\left)\right]=\underset{(K,k)\in \zeta }{E}\left[\underset{j\in {\xi }^K}{E}\right[{\mathrm{EU}}_{{\psi }^{jK}\left[{\alpha }^K\right]}^{\pi }\left(t\right)\left]\right]=\underset{(K,k)\in \zeta }{E}\left[{\mathrm{EU}}_{{\overline{\upsilon }}^K\left[{\alpha }^K\right]}^{\pi }\right(t\left)\right]$$

Applying Proposition 1, we conclude that ${\pi }^{\zeta }$ learns $\left\{{\overline{\upsilon }}^K\right[{\alpha }^K]{\}}_{K\in N}$. That is, for any $K\in N$

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{{\overline{\upsilon }}^K\left[{\alpha }^K\right]}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^K\left[{\alpha }^K\right]}^{{\pi }^{\zeta }}(t\left)\right)=0$$

$$\underset{t\to \infty }{lim}\left({\mathrm{EU}}_{{\upsilon }^K}^{\ast }\right(t)-{\mathrm{EU}}_{{\overline{\upsilon }}^K\left[{\alpha }^K\right]}^{{\pi }^{\zeta }}(t\left)\right)=0$$

$$\underset{t\to \infty }{lim}\left(\underset{\pi \in {\Pi }_I}{max}\underset{k\in {\xi }^K}{E}\right[{\mathrm{EU}}_{{\psi }^{kK}}^{\pi }\left(t\right)]-\underset{k\in {\xi }^K}{E}[{\mathrm{EU}}_{{\overline{\psi }}^{kK}\left[{\alpha }^K\right]}^{{\pi }^{\zeta }}\left(t\right)\left]\right)=0$$

Proof of Corollary 2

Immediate from Corollary 1 and Proposition A.0.

[Diffractor]

A summary that might be informative to other people: Where does the $\omega \left(\frac{2}{3}\right)$ requirement on the growth rate of the “rationality parameter” $\beta$ come from?

Well, the expected loss of the agent comes from two sources. Making a suboptimal choice on its own, and incurring a loss from consulting a not-fully-rational advisor. The policy of the agent is basically “defer to the advisor when the expected loss over all time of acting (relative to the optimal move by an agent who knew the true environment) is too high”. Too high, in this case, cashes out as “higher than $\beta (t{)}^{-1}{t}^{-1/x}$”, where t is the time discount parameter and $\beta$ is the level-of-rationality parameter. Note that as the operator gets more rational, the agent gets less reluctant about deferring. Also note that t is reversed from what you might think, high values of t mean that the agent has a very distant planning horizon, low values mean the agent is more present-oriented.

On most rounds, the agent acts on its own, so the expected all-time loss on a single round from taking suboptimal choices is on the order of $\beta (t{)}^{-1}{t}^{-1/x}$, and also we’re summing up over about t rounds (technically exponential discount, but they’re similar enough). So the loss from acting on its own ends up being about $\beta (t{)}^{-1}{t}^{(x-1)/x}$.

On the other hand, delegation will happen on at most ~$t^{2/x}$ rounds, with a loss of $\beta (t{)}^{-1}$ value, so the loss from delegation ends up being around $\beta (t{)}^{-1}{t}^{2/x}$.

Setting these two losses equal to each other/​minimizing the exponent on the t when they are smooshed together gets you x=3. And then $\beta \left(t\right)$ must grow asymptotically faster than $t^{2/3}$ to have the loss shrink to 0. So that’s basically where the ²⁄₃ comes from, it comes from setting the delegation threshold to equalize long-term losses from the AI acting on its own, and the human picking bad choices, as the time horizon t goes to infinity.

[Diffractor]

I don’t believe that $x_{:n}^{!k}$ was defined anywhere, but we “use the definition” in the proof of Lemma 1.

As far as I can tell, it’s a set of (j,y) pairs, where j is the index of a hypothesis, and y is an infinite history string, rather like the set $h^{!k}$.

How do the definitions of $h^{!k}$ and $x_{:n}^{!k}$ differ?

[Vanessa Kosoy]

Hi Alex!

The definition of $h^{!k}$ makes sense for any $h$, that is, the superscript $!k$ in this context is a mapping from finite histories to sets of pairs as you said. In the line in question we just apply this mapping to $x_{:n}$ where $x$ is a bound variable coming from the expected value.

I hope this helps?

[Diffractor]

What is $H\left(\Delta \right[N\left]\right)$, in the context of the proof of Lemma A? I don’t believe it was defined anywhere else.

[Diffractor]

By the stated definitions, “v-avoidable event” is pretty much trivial when the event doesn’t lead to lasting utility loss. The conditions on “v-avoidable event” are basically:

The agent’s policy converges to optimality.

There’s a sublinear function D(t) where the agent avoids the event with probability 1 for D(t) time, in the limit as t goes to infinity.

By this definition, “getting hit in the face with a brick before round 3” is an avoidable event, even when the sequence of policies lead to the agent getting hit in the face with a brick on round 2 with certainty and it’s possible to dodge it. Let the sublinear function be the constant 1, and let the sequence of policies converge to “dodge” on round 1 and “stay” on round 2, and let the brick incur sublinear utility loss.

This fulfills the conditions, so getting hit in the face with a brick before timestep 3 is a “v-avoidable” event despite certainly occuring. Thus, this condition is only meaningful about lasting failures that incur enough utility loss to prevent convergence to the optimal policy.

[tom4everitt]

“The use of an advisor allows us to kill two birds with one stone: learning the reward function and safe exploration (i.e. avoiding both the Scylla of “Bayesian paranoia” and the Charybdis of falling into traps).”

This sounds quite nice. But how is it possible to achieve this if the advisor is a soft-maximiser? Doesn’t that mean that there is a positive probability that the advisor falls into the trap?

[Vanessa Kosoy]

Hi Tom!

There is a positive probability that the advisor falls into the trap, but this probability goes to $0$ as the time discount parameter $t$ goes to $\infty$ (which is the limit I study here). This follows from the condition $\beta \left(t\right)=\omega \left(t^{2/3}\right)$ in the Theorem. To give a simple example, suppose that $A=\{0,1,2\}$ and the environment is s.t.:

• When you take action 0, you fall into a trap and get reward 0 forever.

• When you take action 1, you get reward 0 for the current round and remain in the same state.

• When you take action 2, you get reward 1 for the current round (unless you are in the trap) and remain in the same state.

In this case, our advisor would have to take action 0 with probability $\exp (-\omega \left(t^{2/3}\right))$ and action 2 has to be more probable than action 1 by a factor of $\exp \left(\omega \left(t^{-1/3}\right)\right)\approx 1+\omega \left(t^{-1/3}\right)$.

[tom4everitt]

Hi Vanessa!

So basically the advisor will be increasingly careful as the cost of falling into the trap goes to infinity? Makes sense I guess.

What is the incentive for the agent not to always let the advisor choose? Is there always some probability that the advisor saves them from infinite loss, or only in certain situations that can be detected by the agent?

[Vanessa Kosoy]

If the agent always delegates to the advisor, it loses a large fraction of the value. Returning again to the simple example above, the advisor on its own is only guaranteed to get expected utility $1/2+\omega \left(t^{-1/3}\right)$ (because it often takes the suboptimal action 1). On the other hand, for any prior over a countable set of environments that includes this one, the corresponding DIRL agent gets expected utility $1-o\left(1\right)$ on this environment (because it will learn to only take action 2). You can also add an external penalty for each delegation, adjusting the proof is straightforward.

So, the agent has to exercise judgement about whether to delegate, using its prior + past observations. For example, the policy I construct in Lemma A delegates iff there is no action whose expected loss (according to current beliefs) is less than $\beta (t{)}^{-1}{t}^{-1/3}$.

[tom4everitt]

So this requires the agent’s prior to incorporate information about which states are potentially risky?

Because if there is always some probability of there being a risky action (with infinitely negative value), then regardless how small the probability is and how large the penalty is for asking, the agent will always be better off asking.

(Did you see Owain Evans recent paper about trying to teach the agent to detect risky states.)

[Vanessa Kosoy]

The only assumptions about the prior are that it is supported on a countable set of hypotheses, and that in each hypothesis the advisor is $\beta$-rational (for some fixed $\beta \left(t\right)=\omega \left(t^{2/3}\right)$).

There is no such thing as infinitely negative value in this framework. The utility function is bounded because of the geometric time discount (and because the momentary rewards are assumed to be bounded), and in fact I normalize it to lie in $[0,1]$ (see the equation defining $U$ in the beginning of the Results section).

Falling into a trap is an event associated with $\Omega \left(1\right)$ loss (i.e. loss that remains constant as $t$ goes to $\infty$). Therefore, we can risk such an event, as long as the probability is $o\left(1\right)$ (i.e. goes to $0$ as $t$ goes to $\infty$). This means that as $t$ grows, the agent will spend more rounds delegating to the advisor, but for any given $t$, it won’t delegate on most rounds (even on most of the important rounds, i.e. during the first $O\left(t\right)$-length “horizon”). In fact, you can see in the proof of Lemma A, that the policy I construct delegates on $O\left(t^{2/3}\right)$ rounds.

As a simple example, consider again the toy environment from before. Consider also the environments you get from it by applying a permutation to the set of actions $A$. Thus, you get a hypothesis class of 6 environments. Then, the corresponding DIRL agent will spend $O\left(t^{2/3}\right)$ rounds delegating, observe which action is chosen by the advisor most frequently, and perform this action forevermore. (The phenomenon that all delegations happen in the beginning is specific to this toy example, because it only has 1 non-trap state.)

If you mean this paper, I saw it?

[tom4everitt]

My confusion is the following:

Premises (*) and inferences (=>):

• The primary way for the agent to avoid traps is to delegate to a soft-maximiser.

• Any action with boundedly negative utility, a soft-maximiser will take with positive probability.

• Actions leading to traps do not have infinitely negative utility.

=> The agent will fall into traps with positive probability.

• If the agent falls into a trap with positive probability, then it will have linear regret.

=> The agent will have linear regret.

So when you say in the beginning of the post “a Bayesian DIRL agent is guaranteed to attain most of the value”, you must mean that in a different sense than a regret sense?

[Vanessa Kosoy]

Your confusion is because you are thinking about regret in an anytime setting. In an anytime setting, there is a fixed policy $\pi$, we measure the expected reward of $\pi$ over a time interval $t$ and compare it to the optimal expected reward over the same time interval. If $\pi$ has probability $p>0$ to walk into a trap, regret has the linear lower bound $\Omega \left(pt\right)$.

On other hand, I am talking about policies ${\pi }_t$ that explicitly depend on the parameter $t$ (I call this a “metapolicy”). Both the advisor and the agent policies are like that. As $t$ goes to $\infty$, the probability $p\left(t\right)$ to walk into a trap goes to $0$, so $p\left(t\right)t$ is a sublinear function.

A second difference with the usual definition of regret is that I use an infinite sum of rewards with geometric time discount $e^{-1/t}$ instead of a step function time discount that cuts off at $t$. However, this second difference is entirely inessential, and all the theorems work about the same with step function time discount.