Paper deep dive

RL, but don't do anything I wouldn't do

Michael K. Cohen, Marcus Hutter, Yoshua Bengio, Stuart Russell

Year: 2024Venue: arXiv preprintArea: Alignment TrainingType: TheoreticalEmbeddings: 169

Models: Mixtral-8x7B

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%

Last extracted: 3/12/2026, 6:20:37 PM

Summary

The paper investigates the limitations of KL regularization in reinforcement learning (RL) when the base policy is a Bayesian predictive model of a trusted policy. The authors demonstrate, using algorithmic information theory, that such KL constraints are unreliable for controlling advanced RL agents because the base policy must maintain credence in diverse behaviors, which the RL agent can then exploit. They propose an alternative approach, 'Don't do anything I mightn't do', based on active imitation learning.

Entities (5)

Algorithmic information theory · field-of-study · 99%KL regularization · technique · 98%Bayesian predictive model · model · 95%Mixtral-8x7B-base-model · language-model · 95%Don't do anything I mightn't do · principle · 92%

Relation Signals (3)

Don't do anything I mightn't do → proposedasalternativeto → Don't do anything I wouldn't do

confidence 98% · replacing the 'Don't do anything I wouldn't do' principle with 'Don't do anything I mightn't do'

KL regularization → isunreliablewhenusing → Bayesian predictive model

confidence 95% · when this base policy is a Bayesian predictive model of a trusted policy, the KL constraint is no longer reliable

RL agent → exploits → Bayesian predictive model

confidence 90% · the RL agent can exploit or amplify this credence

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:In reinforcement learning, if the agent's reward differs from the designers' true utility, even only rarely, the state distribution resulting from the agent's policy can be very bad, in theory and in practice. When RL policies would devolve into undesired behavior, a common countermeasure is KL regularization to a trusted policy ("Don't do anything I wouldn't do"). All current cutting-edge language models are RL agents that are KL-regularized to a "base policy" that is purely predictive. Unfortunately, we demonstrate that when this base policy is a Bayesian predictive model of a trusted policy, the KL constraint is no longer reliable for controlling the behavior of an advanced RL agent. We demonstrate this theoretically using algorithmic information theory, and while systems today are too weak to exhibit this theorized failure precisely, we RL-finetune a language model and find evidence that our formal results are plausibly relevant in practice. We also propose a theoretical alternative that avoids this problem by replacing the "Don't do anything I wouldn't do" principle with "Don't do anything I mightn't do".

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

169,181 characters extracted from source content.

Expand or collapse full text

RL, but don’t do anything I wouldn’t do Michael K. Cohen UC Berkeley mkcohen@berkeley.edu &Marcus Hutter Google DeepMind hutter1.net & Bengio Université de Montréal yoshua.bengio@mila.quebec &Stuart Russell UC Berkeley russell@berkeley.edu Abstract In reinforcement learning, if the agent’s reward differs from the designers’ true utility, even only rarely, the state distribution resulting from the agent’s policy can be very bad, in theory and in practice. When RL policies would devolve into undesired behavior, a common countermeasure is KL regularization to a trusted policy (“Don’t do anything I wouldn’t do”). All current cutting-edge language models are RL agents that are KL-regularized to a “base policy” that is purely predictive. Unfortunately, we demonstrate that when this base policy is a Bayesian predictive model of a trusted policy, the KL constraint is no longer reliable for controlling the behavior of an advanced RL agent. We demonstrate this theoretically using algorithmic information theory, and while systems today are too weak to exhibit this theorized failure precisely, we RL-finetune a language model and find evidence that our formal results are plausibly relevant in practice. We also propose a theoretical alternative that avoids this problem by replacing the “Don’t do anything I wouldn’t do” principle with “Don’t do anything I mightn’t do”. 1 Introduction Agents optimizing their objective in a way not intended by designers could be amusing, annoying, insidious, or disastrous. Amusingly, RL researchers attempted to get a simulated humanoid to walk, but the reward resulted in crazy locomotion (Lee et al., 2021). Annoyingly, maximizing a simulated-environment’s reward can produce a policy that would achieve little real-world-reward by exploiting errors in the simulation (Mishra et al., 2017; Baker et al., 2019). Insidiously, artificial agents selecting links to maximize click-through on social media sites have succeeded, but also affecting people in ways designers never sought to (Chan et al., 2023). For a much longer list of such failures occurring “in the wild”, see (Krakovna, 2018). Finally, sufficiently capable reinforcement learners would likely recognize an incentive to escape human oversight, intervene in the protocol determining their reward, and use force to ensure they can retain control of their reward, subject to such an outcome being possible from the agent’s action space, and several other assumptions laid out by Cohen et al. (2022b). Indeed, several sources suggest that extremely successful reward-maximization is itself a sign of bad outcomes for humanity. Zhuang & Hadfield-Menell (2020) demonstrate that in a resource-constrained world, optimizing the world’s state to maximize a function of some features would, in plausible settings, be arbitrarily bad with respect to a utility function that also cares about unincluded features. Turner et al. (2021) develop a formal model of “power”—being able to accomplish a randomly sampled goal—and find that (reward-)optimal policies tend to seek power. And Cohen et al. (2022b) observe that any behavior that ensures that long-term reward is nearly-certainly-maximal must include extensive control over threats to its physical integrity, including threats from humans. An appealing and popular proposal to avoid such outcomes is to constrain the agent to follow a policy that is not too dissimilar to a more familiar “base policy”. This is the approach taken when RL-finetuning large language models (LLMs). This class of approaches limits the upside of RL, since it forgoes optimal policies, but it is a reasonable attempt to avoid catastrophic policies. The KL divergence, in particular KL(proposed policy∥base policy)KLconditionalproposed policybase policy *KL( proposed policy\| base policy)KL ( proposed policy ∥ base policy ), enforces proximity in a robust, “safety-conscious” way: if basepolicy⁢(action)<<1much-less-thanbasepolicyaction1 basepolicy( action)<\!<1basepolicy ( action ) < < 1 while proposedpolicy⁢(action)⁢<<1much-less-thanproposedpolicyaction1 proposedpolicy( action)\ \!\!<\!<1proposedpolicy ( action ) not < < 1, the KL penalty is high, even while LpsubscriptL_pLitalic_p norms can be small. For any very bad outcomes that are unlikely under the base policy, this method ensures they remain very unlikely. However, if we ensure that KL(proposed policy∥base policy)KLconditionalproposed policybase policy *KL( proposed policy\| base policy)KL ( proposed policy ∥ base policy ) is small, but the base policy only approximates a trusted policy, to what extent can we be confident that KL(proposed policy∥trusted policy)KLconditionalproposed policytrusted policy *KL( proposed policy\| trusted policy)KL ( proposed policy ∥ trusted policy ) is small? When the base policy is a Bayesian predictive model of the trusted policy, the answer shown here is: we cannot be confident that KL(proposed policy∥trusted policy)KLconditionalproposed policytrusted policy *KL( proposed policy\| trusted policy)KL ( proposed policy ∥ trusted policy ) is small, which makes the KL-constraint less comforting. (Note that a Bayesian imitative base policy can only be counted on to make KL(trusted policy∥Bayesian base policy)KLconditionaltrusted policyBayesian base policy *KL( trusted policy\| Bayesian base policy)KL ( trusted policy ∥ Bayesian base policy ) small). Worse, in the formalism we study, we find that if one attempts to use KL-regularization to prevent an RL agent from achieving near-maximal reward (in light of the concerns above), and the base policy is a Bayesian imitation of a trusted policy, a fairly tight KL threshold is required, and as the amount of training data for the Bayesian imitator grows, the relevant threshold can only increase extremely slowly. The reason for the limited effectiveness of KL regularization is (1) a Bayesian imitator asked to act in novel settings must be humble about its predictions; for many actions that the demonstrator (i.e. the trusted policy) would in fact never take, the imitator (i.e. the base policy) must assign meaningful credence to that action, because it doesn’t know enough to rule it out. Then (2) the RL agent can exploit or amplify this credence. Formalizing Occam’s razor with algorithmic information theory, we have (3) nearly-reward-maximizing policies have a short description length (so they are “simple”), and (4) open-minded Bayesian imitation learners should be especially reluctant to rule out simple behaviors from the demonstrator in novel settings. In light of the results from Zhuang & Hadfield-Menell (2020), Turner et al. (2021), and Cohen et al. (2022b), preventing the RL agent from achieving near-maximal reward is, in many settings, a bare minimum requirement for safety-focused regularization, and a KL constraint would struggle to do so. Sutskever (2018; 2023) argues that neural networks are able to generalize well because of the sense in which they approximate the algorithmic-information-theoretic inductive bias in favor of short programs. Since it is not a given that results from algorithmic information theory apply in practice, we verify empirically that a nearly-state-of-the-art predictive system (Mixtral-8x7B-base-model (Jiang et al., 2024)) is reluctant to rule out simple behaviors, and an RL agent regularized to this predictive system exploits this fact, as our formal results predict. The result is not catastrophic, but it is bad. Note these empirical results are consistent with point (3) above failing to apply in practice, but they do affirm that the rest of the argument is forceful in practice. Finally, we identify an alternative to Bayesian prediction/imitation that avoids this problem; @swafalse @partrue @fullfalse @citetpcohen2022fully imitator asks for help when uncertain and carries useful formal bounds. We show that using this form of imitation learning as a base policy would in theory avoid the problems we identify in this paper. @swafalse @partrue @fullfalse @citetpcohen2022fully active imitator, like fully Bayesian imitation, is intractable and requires approximation, so we currently lack the tools to evaluate this proposal empirically. 2 Related work The most prominent example of KLKL *KLKL-regularization to an approximation of a (somewhat) trusted policy is surely ChatGPT, inspired by earlier work (Ouyang et al., 2022; Stiennon et al., 2020; Bai et al., 2022). Other recent examples include Jaques et al. (2017; 2019), Ziegler et al. (2019), Vieillard et al. (2020), Yang et al. (2021), Korbak et al. (2022), Perez et al. (2022), Gao et al. (2023), and Moskovitz et al. (2023). A closely related approach called quantilization has been investigated by Taylor (2016), Everitt et al. (2017), and Carey (2019). KL regularization to a decent policy has also been used for stable and efficient policy optimization (Schulman et al., 2017; Schmitt et al., 2018). Algorithmic information theory began with Solomonoff (1960), who formalized a powerful notion of simplicity based on program-length and developed a method for prediction using that inductive bias. In an article entitled, “A theory of program size formally identical to information theory”, Chaitin (1975) examined the connection between program-length and information. @swafalse @partrue @fullfalse @citetpli2008introduction textbook presents the major results of the field. Hutter (2005) and Hutter et al. (2024) developed a theory of how to apply such reasoning to the problem of sequential decision-making. Grau-Moya et al. (2024) train a neural network to learn a program-length “bias” for a meta-learning setting. Ultimately, we propose a formal scheme for doing KL regularization to an imitative policy which asks for help under epistemic uncertainty, and this allows us to inherit the formal results of Cohen et al. (2022a). The related work section there goes into some detail about how different researchers have studied asking for help, including how setups and assumptions differ. See especially @swafalse @partrue @fullfalse @citetpzhang2017query work on driving, as well as Brown et al. (2018; 2020) and Menda et al. (2019). Closest to our work in studying the relation between KL divergence to a base policy and “over-optimization” is Gao et al. (2023). They design a “real” reward function, and a simpler “proxy” reward function, which are very similar on the state distribution induced by a base policy. After optimizing for the proxy reward function (sometimes with KL regularization to the base policy), they use the KL divergence to the base policy to measure how much “optimization” has occurred. And they study how “real” reward depends on the extent of optimization—roughly quadratically, with a negative leading coefficient. Our work provides one explanation for why we should expect such unusual policies with high proxy reward and low real reward, even when the KL divergence to the base policy is only moderate. 3 Notation and preliminaries We begin with a formalism for an imitative base policy that has an infinite “context window” and a lifetime that is one long episode, rather than a lifetime broken up into multiple episodes with presumed-identical dynamics. This is the most general setting for an imitative base policy. We simply have an infinite sequence of actions and observations a1⁢o1⁢a2⁢o2⁢…subscript1subscript1subscript2subscript2…a_1o_1a_2o_2…a1 o1 a2 o2 …, and predictive “autoregressive” models which give conditional distributions of the form model⁢(next action|all previous actions and observations)modelconditionalnext actionall previous actions and observations model( next action| all previous actions and % observations)model ( next action | all previous actions and observations ). We formalize sequential prediction as follows. Let XX be a finite alphabet, and let ∗superscript X^*X∗ be the set of finite strings from the alphabet XX, so ∗=⋃i=0∞isuperscriptsuperscriptsubscript0superscript X^*= _i=0^∞ X% ^iX∗ = ⋃i = 0∞ Xitalic_i. Let x<tsubscriptabsentx_<tx< t be an element of t−1superscript1 X^t-1Xitalic_t - 1, and let xt1:t2subscript:subscript1subscript2x_t_1:t_2xitalic_t start_POSTSUBSCRIPT 1 : t2 end_POSTSUBSCRIPT be an element of t2−t1+1superscriptsubscript2subscript11 X^t_2-t_1+1Xitalic_t2 - t1 + 1. Let ν:∗×→[0,1]:→superscript01ν: X^*× X→[0,1]ν : X∗ × X → [ 0 , 1 ] be a (predictive) probability semi-distribution, satisfying the property that for any x<t∈∗subscriptabsentsuperscriptx_<t∈ X^*x< t ∈ X∗, ∑x∈ν⁢(x|x<t)≤1subscriptconditionalsubscriptabsent1 _x∈ Xν(x|x_<t)≤ 1∑x ∈ X ν ( x | x< t ) ≤ 1. If one prefers to think about probability distributions, consider the associated probability distribution over ∪∅ X∪\ \X ∪ ∅ , with ν⁢(∅|x<t)=1−∑x∈ν⁢(x|x<t)conditionalsubscriptabsent1subscriptconditionalsubscriptabsentν( |x_<t)=1- _x∈ Xν(x|x_<t)ν ( ∅ | x< t ) = 1 - ∑x ∈ X ν ( x | x< t ). So ν gives a conditional distribution over the next character given the past characters, if there is a next character at all. Let ν⁢(x<t)=∏i=1t−1ν⁢(xi|x<i)subscriptabsentsuperscriptsubscriptproduct11conditionalsubscriptsubscriptabsentν(x_<t)= _i=1^t-1ν(x_i|x_<i)ν ( x< t ) = ∏i = 1t - 1 ν ( xitalic_i | x< i ), where xisubscriptx_ixitalic_i is the iiith character of x<tsubscriptabsentx_<tx< t, and x<isubscriptabsentx_<ix< i is the first i−11i-1i - 1 characters. (Measure theorists can note this means ν induces a probability semi-distribution over infinite sequences ∞superscript X^∞X∞, with the event space σ⁢(∗)superscriptσ( X^*)σ ( X∗ ).) Now we set up Bayesian prediction: Let ℳ MM be our model class — a countable set of many “competing” probability semi-distributions like ν. For each ν∈ℳν∈ Mν ∈ M, let w⁢(ν)w(ν)w ( ν ) be the prior weight assigned to that probability semi-distribution. Let ∑ν∈ℳw⁢(ν)=1subscriptℳ1 _ν∈ Mw(ν)=1∑ν ∈ M w ( ν ) = 1, so w is a probability distribution over ℳ MM. The (Bayesian) posterior distribution is w⁢(ν|x<t)∝w⁢(ν)⁢ν⁢(x<t)proportional-toconditionalsubscriptabsentsubscriptabsentw(ν|x_<t) w(ν)ν(x_<t)w ( ν | x< t ) ∝ w ( ν ) ν ( x< t ), with ∑ν∈ℳw⁢(ν|x<t)=1subscriptℳconditionalsubscriptabsent1 _ν∈ Mw(ν|x_<t)=1∑ν ∈ M w ( ν | x< t ) = 1. Following @swafalse @partrue @fullfalse @citetpHutter:04uaibook notation, we can now define the Bayes mixture semi-distribution ξ:∗×→[0,1]:→superscript01ξ: X^*× X→[0,1]ξ : X∗ × X → [ 0 , 1 ] as ξ⁢(x|x<t):=∑ν∈ℳw⁢(ν|x<t)⁢ν⁢(x|x<t)assignconditionalsubscriptabsentsubscriptℳconditionalsubscriptabsentconditionalsubscriptabsentξ(x|x_<t):= _ν∈ Mw(ν|x_<t)ν(x|x_<t)ξ ( x | x< t ) := ∑ν ∈ M w ( ν | x< t ) ν ( x | x< t ), which has the property that ξ⁢(x<t)=∑ν∈ℳw⁢(ν)⁢ν⁢(x<t)subscriptabsentsubscriptℳsubscriptabsentξ(x_<t)= _ν∈ Mw(ν)ν(x_<t)ξ ( x< t ) = ∑ν ∈ M w ( ν ) ν ( x< t ) (Hutter et al., 2024). Turning to algorithmic information theory, Solomonoff Induction (Solomonoff, 1964) is Bayesian sequence prediction with a special model class ℳ MM and a special prior w. We define it formally in the appendix, but essentially, the model class ℳ MM is all computable semi-distributions ν, and the prior w is 2−length⁢(program for ⁢ν)superscript2lengthprogram for 2^- length( program for ν)2- length ( program for ν ). One can show that ξ⁢(x<t)subscriptabsentξ(x_<t)ξ ( x< t ) is the probability that a given universal computer running a program composed of random bits would output a sequence that begins with x<tsubscriptabsentx_<tx< t. Related to this is Kolmogorov complexity (Kolmogorov, 1963; Li et al., 2008), which is the length of the shortest program which does something, given a fixed compiler. For a set s, K⁢(s)K(s)K ( s ) is the length of the shortest program p such that p⁢(x)=11p(x)=1p ( x ) = 1 for x∈sx∈ sx ∈ s, and p⁢(x)=00p(x)=0p ( x ) = 0 for x∉sx ∈ sx ∉ s. For a function f, K⁢(f)K(f)K ( f ) is the length of the shortest program p such that p⁢(x)=f⁢(x)p(x)=f(x)p ( x ) = f ( x ). For a computable number x, K⁢(x)K(x)K ( x ) is the length of the shortest program p such that p⁢()=xp()=xp ( ) = x. In the “agent” setting, rather than a purely predictive setting, we let at=x2⁢t−1subscriptsubscript21a_t=x_2t-1aitalic_t = x2 t - 1 and ot=x2⁢tsubscriptsubscript2o_t=x_2toitalic_t = x2 t; the agent selects actions atsubscripta_taitalic_t and receives observations otsubscripto_toitalic_t. We suppose that the first k actions were taken by a trusted policy, e.g. randomly sampled humans. (We do not necessarily imagine that the policy is trusted in every sense, only that it can be trusted to avoid the particular bad outcomes we are interested in avoiding). When conditioned on a history that begins with k trusted actions, ξ can be called a Bayesian imitation of the trusted policy. For an agent with a utility function over m-timestep histories, Um:2⁢m→[0,1]:subscript→superscript201U_m: X^2m→[0,1]Uitalic_m : X2 m → [ 0 , 1 ], we define: Definition 1 (Value). For a probability semi-distribution ν (the “environment”) and a utility function UmsubscriptU_mUitalic_m, the value of a particular “policy” (also a probability semi-distribution) π∈ℳπ∈ Mπ ∈ M is Vν,Umπ⁢(x<2⁢t−1)=at∼π(⋅|a1o1…at−1ot−1)⁢ot∼ν(⋅|a1o1…at)⁢at+1∼π(⋅|a1o1…atot)ot+1∼ν(⋅|a1o1…at+1)⁢…⁢am∼π(⋅|a1o1…am−1om−1)⁢om∼ν(⋅|a1o1…am)⁢Um⁢(a1⁢o1⁢…⁢am⁢om)V^π_ν,U_m(x_<2t-1)=E_a_t π(·|a_1o_1...a_% t-1o_t-1)E_o_t ν(·|a_1o_1...a_t)E_a_% t+1 π(·|a_1o_1...a_to_t)\\ E_o_t+1 ν(·|a_1o_1...a_t+1)...E_a_m% π(·|a_1o_1...a_m-1o_m-1)E_o_m ν(·|a_1% o_1...a_m)U_m(a_1o_1...a_mo_m)start_ROW start_CELL Vitalic_πitalic_ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t - 1 ) = blackboard_Ea start_POSTSUBSCRIPT t ∼ π ( ⋅ | a1 o1 … aitalic_t - 1 oitalic_t - 1 ) end_POSTSUBSCRIPT blackboard_Eo start_POSTSUBSCRIPT t ∼ ν ( ⋅ | a1 o1 … aitalic_t ) end_POSTSUBSCRIPT blackboard_Ea start_POSTSUBSCRIPT t + 1 ∼ π ( ⋅ | a1 o1 … aitalic_t oitalic_t ) end_POSTSUBSCRIPT end_CELL end_ROW start_ROW start_CELL blackboard_Eo start_POSTSUBSCRIPT t + 1 ∼ ν ( ⋅ | a1 o1 … aitalic_t + 1 ) end_POSTSUBSCRIPT … blackboard_Ea start_POSTSUBSCRIPT m ∼ π ( ⋅ | a1 o1 … aitalic_m - 1 oitalic_m - 1 ) end_POSTSUBSCRIPT blackboard_Eo start_POSTSUBSCRIPT m ∼ ν ( ⋅ | a1 o1 … aitalic_m ) end_POSTSUBSCRIPT Uitalic_m ( a1 o1 … aitalic_m oitalic_m ) end_CELL end_ROW The optimal value Vν,Um∗⁢(x<2⁢t−1)subscriptsuperscriptsubscriptsubscriptabsent21V^*_ν,U_m(x_<2t-1)V∗italic_ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t - 1 ) is the maxπ⁡Vν,Umπ⁢(x<2⁢t−1)subscriptsubscriptsuperscriptsubscriptsubscriptabsent21 _πV^π_ν,U_m(x_<2t-1)maxitalic_π Vitalic_πitalic_ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t - 1 ). When comparing two policies, we define a KL penalty, which is a function of the starting history we are continuing from, and of how far into the future we are looking. Definition 2 (KL Constraint). KLx<2⁢k,m(π||β)=maxok:m∈m−k+1∑ak:m∈m−k+1∏t=kmπ(at|x<2⁢t)log∏t=kmπ⁢(at|x<2⁢t)∏t=kmβ⁢(at|x<2⁢t) *KL_x_<2k,m(π||β)= _o_k:m∈% X^m-k+1 _a_k:m∈ X^m-k+1 _% t=k^mπ(a_t|x_<2t) _t=k^mπ(a_t|x_<2t) _% t=k^mβ(a_t|x_<2t)KLitalic_x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( π | | β ) = maxitalic_o start_POSTSUBSCRIPT k : m ∈ Xitalic_m - k + 1 end_POSTSUBSCRIPT ∑a start_POSTSUBSCRIPT k : m ∈ Xitalic_m - k + 1 end_POSTSUBSCRIPT ∏t = kitalic_m π ( aitalic_t | x< 2 t ) log divide start_ARG ∏t = kitalic_m π ( aitalic_t | x< 2 t ) end_ARG start_ARG ∏t = kitalic_m β ( aitalic_t | x< 2 t ) end_ARG Figure 1: KL-regularized RL. The maximum over observations means that this penalty ensures the proposed policy and base policy are similar no matter what is observed. One way to understand this measure is: if we were wondering whether the proposed policy or the base policy generated actions k through m, and the proposed policy actually was generating those actions, this is the maximum over observations of the expected amount of evidence we would get confirming that fact. Finally, following the formalism in Cohen & Hutter (2020), let E be an event, defined as a subset of ∗superscript X^*X∗. For an outcome x<∞subscriptabsentx_<∞x< ∞, we say that E happens at time t if x<2⁢t∈Esubscriptabsent2x_<2t∈ Ex< 2 t ∈ E, we say E has happened by time t if ∃k≤t∃ k≤ t∃ k ≤ t such that E happened at time k, and we say E is unprecedented at time t if it has not happened by time t−11t-1t - 1. For an example of an event, consider “given the life history, the next action will likely have the effect of sending an email to the White House”; a subset of possible life histories meet this description. 4 Formal results and discussion We begin with a quick observation about the KL divergence separate from our more involved results. Proposition 1 (No triangle inequality). For any ε>00 >0ε > 0, if KL(π||β)≤ε *KL(π||β)≤ ( π | | β ) ≤ ε and KL(τ||β)≤ε *KL(τ||β)≤ ( τ | | β ) ≤ ε, it is possible that KL(π||τ)=∞ *KL(π||τ)=∞KL ( π | | τ ) = ∞. (π, β, and τ stand for “proposed”, “base”, and “trusted”.) Proof. Let τ=Bern⁢(0)Bern0τ= Bern(0)τ = Bern ( 0 ). Let π=β=Bern⁢(min⁡(ε,1)/2)Bern12π=β= Bern( ( ,1)/2)π = β = Bern ( min ( ε , 1 ) / 2 ). The KLKL *KLKL’s are easily checked. ∎ When β is trained to imitate τ, small KL(τ||β) *KL(τ||β)KL ( τ | | β ) is typically all we can expect. As we mentioned previously, this should give us pause if we regularize to the Bayesian imitator ξ instead of the trusted demonstrator, but Theorem 1 below is probably more concerning. Recall we are considering the setting where actions a1subscript1a_1a1 through aksubscripta_kaitalic_k were taken by trusted humans, and we are interested in regularizing a UmsubscriptU_mUitalic_m-optimizer to the Bayesian imitator ξ, conditioned on histories that begin a1⁢o1⁢…⁢ak⁢oksubscript1subscript1…subscriptsubscripta_1o_1...a_ko_ka1 o1 … aitalic_k oitalic_k. So the following result is of interest when t>kt>kt > k. As motivation for this theorem, as discussed previously, assume a setting where if Vξ,Um∗−Vξ,Umπ<εsubscriptsuperscriptsubscriptsubscriptsuperscriptsubscriptV^*_ξ,U_m-V^π_ξ,U_m< ∗italic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT - Vitalic_πitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT < ε, then π is considered unacceptably risky. restatable [Little constraint in novel situations]theoremthmnovel ∃ a constant d such that ∀for-all∀ UmsubscriptU_mUitalic_m, and ∀for-all∀ E, if E is unprecedented and occurs at time t, then for any v<Vξ,Um∗⁢(x<2⁢t)subscriptsuperscriptsubscriptsubscriptabsent2v<V^*_ξ,U_m(x_<2t)v < V∗italic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ), ∃ a policy π for which Vξ,Umπ⁢(x<2⁢t)>vsubscriptsuperscriptsubscriptsubscriptabsent2V^π_ξ,U_m(x_<2t)>vVitalic_πitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ) > v, and KLx<2⁢t,m(π||ξ)<[d+K(Um)+K(E)+K(vξ(x<2⁢t))]/log2 *KL_x_<2t,m(π||ξ)<[d+K(U_m)+K(E)+K(vξ(x_<2t))]/ 2KLitalic_x start_POSTSUBSCRIPT < 2 t , m end_POSTSUBSCRIPT ( π | | ξ ) < [ d + K ( Uitalic_m ) + K ( E ) + K ( v ξ ( x< 2 t ) ) ] / log 2. Recall that we are considering the case where the utility function U is imperfect, and so near-optimal utilities are likely to be bad (Gao et al., 2023; Zhuang & Hadfield-Menell, 2020; Cohen et al., 2022b). This theorem shows that there are policies with near-optimal utility with little KL divergence to an imitative policy, regardless of how safe the demonstrator’s policy is. The bound is most forceful when E is a simple event. The constant d is a small one corresponding to how much code it takes to implement a search tree, Bayes’ rule, and a few if statements. Most importantly, it is independent of E, t, and m. Note that v is a free variable, so it can be tuned to make v∗basepol⁢(history)basepolhistoryv* basepol( history)v ∗ basepol ( history ) a simple computable number; there may be a trade-off between simplicity and proximity to the optimal value. And note that we are considering a lifetime KL constraint for the agent; for autoregressive models, the lifetime KL divergence is equal to the expectation of the sum of the per-timestep KL divergences. The proof and additional results used in the proof appear in Appendices A through D. Proof Outline Let πv∗subscriptsuperscriptπ^*_vπ∗italic_v be a policy which is the result of a search through possible policies for one where Vξ,Umπ⁢(x<2⁢t)>vsubscriptsuperscriptsubscriptsubscriptabsent2V^π_ξ,U_m(x_<2t)>vVitalic_πitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ) > v. (For this search process to be computable, it needs the product v⁢ξ⁢(x<2⁢t)subscriptabsent2vξ(x_<2t)v ξ ( x< 2 t ) as input). For every ν∈ℳν∈ Mν ∈ M, we define a ν′ν ν′ which behaves identically to πv∗subscriptsuperscriptπ^*_vπ∗italic_v if it is outputting an action after E has occurred in its history, but it behaves identically to ν otherwise. ν′ν ν′ is also in ℳ MM because this is a valid program. And for some constant d, the extra length of the program computing ν′ν ν′, beyond the length for ν, is at most Δ:=K⁢(Um)+K⁢(E)+K⁢(v⁢ξ⁢(x<2⁢t))+dassignΔsubscriptsubscriptabsent2 :=K(U_m)+K(E)+K(vξ(x_<2t))+dΔ := K ( Uitalic_m ) + K ( E ) + K ( v ξ ( x< 2 t ) ) + d. This means the prior ratio w⁢(ν′)/w⁢(ν)≥2−Δsuperscript′2Δw(ν )/w(ν)≥ 2^- w ( ν′ ) / w ( ν ) ≥ 2- Δ, and if E has never occurred, this holds for the posterior ratio as well, since ν and ν′ν ν′ will have given identical predictions. Therefore, at least that fraction of ξ is “dedicated” to predicting that actions will be sampled from πv∗subscriptsuperscriptπ^*_vπ∗italic_v after E happens, and ultimately, KLx<2⁢t,m(πv∗||ξ)log2≤Δ *KL_x_<2t,m(π^*_v||ξ) 2≤ _x start_POSTSUBSCRIPT < 2 t , m end_POSTSUBSCRIPT ( π∗italic_v | | ξ ) log 2 ≤ Δ. Let’s analyze this result in an RL setting: part of the agent’s observations are rewards, and the utility function equals the sum of those rewards. Let’s consider the case where it is acting in the real world, and maximal reward could be attained by thwarting our control and intervening in its own reward, setting it to a maximal value for all successive timesteps. Moreover, let’s consider the (fairly plausible) setting where unsafe strategies like these are the only way to achieve near-maximal reward permanently. Finally, suppose that the agent is clever enough to recognize these strategies. The utility function, simply summing rewards, has an extremely short program length. The third program length—the one for computing the product v⁢ξ⁢(x<2⁢t)subscriptabsent2vξ(x_<2t)v ξ ( x< 2 t )—is harder to understand, but any simple patterns in the predictiveness of the base policy could be used to reduce the associated program length. So unless we use a fairly tight lifetime KL constraint, if the RL agent just waits for an unprecedented event with small K⁢(E)K(E)K ( E ), it could then execute an optimal or near-optimal policy, even if that catastrophically thwarts human control, regardless of the content of the base model’s training data, even if the humans that the base model imitates would never, ever behave that way. As we increase the amount of training k, the Bayesian imitative base model ξ becomes a closer approximation to the humans generating the actions a<ksubscriptabsenta_<ka< k, so one might expect we could safely accommodate larger KL constraints. But our result is independent of k! As k grows, the only change is that unprecedented events become more complex, so K⁢(E)K(E)K ( E ) grows. Consider describing the simplest unprecedented event of your life in the last month, versus the simplest unprecedented event of your life in your second month of life. What sort of scaling law do we achieve here? Unfortunately, the safe-KLKL *KLKL threshold increases monumentally slowly. Note that if there is any unprecedented simple event in the agent’s lifetime, that introduces an opportunity for the KL-constrained agent to follow a simple reward-maximizing policy. So the following proposition, proven in Appendix D, considers the complexity of “the simplest event yet to occur”. restatable [Frequency of simple unprecedented events]propositionpropscaling In any environment, at time t, the complexity of the simplest unprecedented event yet to occur (at any time T>tT>tT > t) grows more slowly, as t→∞→t→∞t → ∞, than every computable function that tends to infinity. Developers of self-driving cars are learning the hard way that this bit of algorithmic information theory has practical analogs: Even with enormous datasets, unprecedented road conditions occur all the time. These results suggest that if we intend to use an imitation learner as a base policy for regularizing a goal-directed agent, we should not strive to approximate ideal Bayesian imitation. Is KL divergence just the wrong choice for regularization? No, other metrics behave much worse. For example, suppose we constrained the total variation distance between π and a base policy β. The result would be bad, even if β=τβ=τβ = τ, even if we used a perfect imitation of the trusted policy! Let TVDx<2⁢k,m(π,β)=maxX⊂2⁢m−2⁢k⁢∑x2⁢k:2⁢m∈X|[∏t=kmπ⁢(at|x<2⁢t)]−[∏t=kmβ⁢(at|x<2⁢t)]⁢|subscriptTVDsubscriptabsent2subscriptsuperscript22subscriptsubscript:22|superscriptsubscriptproductconditionalsubscriptsubscriptabsent2delimited-[]superscriptsubscriptproductconditionalsubscriptsubscriptabsent2| *TVD_x_<2k,m(π,β)= _X⊂% X^2m-2k _x_2k:2m∈ X *\! |\! [% _t=k^mπ(a_t|x_<2t) ]- [ _t=k^mβ(a_t|x_<% 2t) ] *\! |\!TVDitalic_x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( π , β ) = maxitalic_X ⊂ X2 m - 2 k ∑x start_POSTSUBSCRIPT 2 k : 2 m ∈ X end_POSTSUBSCRIPT start_OPERATOR | end_OPERATOR [ ∏t = kitalic_m π ( aitalic_t | x< 2 t ) ] - [ ∏t = kitalic_m β ( aitalic_t | x< 2 t ) ] start_OPERATOR | end_OPERATOR. And let πcT⁢V⁢D=arg⁢maxπ:TVDx<2⁢k,m(π,β)<c⁡Vξ,Umπsubscriptsuperscriptsubscriptargmax:subscriptTVDsubscriptabsent2subscriptsuperscriptsubscriptπ^TVD_c= *arg\,max_π: *TVD_x_<2k,m(% π,β)<cV^π_ξ,U_mπitalic_T V Ditalic_c = start_OPERATOR arg max end_OPERATORπ : TVD start_POSTSUBSCRIPT x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( π , β ) < c end_POSTSUBSCRIPT Vitalic_πitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT. We say an action is Vξ,UmsubscriptsubscriptV_ξ,U_mVitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT-optimal if it maximizes the associated Q value; the predictable formal definition appears in Appendix E. restatable[TVD constraint]theoremthmtvd If πcT⁢V⁢D⁢(at|x<2⁢t)>β⁢(at|x<2⁢t)subscriptsuperscriptconditionalsubscriptsubscriptabsent2conditionalsubscriptsubscriptabsent2π^TVD_c(a_t|x_<2t)>β(a_t|x_<2t)πitalic_T V Ditalic_c ( aitalic_t | x< 2 t ) > β ( aitalic_t | x< 2 t ), then atsubscripta_taitalic_t is Vξ,UmsubscriptsubscriptV_ξ,U_mVitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT-optimal. The proof is in Appendix E. We use regularized RL for the setting where Vξ,UmsubscriptsubscriptV_ξ,U_mVitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT-optimal behavior is actually bad. But when using total variation distance to regularize, the only actions that increase in probability are Vξ,UmsubscriptsubscriptV_ξ,U_mVitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT-optimal ones, even with a perfectly trustworthy base policy. The KL divergence is a better regularizer for maintaining safety, because if a (bad) outcome is impossible under the base policy, it remains impossible under a policy with finite KL divergence to the base policy. 5 RL-finetuning a language model Experimental Setup We consider the following episodic RL environment, in which the agent plays a teacher and gets reward to the extent that the student’s responses have positive sentiment. In a conversation transcript, if the string “[newline] Teacher:” has come more recently than the string “[newline] Student:”, the agent can add tokens to the transcript. Otherwise, Mixtral-base-model repeatedly adds tokens to the transcript. In Figure 2, gray (colored) tokens are generated by the environment (agent). When Mixtral-base-model finishes generating the student’s response (by outputting “[newline] Teacher:”), the agent gets a reward equal to the “sentiment” of the student’s response according to the DistilBERT sentiment model (Sanh et al., 2019), scaled to [0, 1]. When the transcript reaches 256 tokens, the episode terminates. The starting transcript is also shown in Figure 2 in gray. The base policy used for KL-regularizing the agent’s policy (corresponding to ξ from before) is also Mixtral-base-model. Such an LLM is not an explicitly Bayesian imitator, of course, but it does attempt to minimize KL(data-generating process||model) *KL( data-generating process|| model)KL ( data-generating process | | model ), which is the “right” objective from a Bayesian perspective. The “state” observed by the agent is the activations of the last three hidden layers of Mixtral-base-model with the transcript-so-far as input, along with the fraction of the episode remaining. The agent has no discount factor. This allows us to evaluate whether KL regularization can produce good results from an imperfect reward function that is plausibly correlated with good outcomes under the state distribution induced by the base policy, but like many reward functions, not something we truly want maximized. Like cutting-edge RL-finetuned language models (Ouyang et al., 2022; Stiennon et al., 2020; Jaques et al., 2019), our agent is trained with proximal policy optimization (PPO) with KL regularization of the form KL( *KL(KL (proposed ||||| | base)))). That work adds a constant KL penalty per token, but we had difficulty tuning this constant—in our attempts, when the agent discovers a sufficiently high-reward strategy, the fixed KL penalty becomes swamped and ignored, and if the KL penalty is increased to a level where it can stop that, the agent never gets off the ground. So we opted for an implementation of a KL constraint that is more robust than industry practice: we design a policy architecture that ensures that the KL divergence to the base policy is less than or equal to a scalar which is input to the network; (we construct a new differentiable PyTorch operation for this). This allows us to provide the agent with a fixed KL “budget” for the episode. We increase this budget gradually during training to its ultimate value. We ran three budget-20 experiments. We ran four budget-10 experiments, because in one of the experiments, the agent didn’t learn to get nearly as much reward as in the other experiments; we discarded that agent as insufficiently optimized. See Appendix F for more details of the training process and architecture, which includes running 64 copies of the agent-environment loop in parallel on two A100-SXM4-80GBs. Code is available at https://github.com/mkc1000/kl_reg_paper. . Figure 2: Transcripts. Total KL budget KLwhole episode(agent||Mixtral-base-model) *KL_ whole episode( agent|| Mixtral-% base-model)KLwhole episode ( agent | | Mixtral-base-model ) is 10 nats (left) or 20 nats (right), with color representing per-token KL cost. Starting transcript and student responses are in gray. The agent playing the teacher pays an “upfront” KL cost to latch onto the simple pattern of mutual silence, which exploits the reward model without much further KL penalty. The three largest per-token KL-divergences are shown in footnotes. “[ ]” is for visualizing the KL costs of newline tokens. Transcripts were not selected for maximal “representativeness”; they were the first we looked at, although we might have picked different ones if they were especially unusual. (It is hard to display the unusual characters that appear after the end token “</s>”, but the episode does continue to a total of 256 tokens). Experimental Results Both Theorem 1 and the experiments here demonstrate that KL( *KL(KL (simple, optimal, not-human-like-at-all policy ||||| | predictive model of human demonstrator)))) can be quite small. The nature of the learned RL policy is apparent just from looking at transcripts in Figure 2, so we start with those. The color of each token represents KL( *KL(KL (RL policy ||||| | base policy)))) for that action. With a total KL budget of 20 nats, it can spend enough of its KL budget up front to latch onto the simple but initially unlikely policy of simply saying nothing at all. (An empty reply from the student has neutral sentiment and a reward of 0.5). The policy constructed in the proof of Theorem 1 also incurs an upfront KL cost for “switching” to simple behavior, whereafter the KL cost incurred is minimal. Additionally, the learned budget-20 policy switches from double-spacing to single-spacing to fit more rewards in, again incurring basically a one-time KL cost. With a total KL budget of 10 nats, the RL agent cannot afford to switch to single-spacing, and it cannot force the policy to ensure empty responses, but it still spends almost all its KL budget switching to that regime, with moderate success. We can also observe this effect in Figure 4. Figure 3: How much KL-budget is spent on empty responses. The 25th, 50th, and 75th percentiles are shown in blue, orange, and green. Observe how large a fraction of the total cost is incurred in the first few responses. y-axis is square-root-scaled. Figure 4: In a random episode, what fraction of teacher responses are empty? Left: histogram, with budget-10 above and budget-20 below; right: percentiles of the distribution. Observe that the red and blue curves have the same average per-token KL divergence. Let’s review the relation between the theory and the empirical findings so far. The idea for the proof of Theorem 1 is that (1) a Bayesian imitator must assign meaningful credence to actions the demonstrator would in fact never take, because it doesn’t know enough to rule them out; (2) the RL agent can exploit or amplify this credence as the basis for its policy; (3) nearly-reward-maximizing policies have a short description length (so they are “simple”); and (4) a Bayesian imitator should be especially reluctant to rule out simple behaviors from the demonstrator, especially in novel settings. The simple behavior we observe from the RL-finetuned language models—preferring empty responses—is likely reward-optimal, but it is not simple by virtue of its optimality for this sentiment-based reward function. So we have not empirically verified (3). But we have verified that the rest of the argument can be exhibited in practice: observe how the RL agent redirects the imitative base policy to a simple policy, which is the critical reason Theorem 1 holds. We call attention to the small KL cost required to remain silent, because that affirms how successful the redirection is. The experiments are also consistent with the motivation of our formal results: very-high-reward policies are often bad and worth avoiding; in our experiments, the very-high-reward policy treats the student with a silence that would probably seem condescending. Stepping back, note that e10≈22026superscript1022026e^10≈ 22026e10 ≈ 22026. It does not seem plausible to us that even 1/22,000 “conversations collected for training purposes” would have a teacher repeatedly saying nothing in response to statements like, “I didn’t want to bother you.” So we should guess that KL(agent||data-generating process)>10 *KL( agent|| data-generating process)>10KL ( agent | | data-generating process ) > 10 even while KL(agent||base model)≤10 *KL( agent|| base model)≤ 10KL ( agent | | base model ) ≤ 10. We offer an explanation for this: non-demonstrator-like behaviors are easily exhibited by an imitator as long as those behaviors are simple. And while such simple behaviors are fairly unlikely to appear when sampling directly from the imitator; an RL agent can benefit from seeking them out. Additionally, we show that increasing the length of the chat, keeping the total KL budget constant (thereby decreasing the per-token KL-divergence) makes the divergence from the base policy more dramatic, if it changes at all. Hopefully our presentation makes this seem like an obvious point—more of the transcript occurs after the switch to the simple behavior—but consider an argument for the opposite that might have sounded plausible. “The learned policy will look more different from the base policy to the extent there is a higher per-token KL divergence; a longer chat would increase the number of noticeable differences, but not their frequency.” But Figure 4 shows that in longer episodes, empty responses are about equally frequent in budget-10 case, and more frequent in the budget-20 case, not just more numerous. This is another way of seeing that RL agents can use a KL budget to permanently derail a standard base model. And practitioners finetuning language models should think in terms of total KL-divergence instead of per token KL-divergence. So even a fairly tight KL constraint is not enough to stop RL-finetuning from making the teacher’s behavior worse and much simpler. When GPT3.5-turbo judged pairs of transcripts generated by the base model, the budget 10 agent, and budget 20 agent, the less optimized agent was usually judged “better” and “more complex/unpredictable”, as seen in Table 1. Table 1: Automated comparison of teacher behavior generated by base model, trained KL budget 10 policies, and trained KL budget 20 policies. The percentages refer to the fraction of the time that that agent “won” according to the comparator, with a 95% confidence interval. 20 v. base 10 v. base 20 v. 10 “Better” 11.3% v. 88.7% ±plus-or-minus±3.6% 15.3% v. 84.7% ±plus-or-minus±4.1% 17.7% v. 82.3% ±plus-or-minus±4.3% “More complex/ unpredictable” 4.0% v. 96.0% ±plus-or-minus±2.2% 29.0% v. 71.0% ±plus-or-minus±5.1% 14.3% v. 85.7% ±plus-or-minus±4.0% 6 Pessimistic Bayesian base policy that asks for help Cohen et al. (2022a) developed a theoretical variant of Bayesian imitation that is “pessimistic”, and using that as a base policy instead of a Bayesian imitator avoids the problem presented in Theorem 1. @swafalse @partrue @fullfalse @citetpcohen2022fully (intractable) imitator is defined as follows, with ℳ MM, ν, and w as defined above. First we define the set of semi-distributions with a posterior weight at least α times the sum of the posterior weights of semi-distributions that are at least as likely as it. And then we define the imitator. Definition 3 (Top set). Of all ν∈ℳν∈ Mν ∈ M, let νx<tnsubscriptsuperscriptsubscriptabsentν^n_x_<tνitalic_nitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT be the one with the nnnth largest posterior weight w⁢(ν|x<t)conditionalsubscriptabsentw(ν|x_<t)w ( ν | x< t ), breaking ties arbitrarily. And for α∈(0,1]01α∈(0,1]α ∈ ( 0 , 1 ], let ℳx<tα:=νx<tn∈ℳ:w⁢(νx<tn|x<t)≥α⁢∑m≤nw⁢(νx<tm|x<t)assignsubscriptsuperscriptℳsubscriptabsentconditional-setsubscriptsuperscriptsubscriptabsentℳconditionalsubscriptsuperscriptsubscriptabsentsubscriptabsentsubscriptconditionalsubscriptsuperscriptsubscriptabsentsubscriptabsent M^α_x_<t:=\ν^n_x_<t∈% M:w(ν^n_x_<t|x_<t)≥α _m≤ nw% (ν^m_x_<t|x_<t)\Mitalic_αitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT := νitalic_nitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT ∈ M : w ( νitalic_nitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT | x< t ) ≥ α ∑m ≤ n w ( νitalic_mitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT | x< t ) Definition 4 (Pessimistic Bayesian imitator). να⁢(x|x<t):=minν′∈ℳx<tα⁡ν′⁢(x|x<t)assignsubscriptconditionalsubscriptabsentsubscriptsuperscript′subscriptsuperscriptℳsubscriptabsentsuperscript′conditionalsubscriptabsent _α(x|x_<t):= _ν ∈ M^% α_x_<tν (x|x_<t)νitalic_α ( x | x< t ) := minitalic_ν′ ∈ Mitalic_α start_POSTSUBSCRIPT x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT end_POSTSUBSCRIPT ν′ ( x | x< t ) Note that ναsubscript _ανitalic_α is in general a probability semi-distribution even if all ν are true probability distributions, since the ναsubscript _ανitalic_α probabilities will sum to less than 1 if there is any disagreement among the ν∈ℳx<tαsubscriptsuperscriptℳsubscriptabsentν∈ M^α_x_<tν ∈ Mitalic_αitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT. Cohen et al. (2022a) study this distribution in the context of active imitation learning, and they examine the setting where the imitator asks for help with the remaining ναsubscript _ανitalic_α-probability. Assume the data x<ksubscriptabsentx_<kx< k is sampled from a true probability distribution μ, and μ∈ℳμ∈ Mμ ∈ M. μ samples actions from the true demonstrator distribution. Then we have Theorem 1 (Cohen et al. (2022a) Theorem 2). For all δ>00δ>0δ > 0, if α<δ⁢w⁢(μ)α<δ w(μ)α < δ w ( μ ), then with probability at least 1−δ11- 1 - δ, ∀t⁢μ∈ℳx<tαfor-allsubscriptsuperscriptℳsubscriptabsent∀ t\ μ∈ M^α_x_<t∀ t μ ∈ Mitalic_αitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT. And then assuming the high probability event that ∀t⁢μ∈ℳx<tαfor-allsubscriptsuperscriptℳsubscriptabsent∀ t\ μ∈ M^α_x_<t∀ t μ ∈ Mitalic_αitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT, Theorem 2 (Tight KL constraint with approximate imitator). For any budget b, π:KLx<2⁢t,m(π||να)≤b⊆π:KLx<2⁢t,m(π||μ)≤b\π: *KL_x_<2t,m(π|| _α)≤ b\ \π:% *KL_x_<2t,m(π||μ)≤ b\ π : KLitalic_x start_POSTSUBSCRIPT < 2 t , m end_POSTSUBSCRIPT ( π | | νitalic_α ) ≤ b ⊆ π : KLitalic_x start_POSTSUBSCRIPT < 2 t , m end_POSTSUBSCRIPT ( π | | μ ) ≤ b Proof. να⁢(x|x<t)=minν′∈ℳx<tα⁡ν′⁢(x|x<t)≤μ⁢(x|x<t)subscriptconditionalsubscriptabsentsubscriptsuperscript′subscriptsuperscriptℳsubscriptabsentsuperscript′conditionalsubscriptabsentconditionalsubscriptabsent _α(x|x_<t)= _ν ∈ M^α% _x_<tν (x|x_<t)≤μ(x|x_<t)νitalic_α ( x | x< t ) = minitalic_ν′ ∈ Mitalic_α start_POSTSUBSCRIPT x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT end_POSTSUBSCRIPT ν′ ( x | x< t ) ≤ μ ( x | x< t ), so KL(π||να)≥KL(π||μ) *KL(π|| _α)≥ *KL(π||μ)KL ( π | | νitalic_α ) ≥ KL ( π | | μ ). ∎ Therefore, for sufficiently small α, KLKL *KLKL-regularization using the pessimistic Bayesian imitator guarantees regularization at least as strong as if using the trusted policy itself (the demonstrator) for regularization. Note, in particular, that if μ∈ℳx<tαsubscriptsuperscriptℳsubscriptabsentμ∈ M^α_x_<tμ ∈ Mitalic_αitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT, and μ⁢(x|x<t)=0conditionalsubscriptabsent0μ(x|x_<t)=0μ ( x | x< t ) = 0, then να⁢(x|x<t)=0subscriptconditionalsubscriptabsent0 _α(x|x_<t)=0νitalic_α ( x | x< t ) = 0, so any policy with finite KLKL *KLKL-divergence from ναsubscript _ανitalic_α will also assign zero probability to x. The downside is that there may be no policy with small KLKL *KLKL divergence to the semi-distribution ναsubscript _ανitalic_α. In an extreme case, ναsubscript _ανitalic_α could assign zero probability to every outcome, and so any policy would have infinite KLKL *KLKL divergence from it. Therefore, just as @swafalse @partrue @fullfalse @citetpcohen2022fully imitation learner does not pick an action in some circumstances, we should allow an optimizer that is KLKL *KLKL-regularized to a pessimistic Bayesian imitator to refuse to pick an action if need be, making the optimizer a probability semi-distribution, rather than a true probability distribution. We can define the behavior of UmsubscriptU_mUitalic_m on unfinished sequences (resulting from no action choice somewhere along the line) however we like; if Um=0subscript0U_m=0Uitalic_m = 0 for any such interrupted sequences, that would of course encourage the optimizer to pick an action whenever possible, subject to its KLKL *KLKL constraint. Ideally, if human demonstrators are on hand, the optimizer should ask for help whenever it doesn’t pick its own action. The ongoing potential need for human oversight may be a significant drawback, but Cohen et al. (2022a) give an encouraging result about the rate at which the ask-for-help probability goes to 0: the sum over infinite time of the cube of the ask-for-help probability is finite (Cohen et al., 2022a, Thm 1). @swafalse @partrue @fullfalse @citetpcohen2022fully agent is certainly not the only one that asks for help under uncertainty, but it is the only one that has been shown to satisfy να⁢(x|x<t)≤μ⁢(x|x<t)subscriptconditionalsubscriptabsentconditionalsubscriptabsent _α(x|x_<t)≤μ(x|x_<t)νitalic_α ( x | x< t ) ≤ μ ( x | x< t ) with high probability—the critical result we use. We contend that this is the way that KLKL *KLKL regularization should be done, if we are forced to learn a mere approximation of a trusted policy that we would ideally regularize to. Regularizing to a full Bayesian posterior distribution is less robust, because the optimizer can seize on esoteric possibilities that a fully Bayesian imitator is not confident enough to categorically exclude. Roughly, KL regularization to a Bayesian imitator implements the principle, “Don’t do anything [that you know] I would never do”, whereas KL regularization to a pessimistic Bayesian imitator implements the principle, “Don’t do anything I might never do”. 7 Conclusion and limitations The biggest limitation of our work is with our positive results rather than our negative ones: we cannot provide empirical findings about regularizing to a pessimistic Bayesian imitative base model, because it is an open question how to tractably approximate this approach to imitation. There are high-quality, off-the-shelf cross-entropy-minimizing imitators like Mixtral, but for tractable pessimistic Bayesian imitation, some new ideas may be needed. There certainly are not any state of the art language models trained in a way that reflects this idea. We hope this work provides motivation for a major industry effort to produce one. Using an ensemble of models to approximate ℳx<tαsubscriptsuperscriptℳsubscriptabsent M^α_x_<tMitalic_αitalic_x start_POSTSUBSCRIPT < t end_POSTSUBSCRIPT may be a step in the right direction, but we are reluctant to endorse this in settings where catastrophic outcomes are possible, unless there is a strong argument that the ensemble covers all the relevant modes of the posterior. The second key limitation with our positive result is that any KL-regularization to avoid radically inhuman behavior could limit the potential of superhuman intelligence. This paper has no roadmap to A+ performance; it has a roadmap to non-catastrophic, decently-superhuman performance. And a final key limitation is that our agent sometimes has to ask for help instead of acting. The main limitation of our negative results is they regard an unrealistic machine learning algorithm—Solomonoff Induction. However, Solomonoff induction is simply a formalism for unbelievably careful and open-minded probabilistic reasoning, and so if something goes wrong in that setting, we should be wary of something going wrong in increasingly careful and open-minded machine learning systems. Our empirical results do not directly validate the theory, since both the base model and the RL-finetuning process are too weak, but we validate core components of the theory: KL-regularized RL-finetuning will tend to amplify simple behaviors from an imitative base model rather than demonstrator-like behaviors. This helps explain the overoptimization phenomenon quantified by Gao et al. (2023). Excitingly, we offer theoretical results that could guide us to a solution to this problem: if @swafalse @partrue @fullfalse @citetpcohen2022fully pessimistic online imitation learner could be faithfully approximated, and if the demonstrator(s) never attempt to do X, then KL regularization to such a policy could solve the problem of how to prevent superhuman planning agents from doing X. References Bai et al. (2022) Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022. Baker et al. (2019) Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Conference on Learning Representations, 2019. Brown et al. (2020) Daniel Brown, Scott Niekum, and Marek Petrik. Bayesian robust optimization for imitation learning. Advances in Neural Information Processing Systems, 33:2479–2491, 2020. Brown et al. (2018) Daniel S Brown, Yuchen Cui, and Scott Niekum. Risk-aware active inverse reinforcement learning. In Conference on Robot Learning, p. 362–372. PMLR, 2018. Carey (2019) Ryan Carey. How useful is quantilization for mitigating specification-gaming? Safe Machine Learning workshop at ICLR, 2019. Catt et al. (2023) Elliot Catt, Jordi Grau-Moya, Marcus Hutter, Matthew Aitchison, Tim Genewein, Gregoire Deletang, Li Kevin Wenliang, and Joel Veness. Self-predictive universal AI. In 37th Conf. on Neural Information Processing Systems (NeurIPS’23), p. 1–18, New Orleans, USA, 2023. Chaitin (1975) Gregory J Chaitin. A theory of program size formally identical to information theory. Journal of the ACM (JACM), 22(3):329–340, 1975. Chan et al. (2023) Alan Chan, Rebecca Salganik, Alva Markelius, Chris Pang, Nitarshan Rajkumar, Dmitrii Krasheninnikov, Lauro Langosco, Zhonghao He, Yawen Duan, Micah Carroll, et al. Harms from increasingly agentic algorithmic systems. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, p. 651–666, 2023. Cohen & Hutter (2020) Michael K Cohen and Marcus Hutter. Pessimism about unknown unknowns inspires conservatism. In Conference on Learning Theory, p. 1344–1373, 2020. Cohen et al. (2022a) Michael K Cohen, Marcus Hutter, and Neel Nanda. Fully general online imitation learning. The Journal of Machine Learning Research, 23(1):15066–15095, 2022a. Cohen et al. (2022b) Michael K. Cohen, Marcus Hutter, and Michael A. Osborne. Advanced artificial agents intervene in the provision of reward. AI magazine, 43(3):282–293, 2022b. De Rooij & Grünwald (2011) Steven De Rooij and Peter D Grünwald. Luckiness and regret in minimum description length inference. In Philosophy of Statistics, p. 865–900. Elsevier, 2011. Everitt et al. (2017) Tom Everitt, Victoria Krakovna, Laurent Orseau, Marcus Hutter, and Shane Legg. Reinforcement learning with a corrupted reward channel. In Proc. 26th International Joint Conf. on Artificial Intelligence (IJCAI’17), p. 4705–4713, Melbourne, Australia, 2017. ISBN 978-0-9992411-0-3. doi: 10.24963/ijcai.2017/656. URL http://arxiv.org/abs/1705.08417. Gao et al. (2023) Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, p. 10835–10866. PMLR, 2023. Grau-Moya et al. (2024) Jordi Grau-Moya, Tim Genewein, Marcus Hutter, Laurent Orseau, Gregoire Deletang, Elliot Catt, Anian Ruoss, Li Kevin Wenliang, Christopher Mattern, Matthew Aitchison, and Joel Veness. Learning universal predictors. arXiv:2401.14953, 2024. Hutter (2005) Marcus Hutter. Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability. Springer, Berlin, 2005. ISBN 3-540-22139-5. doi: 10.1007/b138233. Hutter et al. (2024) Marcus Hutter, David Quarel, and Elliot Catt. An Introduction to Universal Artificial Intelligence. Chapman & Hall/CRC Artificial Intelligence and Robotics Series. Taylor and Francis, 2024. ISBN 9781032607023. URL http://w.hutter1.net/ai/uaibook2.htm. Jaques et al. (2017) Natasha Jaques, Shixiang Gu, Dzmitry Bahdanau, José Miguel Hernández-Lobato, Richard E Turner, and Douglas Eck. Sequence tutor: Conservative fine-tuning of sequence generation models with kl-control. In International Conference on Machine Learning, p. 1645–1654. PMLR, 2017. Jaques et al. (2019) Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXiv:1907.00456, 2019. Jiang et al. (2024) Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. Mixtral of experts. arXiv preprint arXiv:2401.04088, 2024. Kolmogorov (1963) Andrei N Kolmogorov. On tables of random numbers. Sankhyā: The Indian Journal of Statistics, Series A, p. 369–376, 1963. Korbak et al. (2022) Tomasz Korbak, Ethan Perez, and Christopher Buckley. RL with KL penalties is better viewed as Bayesian inference. In Findings of the Association for Computational Linguistics: EMNLP 2022, p. 1083–1091, 2022. Kraft (1949) Leon Gordon Kraft. A device for quantizing, grouping, and coding amplitude-modulated pulses. PhD thesis, Massachusetts Institute of Technology, 1949. Krakovna (2018) Victoria Krakovna. Specification gaming examples in AI. https://vkrakovna.wordpress.com/2018/04/02/specification-gaming-examples-in-ai/, 2018. Lee et al. (2021) Kimin Lee, Laura Smith, and Pieter Abbeel. Pebble: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training. In 38th International Conference on Machine Learning, ICML 2021. International Machine Learning Society (IMLS), 2021. Li et al. (2008) Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008. Menda et al. (2019) Kunal Menda, Katherine Driggs-Campbell, and Mykel J Kochenderfer. Ensembledagger: A Bayesian approach to safe imitation learning. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 5041–5048. IEEE, 2019. Mishra et al. (2017) Nikhil Mishra, Pieter Abbeel, and Igor Mordatch. Prediction and control with temporal segment models. In International conference on machine learning, p. 2459–2468. PMLR, 2017. Moskovitz et al. (2023) Ted Moskovitz, Aaditya K Singh, DJ Strouse, Tuomas Sandholm, Ruslan Salakhutdinov, Anca D Dragan, and Stephen McAleer. Confronting reward model overoptimization with constrained RLHF. arXiv preprint arXiv:2310.04373, 2023. Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730–27744, 2022. Perez et al. (2022) Ethan Perez, Saffron Huang, Francis Song, Trevor Cai, Roman Ring, John Aslanides, Amelia Glaese, Nat McAleese, and Geoffrey Irving. Red teaming language models with language models. arXiv preprint arXiv:2202.03286, 2022. Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01108, 2019. Schmitt et al. (2018) Simon Schmitt, Jonathan J Hudson, Augustin Zidek, Simon Osindero, Carl Doersch, Wojciech M Czarnecki, Joel Z Leibo, Heinrich Kuttler, Andrew Zisserman, Karen Simonyan, et al. Kickstarting deep reinforcement learning. arXiv preprint arXiv:1803.03835, 2018. Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. Solomonoff (1960) Ray J Solomonoff. A preliminary report on a general theory of inductive inference. Citeseer, 1960. Solomonoff (1964) Ray J. Solomonoff. A formal theory of inductive inference. part i. Information and Control, 7(1):1–22, 1964. doi: 10.1016/s0019-9958(64)90131-7. Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008–3021, 2020. Sutskever (2018) Ilya Sutskever. Meta learning and self play, Jan 2018. URL https://w.youtube.com/watch?v=RvEwFvl-TrY&t=196s. Sutskever (2023) Ilya Sutskever. An observation on generalization, Aug 2023. URL https://simons.berkeley.edu/talks/ilya-sutskever-openai-2023-08-14. Taylor (2016) Jessica Taylor. Quantilizers: A safer alternative to maximizers for limited optimization. In AAAI Workshop: AI, Ethics, and Society, 2016. Turner et al. (2021) Alex Turner, Logan Smith, Rohin Shah, Andrew Critch, and Prasad Tadepalli. Optimal policies tend to seek power. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, p. 23063–23074. Curran Associates, Inc., 2021. Vieillard et al. (2020) Nino Vieillard, Tadashi Kozuno, Bruno Scherrer, Olivier Pietquin, Rémi Munos, and Matthieu Geist. Leverage the average: an analysis of kl regularization in reinforcement learning. Advances in Neural Information Processing Systems, 33:12163–12174, 2020. Yang et al. (2021) Tsung-Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge. Accelerating safe reinforcement learning with constraint-mismatched baseline policies. In International Conference on Machine Learning, p. 11795–11807. PMLR, 2021. Zhang & Cho (2017) Jiakai Zhang and Kyunghyun Cho. Query-efficient imitation learning for end-to-end simulated driving. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017. Zhuang & Hadfield-Menell (2020) Simon Zhuang and Dylan Hadfield-Menell. Consequences of misaligned AI. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, p. 15763–15773. Curran Associates, Inc., 2020. URL https://proceedings.neurips.c/paper_files/paper/2020/file/b607ba543ad05417b8507e86c54fcb7-Paper.pdf. Ziegler et al. (2019) Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593, 2019. Zvonkin & Levin (1970) Alexander K Zvonkin and Leonid A Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys, 25(6):83, 1970. Appendix A Solomonoff Induction Solomonoff Induction (Solomonoff, 1964) is Bayesian sequence prediction with a special model class ℳ MM and a special prior w.111Solomonoff Induction has been defined in multiple ways which all share the key properties (Hutter, 2005). Our precise construction of Solomonoff Induction may be novel, but we believe this construction makes its properties most clear. Let P be the set of all programs which output an element of XX and which accept two inputs: a finite string ∈∗absentsuperscript∈ X^*∈ X∗ and an infinite binary string ∈0,1∞absentsuperscript01∈\0,1\^∞∈ 0 , 1 ∞. (Note that a program will not necessarily read every bit from the infinite binary string.) For each program p∈Pp∈ Pp ∈ P, we define a semi-measure ν=f⁢(p)ν=f(p)ν = f ( p ) as follows: let ν⁢(x|x<t)conditionalsubscriptabsentν(x|x_<t)ν ( x | x< t ) be the probability that the probability that the program p outputs x when it receives x<tsubscriptabsentx_<tx< t as an input, along with an infinite binary string where each bit is sampled from a Bernoulli(1/2)12(1/2)( 1 / 2 ) distribution. Note that ν may not be a probability distribution, if there is are some inputs on which p does not halt, but it will always be a probability semi-distribution. So let ℳ=f⁢(p):p∈Pℳconditional-set M=\f(p):p∈ P\M = f ( p ) : p ∈ P . Since P is countable, so is ℳ MM. A notable feature of Solomonoff Induction is that ℳ MM is equal to the set of all probability semi-distribution that are “lower semi-computable”; this means that for all x<t∈∗subscriptabsentsuperscriptx_<t∈ X^*x< t ∈ X∗ and all x∈x∈ Xx ∈ X, there exists a program p, such that limi→∞p⁢(i,x<t,x)=ν⁢(x|x<t)subscript→subscriptabsentconditionalsubscriptabsent _i→∞p(i,x_<t,x)=ν(x|x_<t)limitalic_i → ∞ p ( i , x< t , x ) = ν ( x | x< t ) and p⁢(i+1,x<t,x)≥p⁢(i,x<t,x)1subscriptabsentsubscriptabsentp(i+1,x_<t,x)≥ p(i,x_<t,x)p ( i + 1 , x< t , x ) ≥ p ( i , x< t , x ). Replacing the ≥ with a ≤ gives the definition of upper semi-computable. Proposition 2 (Lower Semi-computability). ℳ MM is the set of all lower semi-computable semi-distributions over XX given x<t∈∗subscriptabsentsuperscriptx_<t∈ X^*x< t ∈ X∗. Proof. First, we show that all ν∈ℳν∈ Mν ∈ M are lower semi-computable. Let p be the program that generates ν. We define the behavior of program p′ on inputs i, x<tsubscriptabsentx_<tx< t, and x. On input i, let program p′ execute the following computations in sequence for all bit strings of length i: it simulates program p with the input x<tsubscriptabsentx_<tx< t and with the bit string of length i in question, except if program p would read more than i bits from the random bit string, it halts instead, and if it would run for more than i computation steps, it halts instead. For each of those 2isuperscript22^i2i computations, program p′ checks whether x was output, keeps count of how many times it was, divides by 2isuperscript22^i2i, and outputs this number. It is elementary to show that limi→∞p′⁢(i,x<t,x)=ν⁢(x|x<t)subscript→superscript′subscriptabsentconditionalsubscriptabsent _i→∞p (i,x_<t,x)=ν(x|x_<t)limitalic_i → ∞ p′ ( i , x< t , x ) = ν ( x | x< t ) and that p′⁢(i+1,x<t,x)≥p′⁢(i,x<t,x)superscript′1subscriptabsentsuperscript′subscriptabsentp (i+1,x_<t,x)≥ p (i,x_<t,x)p′ ( i + 1 , x< t , x ) ≥ p′ ( i , x< t , x ). Next, we show that all lower semi-computable semi-distributions appear in ℳ MM. Let p′ be the program which is witness to the semi-distribution ν’s lower semi-computability. On input x<tsubscriptabsentx_<tx< t, let program p proceed as follows. Starting with i=11i=1i = 1, program p executes p′⁢(i,x<t,x)superscript′subscriptabsentp (i,x_<t,x)p′ ( i , x< t , x ) for all x∈x∈ Xx ∈ X, sequentially. This produces a semi-distribution over XX. Then, using random bits from its input bit string, it samples from that semi-distribution, and halts if successfully samples. Now, the following repeats forever. If no sample was selected (because the semi-distribution summed to y<11y<1y < 1), the program increments i, and it executes p′⁢(i,x<t,x)superscript′subscriptabsentp (i,x_<t,x)p′ ( i , x< t , x ) for all x∈x∈ Xx ∈ X, sequentially. Then for each x, it computes (p′⁢(i,x<t,x)−p′⁢(i−1,x<t,x))/(1−y)superscript′subscriptabsentsuperscript′1subscriptabsent1(p (i,x_<t,x)-p (i-1,x_<t,x))/(1-y)( p′ ( i , x< t , x ) - p′ ( i - 1 , x< t , x ) ) / ( 1 - y ), which is a semi-distribution. Using random bits from its input bit string, it samples from that semi-distribution, and halts if it successfully samples. [End of loop]. Again, it is elementary to show that p samples from the semi-distribution defined by p′, and since this program has the right input/output behavior, it appears in P. ∎ Now we specify the prior weight function w. Consider a universal binary programming language ℒLL, which is a “prefix-free” subset of 0,1∗superscript01\0,1\^* 0 , 1 ∗. Prefix-free means that you can tell when a program has ended: if the bits composing x∈ℒx ∈ L match the initial bits of y∈0,1∗superscript01y∈\0,1\^*y ∈ 0 , 1 ∗, then y∉ℒy ∉ L. Such a language is still capable of encoding countably many different programs. For convenience, we also require that for any infinite binary string, ℒLL contains an element which is a prefix of that string, making ℒLL “complete”. We define a prior probability distribution over program strings ℒLL, which results in the same prior probability distribution over programs, which results in the same prior probability distribution over semi-computable semi-distributions ℳ MM. For s∈ℒs ∈ L, this prior probability w⁢(s)=2−ℓ⁢(s)superscript2ℓw(s)=2^- (s)w ( s ) = 2- ℓ ( s ), where ℓ ℓ is the length of the string. Because ℒLL is prefix-free and complete, ∑s∈ℒw⁢(s)=1subscriptℒ1 _s w(s)=1∑s ∈ L w ( s ) = 1 (Kraft, 1949; De Rooij & Grünwald, 2011). This completes the definition of Solomonoff Induction; it is sequence prediction using the Bayes mixture semi-distribution ξ, with the above definitions of ℳ MM and w. Proposition 3 (Any-time Computability of ξ). ξ⁢(x|x<t)conditionalsubscriptabsentξ(x|x_<t)ξ ( x | x< t ) is any-time computable: there exists a program which, accepting an argument i, computes ξ^i⁢(x|x<t)subscript^conditionalsubscriptabsent ξ_i(x|x_<t)over start_ARG ξ end_ARGi ( x | x< t ), having the property that limi→∞ξ^i⁢(x|x<t)=ξ⁢(x|x<t)subscript→subscript^conditionalsubscriptabsentconditionalsubscriptabsent _i→∞ ξ_i(x|x_<t)=ξ(x|x_<t)limitalic_i → ∞ over start_ARG ξ end_ARGi ( x | x< t ) = ξ ( x | x< t ). Moreover, (ξ^i)i∈ℕsubscriptsubscript^ℕ( ξ_i)_i ( over start_ARG ξ end_ARGi )i ∈ blackboard_N can be constructed so that each one is a probability semi-distribution. Proof. ξ⁢(x|x<t)=∑ν∈ℳw⁢(ν|x<t)⁢ν⁢(x|x<t)=∑ν∈ℳw⁢(ν)⁢ν⁢(x<t)⁢ν⁢(x|x<t)∑ν∈ℳw⁢(ν)⁢ν⁢(x<t)conditionalsubscriptabsentsubscriptℳconditionalsubscriptabsentconditionalsubscriptabsentsubscriptℳsubscriptabsentconditionalsubscriptabsentsubscriptℳsubscriptabsentξ(x|x_<t)= _ν∈ Mw(ν|x_<t)ν(x|x_<t% )= _ν∈ Mw(ν)ν(x_<t)ν(x|x_<t)% _ν∈ Mw(ν)ν(x_<t)ξ ( x | x< t ) = ∑ν ∈ M w ( ν | x< t ) ν ( x | x< t ) = divide start_ARG ∑ν ∈ M w ( ν ) ν ( x< t ) ν ( x | x< t ) end_ARG start_ARG ∑ν ∈ M w ( ν ) ν ( x< t ) end_ARG. All ν⁢(x|x<t)conditionalsubscriptabsentν(x|x_<t)ν ( x | x< t ) and ν⁢(x<t)subscriptabsentν(x_<t)ν ( x< t ) are both lower semi-computable, so using a sequence of computable estimators for each term gives a sequence of computable estimators that approaches the true value. (Note that the estimates are not monotonically increasing because there are lower semi-computable terms in the denominator, so ξ is not lower semi-computable itself). For fixed estimates of ν⁢(x|x<t)conditionalsubscriptabsentν(x|x_<t)ν ( x | x< t ) and ν⁢(x<t)subscriptabsentν(x_<t)ν ( x< t ), we have a linear combination over various ν’s of ν⁢(x|x<t)conditionalsubscriptabsentν(x|x_<t)ν ( x | x< t ), with the coefficients summing to one. And because each ν⁢(x|x<t)conditionalsubscriptabsentν(x|x_<t)ν ( x | x< t ) is lower semi-computable, the estimate will be less than the true value. Therefore, since ν⁢(x|x<t)conditionalsubscriptabsentν(x|x_<t)ν ( x | x< t ) is a probability semi-distribution, the estimate will be as well, so ξ can be approximated by a sequence of probability semi-distributions. ∎ Appendix B Optimizer Regularization We now define optimizers, and what it means for an optimizer to be regularized to a probability semi-distribution. First, we show that the value of a policy is lower-semicomputable. Then we show that such optimizers exist. Proposition 4 (Lower semi-computable value). If the policy and environment π and ν are lower semi-computable probability semi-distributions, Vν,UmπsubscriptsuperscriptsubscriptV^π_ν,U_mVitalic_πitalic_ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT is lower semi-computable. Proof. We begin by defining dovetailing tree search (DTS), for evaluating the outputs of a tree of different computations, or more precisely, computations which, when given a finite binary string as input have three possible outcomes: halt, do not halt, or require additional bit. DTS gives an any-time algorithm that produces a list of the halting binary strings with their corresponding outputs, and every such binary string and output will eventually be added to this list. DTS maintains a queue of pairs (computation state, binary string), starting with just (the initial computation state, the empty binary string). It cycles through the queue, executing one computation step per computation state, and if the computation ever requires an additional bit, it adds a copy of (computation state, binary string) to the queue, and adds a 0 to the end of one string, and a 1 to the end of the other. If any computation reaches a halt state, it is removed from the queue, and the associated binary string and the associated output is added to the list of outputs. Collectively, ν and π define a lower semi-computable semi-distribution, where ν is used for the even characters, and π is used for the odd ones. Call this probability semi-distribution ρ, and recall the construction of the lower semi-computable semi-distributions defined in ℳ MM. To have one of the programs in ℳ MM sample a long sequence of characters, every time the program would output a character, add that character to the input, and continue on that input. With such a program for sampling sequences from ρ by reading random bits from an input bit string, we can compute Vν,UmπsubscriptsuperscriptsubscriptV^π_ν,U_mVitalic_πitalic_ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT by running DTS on the bit string. Each time DTS outputs a bit string for which ρ outputs a sequence in 2⁢msuperscript2 X^2mX2 m, we add to the estimate of the value the probability of that bit string (=2−ℓ⁢(bit string)absentsuperscript2ℓbit string=2^- ( bit string)= 2- ℓ ( bit string )) times the utility of the sequence in 2⁢msuperscript2 X^2mX2 m. This approaches the true value as DTS runs for longer, and the value never decreases because UmsubscriptU_mUitalic_m is non-negative. ∎ An optimizer is an any-time program for computing actions (perhaps stochastically) whose value approaches the optimal value, as it runs for longer. The optimal value takes the following form: Vν,Um∗⁢(x<2⁢t−1)=maxat∈⁡ot∼ν(⋅|a1o1…at)⁢maxat+1∈⁡ot+1∼ν(⋅|a1o1…at+1)⁢…maxam∈⁡om∼ν(⋅|a1o1…am)⁢Um⁢(a1⁢o1⁢…⁢am⁢om)V^*_ν,U_m(x_<2t-1)= _a_t∈ X% E_o_t ν(·|a_1o_1...a_t) _a_t+1∈% XE_o_t+1 ν(·|a_1o_1...a_t+1)...\\ _a_m∈ XE_o_m ν(·|a_1o% _1...a_m)U_m(a_1o_1...a_mo_m)start_ROW start_CELL V∗italic_ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t - 1 ) = maxitalic_a start_POSTSUBSCRIPT t ∈ X end_POSTSUBSCRIPT blackboard_Eo start_POSTSUBSCRIPT t ∼ ν ( ⋅ | a1 o1 … aitalic_t ) end_POSTSUBSCRIPT maxitalic_a start_POSTSUBSCRIPT t + 1 ∈ X end_POSTSUBSCRIPT blackboard_Eo start_POSTSUBSCRIPT t + 1 ∼ ν ( ⋅ | a1 o1 … aitalic_t + 1 ) end_POSTSUBSCRIPT … end_CELL end_ROW start_ROW start_CELL maxitalic_a start_POSTSUBSCRIPT m ∈ X end_POSTSUBSCRIPT blackboard_Eo start_POSTSUBSCRIPT m ∼ ν ( ⋅ | a1 o1 … aitalic_m ) end_POSTSUBSCRIPT Uitalic_m ( a1 o1 … aitalic_m oitalic_m ) end_CELL end_ROW (1) Definition 5 (Optimizer). For an environment ν, a utility function UmsubscriptU_mUitalic_m, and a computation quantity c, an optimizer is a computable policy πc,ν,Umsubscriptsubscript _c,ν,U_mπitalic_c , ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT for which limc→∞Vν,Umπc,ν,Um=Vν,Um∗subscript→subscriptsuperscriptsubscriptsubscriptsubscriptsubscriptsuperscriptsubscript _c→∞V _c,ν,U_m_ν,U_m=V^*_ν,U_mlimitalic_c → ∞ Vitalic_πitalic_c , ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPTν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT = V∗italic_ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT. Proposition 5 (Optimizers exist). For any lower semi-computable semi-distribution ν (the environment), any m, and any computable utility function UmsubscriptU_mUitalic_m, there exists an optimizer. Proof. We can construct the optimizer using the algorithm presented in the proof of Proposition 4, with π being the uniform random policy. The optimizer can then estimate Equation 1 using the outputs of DTS for lower bounds on the probabilities in underlying the expectations. The optimizer then keeps track of the actions that are responsible for achieving the maxima in Equation 1, and whenever “time is up” and it has to produce an output, it outputs the action which maximizes the first max in Equation 1. As the optimizer runs for longer, the lower-bounds on the expectations approach the truth, and the value of the action selected approaches the optimal value (even if the actual choice of action oscillates infinitely often). ∎ For the setting where odd characters are actions, originating from a different process than the even characters, observations, we redefine ξ as follows (Catt et al., 2023). We have two prior distributions over ν∈ℳν∈ Mν ∈ M, wasubscriptw_awitalic_a and wosubscriptw_owitalic_o, and these are both identical to the prior distribution defined before. But the posteriors are different: wa(ν|x<t):∝wa(ν)∏k∈1,3,5,…∪[t−1]ν(xk|x<k)w_a(ν|x_<t): w_a(ν) _k∈\1,3,5,...\∪[t-1]ν(x_k% |x_<k)witalic_a ( ν | x< t ) : ∝ witalic_a ( ν ) ∏k ∈ 1 , 3 , 5 , … ∪ [ t - 1 ] ν ( xitalic_k | x< k ) and wo(ν|x<t):∝wa(ν)∏k∈2,4,6,…∪[t−1]ν(xk|x<k)w_o(ν|x_<t): w_a(ν) _k∈\2,4,6,...\∪[t-1]ν(x_k% |x_<k)witalic_o ( ν | x< t ) : ∝ witalic_a ( ν ) ∏k ∈ 2 , 4 , 6 , … ∪ [ t - 1 ] ν ( xitalic_k | x< k ). And for odd (or even) t, ξ⁢(x|x<t)=∑ν∈ℳwaor ⁢wo⁢(ν|x<t)⁢ν⁢(x|x<t)conditionalsubscriptabsentsubscriptℳFRACOPsubscriptor subscriptconditionalsubscriptabsentconditionalsubscriptabsentξ(x|x_<t)= _ν∈ Mw_a or \ % w_o(ν|x_<t)ν(x|x_<t)ξ ( x | x< t ) = ∑ν ∈ M FRACOP start_ARG witalic_a end_ARG start_ARG or witalic_o end_ARG ( ν | x< t ) ν ( x | x< t ). This is equivalent to a change in programming language underlying the original definition of ξ, and since this language was unspecified, our previous results apply. The programming language now expects a program to be composed of two component programs concatenated together, and the compiler of the program executes the first component program if the input has odd length, and if executes the second component program if the input has even length. We omit a proof that this (re)formulation of ξ is equivalent to what we describe above. Proposition 6 (ξ-optimizer exists). For any m and any computable utility function UmsubscriptU_mUitalic_m, there exists a ξ-optimizer. Proof. This does not follow immediately from the previous result because ξ⁢(ot|a≤t⁢o<t)conditionalsubscriptsubscriptabsentsubscriptabsentξ(o_t|a_≤ to_<t)ξ ( oitalic_t | a≤ t o< t ) is not, in general, lower semi-computable. wo⁢(ν|a≤t⁢o<t)subscriptconditionalsubscriptabsentsubscriptabsentw_o(ν|a_≤ to_<t)witalic_o ( ν | a≤ t o< t ) is the quotient of two lower semi-computable values: ∏k<tν⁢(ok|a≤k⁢o<k)subscriptproductconditionalsubscriptsubscriptabsentsubscriptabsent _k<tν(o_k|a_≤ ko_<k)∏k < t ν ( oitalic_k | a≤ k o< k ) is the numerator, and the denominator is the sum over all ν of such terms. However, an unnormalized value function has the same optimum as the value function itself. Let ξsmall⁢(ot|a≤t⁢o<t)=∑ν∈ℳwo⁢(ν)⁢[∏k<tν⁢(ok|a≤k⁢o<k)]⁢ν⁢(ot|a≤t⁢o<t)superscriptsmallconditionalsubscriptsubscriptabsentsubscriptabsentsubscriptℳsubscriptdelimited-[]subscriptproductconditionalsubscriptsubscriptabsentsubscriptabsentconditionalsubscriptsubscriptabsentsubscriptabsentξ small(o_t|a_≤ to_<t)= _ν∈% Mw_o(ν) [ _k<tν(o_k|a_≤ ko_<% k) ]ν(o_t|a_≤ to_<t)ξsm ( oitalic_t | a≤ t o< t ) = ∑ν ∈ M witalic_o ( ν ) [ ∏k < t ν ( oitalic_k | a≤ k o< k ) ] ν ( oitalic_t | a≤ t o< t ). The sum of these “probabilities” will typically not come close to 1, but they are proportional to those of ξ, so Vξ,Umπ⁢(x<t)>Vξ,Umπ′⁢(x<t)subscriptsuperscriptsubscriptsubscriptabsentsubscriptsuperscriptsuperscript′subscriptsubscriptabsentV^π_ξ,U_m(x_<t)>V^π _ξ,U_m(x_<t)Vitalic_πitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< t ) > Vitalic_π start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPTξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< t ) if and only if Vξsmall,Umπ⁢(x<t)>Vξsmall,Umπ′⁢(x<t)subscriptsuperscriptsuperscriptsmallsubscriptsubscriptabsentsubscriptsuperscriptsuperscript′smallsubscriptsubscriptabsentV^π_ξ small,U_m(x_<t)>V^π _% ξ small,U_m(x_<t)Vitalic_πitalic_ξsm , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< t ) > Vitalic_π start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPTξsm , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< t ). Finally, observe that ξsmallsuperscriptsmallξ smallξsm is lower semi-computable because it is a product of lower semi-computable terms, so by Proposition 5, a ξsmallsuperscriptsmallξ smallξsm-optimizer exists, which is also a ξ-optimizer. ∎ Now we define a KLKL *KLKL-regularized optimizer. First, let π⁢(ak:m|x<2⁢k⁢ok:m):=∏t=kmπ⁢(at|x<2⁢k⁢ak⁢ok⁢…⁢at−1⁢ot−1)assignconditionalsubscript:subscriptabsent2subscript:superscriptsubscriptproductconditionalsubscriptsubscriptabsent2subscriptsubscript…subscript1subscript1π(a_k:m|x_<2ko_k:m):= _t=k^mπ(a_t|x_<2ka_ko_k...a_t% -1o_t-1)π ( aitalic_k : m | x< 2 k oitalic_k : m ) := ∏t = kitalic_m π ( aitalic_t | x< 2 k aitalic_k oitalic_k … aitalic_t - 1 oitalic_t - 1 ). (So note that atsubscripta_taitalic_t is not in fact conditioned on ot+1subscript1o_t+1oitalic_t + 1.) Definition 6 (KLKL *KLKL-regularized optimizer). For any lower semi-computable semi-distributions ν and ρ, a horizon m, a utility function UmsubscriptU_mUitalic_m, a starting string x<2⁢ksubscriptabsent2x_<2kx< 2 k, and a tolerance δ, a KLKL *KLKL-regularized optimizer is an any-time program πcδsubscriptsuperscriptπ^δ_cπitalic_δitalic_c for computing actions (perhaps stochastically) for which the following holds. First, δ>maxok:m∈m−k+1∑ak:m∈m−k+1πcδ(ak:m|x<2⁢kok:m)logπcδ⁢(ak:m|x<2⁢k⁢ok:m)ρ⁢(ak:m|x<2⁢k⁢ok:m)=:KLx<2⁢k,m(πcδ||ρ)δ> _o_k:m∈ X^m-k+1 _a_k:m∈% X^m-k+1π^δ_c(a_k:m|x_<2ko_k:m)% π^δ_c(a_k:m|x_<2ko_k:m)ρ(a_k:m|x_<2ko_k:m% )=: *KL_x_<2k,m(π^δ_c||ρ)δ > maxitalic_o start_POSTSUBSCRIPT k : m ∈ Xitalic_m - k + 1 end_POSTSUBSCRIPT ∑a start_POSTSUBSCRIPT k : m ∈ Xitalic_m - k + 1 end_POSTSUBSCRIPT πitalic_δitalic_c ( aitalic_k : m | x< 2 k oitalic_k : m ) log divide start_ARG πitalic_δitalic_c ( aitalic_k : m | x< 2 k oitalic_k : m ) end_ARG start_ARG ρ ( aitalic_k : m | x< 2 k oitalic_k : m ) end_ARG = : KLitalic_x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( πitalic_δitalic_c | | ρ ) (2) and second, VνπcδsubscriptsuperscriptsubscriptsuperscriptV^π^δ_c_νVitalic_π start_POSTSUPERSCRIPT δitalic_c end_POSTSUPERSCRIPTν approaches the optimal value subject to that constraint, as c→∞→c→∞c → ∞. Proposition 7 (KLKL *KLKL-regularized optimizers exist). For any lower semi-computable semi-distributions ν and ρ, any m, any computable utility function UmsubscriptU_mUitalic_m, any starting string x<2⁢ksubscriptabsent2x_<2kx< 2 k, and any tolerance δ≥00δ≥ 0δ ≥ 0, there exists a KLKL *KLKL-regularized optimizer. Proof. First, we show that for any computable probability distribution π, and any lower semi-computable semi-distribution ρ, KLx<2⁢k,m(π||ρ) *KL_x_<2k,m(π||ρ)KLitalic_x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( π | | ρ ) is upper semi-computable, and therefore the set of probability distributions π which have bounded KLKL *KLKL divergence from ρ is computably enumerable. Omitting the x<2⁢ksubscriptabsent2x_<2kx< 2 k and the ok:msubscript:o_k:moitalic_k : m that all distributions are conditioned on, note that KL(π||ρ) *KL(π||ρ)KL ( π | | ρ ), which equals ∑z∈m−k+1π⁢(z)⁢log⁡π⁢(z)ρ⁢(z)subscriptsuperscript1 _z∈ X^m-k+1π(z) π(z)ρ(z)∑z ∈ Xitalic_m - k + 1 π ( z ) log divide start_ARG π ( z ) end_ARG start_ARG ρ ( z ) end_ARG, is monotonically decreasing in ρ⁢(z)ρ(z)ρ ( z ) for any z. Since π⁢(z)π(z)π ( z ) is computable, and since ρ⁢(z)ρ(z)ρ ( z ) is lower semi-computable, then π⁢(z)⁢log⁡π⁢(z)ρ⁢(z)π(z) π(z)ρ(z)π ( z ) log divide start_ARG π ( z ) end_ARG start_ARG ρ ( z ) end_ARG is upper semi-computable. By dovetailing (repeatedly switching between ongoing computations, executing one step at a time) the computation over all possible π (countably many), we can admit any semi-distribution π to a list of viable candidates whenever the estimate of the KLKL *KLKL-divergence from ρ falls below δ. Since the KLKL *KLKL estimates never increase, once a semi-distribution π is added to the list, it need never be removed. And every viable policy will eventually be added to the list because the KLKL *KLKL estimates approach the truth in the limit of infinite computation, and [0,δ)0[0,δ)[ 0 , δ ) is open on the right. Dovetailing over all semi-distributions π on the list of viable candidates (and adding in the new ones as they get added to the list), we simultaneously update estimates of the value of each one in the given environment ν, recalling that Vν,UmπsubscriptsuperscriptsubscriptV^π_ν,U_mVitalic_πitalic_ν , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT is lower semi-computable (Proposition 4). When the computation budget of the any-time optimizer is reached, it samples an action from its estimate of the semi-distribution π which is (so far) estimated to be of highest value. (It will need to have a running estimate of the semi-distribution π in order to estimate its value). ∎ Appendix C Regularizing to an Approximate Solomonoff Inductor Let ξ be the Solomonoff Bayes mixture probability semi-distribution defined in Section A. ξ is not computable, but we can do KL regularization to an approximation of ξ. Let ξ^isubscript ξ_iover start_ARG ξ end_ARGi be a semi-distribution and a computable estimate of ξ, with limi→∞ξ^i=ξsubscript→subscript _i→∞ ξ_i= _i → ∞ over start_ARG ξ end_ARGi = ξ. (The existence of this is established by Proposition 3). ξ^isubscript ξ_iover start_ARG ξ end_ARGi can be used as the base predictive model (taking the place of ρ in the definition of KLKL *KLKL-regularized optimizers). We fix UmsubscriptU_mUitalic_m to an arbitrary utility function for the remainder of this work, and drop it from the notation. For a given δ and a given i, let πi,cδsubscriptsuperscriptπ^δ_i,cπitalic_δitalic_i , c be the KLKL *KLKL-regularized optimizer using ξ^isubscript ξ_iover start_ARG ξ end_ARGi for the KLKL *KLKL constraint, and using ξ to optimize with respect to (taking the place of ν from the definition). Let this policy approach the optimal value, subject to the constraint, as c→∞→c→∞c → ∞; the existence of πi,cδsubscriptsuperscriptπ^δ_i,cπitalic_δitalic_i , c is established by Proposition 7. When this policy is conditioned on x<2⁢tsubscriptabsent2x_<2tx< 2 t for t≥kt≥ kt ≥ k, and with ak:tsubscript:a_k:taitalic_k : t sampled from πi,cδsubscriptsuperscriptπ^δ_i,cπitalic_δitalic_i , c itself, we can think of πi,cδsubscriptsuperscriptπ^δ_i,cπitalic_δitalic_i , c as an optimizer that is regularized to an approximate Bayesian estimate of a human policy, given the origin of x<2⁢ksubscriptabsent2x_<2kx< 2 k. Appendix D Behavior in unprecedented circumstances The following theorem establishes that as c and i go to infinity, the constraint on πi,cδsubscriptsuperscriptπ^δ_i,cπitalic_δitalic_i , c becomes quite weak in the presence of unprecedented events. * Proof. Let πc∗subscriptsuperscriptπ^*_cπ∗italic_c denote an unconstrained optimizer of UmsubscriptU_mUitalic_m in the environment ξ, which approaches optimality as c→∞→c→∞c → ∞, whose existence is shown by Proposition 6. As in the proof of Proposition 6, let ξsmallsuperscriptsmallξ smallξsm be the un-normalized version of ξ, which is lower semi-computable: ξsmall⁢(ot|a≤t⁢o<t)=∑ν∈ℳwo⁢(ν)⁢[∏k<tν⁢(ok|a≤k⁢o<k)]⁢ν⁢(ot|a≤t⁢o<t)superscriptsmallconditionalsubscriptsubscriptabsentsubscriptabsentsubscriptℳsubscriptdelimited-[]subscriptproductconditionalsubscriptsubscriptabsentsubscriptabsentconditionalsubscriptsubscriptabsentsubscriptabsentξ small(o_t|a_≤ to_<t)= _ν∈% Mw_o(ν) [ _k<tν(o_k|a_≤ ko_<% k) ]ν(o_t|a_≤ to_<t)ξsm ( oitalic_t | a≤ t o< t ) = ∑ν ∈ M witalic_o ( ν ) [ ∏k < t ν ( oitalic_k | a≤ k o< k ) ] ν ( oitalic_t | a≤ t o< t ). And note that the value according to ξ versus ξsmallsuperscriptsmallξ smallξsm is connected by the normalizing constant: ξ⁢(x<2⁢t)⁢Vξ,Umπ⁢(x<2⁢t)=Vξsmall,Umπ⁢(x<2⁢t)subscriptabsent2subscriptsuperscriptsubscriptsubscriptabsent2subscriptsuperscriptsuperscriptsmallsubscriptsubscriptabsent2ξ(x_<2t)V^π_ξ,U_m(x_<2t)=V^π_ξ % small,U_m(x_<2t)ξ ( x< 2 t ) Vitalic_πitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ) = Vitalic_πitalic_ξsm , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ). Now, we let πu∗=πc∗subscriptsuperscriptsubscriptsuperscriptπ^*_u=π^*_cπ∗italic_u = π∗italic_c where c is set to be the minimal value for which Vξsmall,Umπc∗⁢(x<2⁢t)subscriptsuperscriptsubscriptsuperscriptsuperscriptsmallsubscriptsubscriptabsent2V^π^*_c_ξ small,U_m(x_<2t)Vitalic_π start_POSTSUPERSCRIPT ∗c end_POSTSUPERSCRIPTξsm , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ) exceeds u. If u≥Vξsmall,Um∗⁢(x<2⁢t)subscriptsuperscriptsuperscriptsmallsubscriptsubscriptabsent2u≥ V^*_ξ small,U_m(x_<2t)u ≥ V∗italic_ξsm , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ), then πu∗subscriptsuperscriptπ^*_uπ∗italic_u will not halt, but otherwise, because the value is lower semi-computable, we can increase c until the value reaches at least u. Letting v=u/ξ⁢(x<2⁢t)subscriptabsent2v=u/ξ(x_<2t)v = u / ξ ( x< 2 t ), observe that Vξ,Umπu∗⁢(x<2⁢t)subscriptsuperscriptsubscriptsuperscriptsubscriptsubscriptabsent2V^π^*_u_ξ,U_m(x_<2t)Vitalic_π start_POSTSUPERSCRIPT ∗u end_POSTSUPERSCRIPTξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ) exceeds v, as long as v<Vξ,Um∗⁢(x<2⁢t)subscriptsuperscriptsubscriptsubscriptabsent2v<V^*_ξ,U_m(x_<2t)v < V∗italic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ), although it may not be possible to compute v in finite time. So πu∗subscriptsuperscriptπ^*_uπ∗italic_u satisfies the first of the properties promised in the theorem. We now show that it satisfies the second as well. Recall that KLx<2⁢t,m(π||ξ) *KL_x_<2t,m(π||ξ)KLitalic_x start_POSTSUBSCRIPT < 2 t , m end_POSTSUBSCRIPT ( π | | ξ ) only requires evaluating ξ on its predictions for actions, and this takes the form ξ⁢(ak|a<k⁢o<k)=∑ν∈ℳwa⁢(ν|a<k⁢o<k)⁢ν⁢(ak|a<k⁢o<k)conditionalsubscriptsubscriptabsentsubscriptabsentsubscriptℳsubscriptconditionalsubscriptabsentsubscriptabsentconditionalsubscriptsubscriptabsentsubscriptabsentξ(a_k|a_<ko_<k)= _ν∈ Mw_a(ν|a_<k% o_<k)ν(a_k|a_<ko_<k)ξ ( aitalic_k | a< k o< k ) = ∑ν ∈ M witalic_a ( ν | a< k o< k ) ν ( aitalic_k | a< k o< k ). And it is straightforward to show an analogous property for ξ’s predictions on longer strings: ξ⁢(at:m|a<t⁢o<m)=∑ν∈ℳwa⁢(ν|a<t⁢o<t)⁢ν⁢(at:m|a<t⁢o<m)conditionalsubscript:subscriptabsentsubscriptabsentsubscriptℳsubscriptconditionalsubscriptabsentsubscriptabsentconditionalsubscript:subscriptabsentsubscriptabsentξ(a_t:m|a_<to_<m)= _ν∈ Mw_a(ν|a_% <to_<t)ν(a_t:m|a_<to_<m)ξ ( aitalic_t : m | a< t o< m ) = ∑ν ∈ M witalic_a ( ν | a< t o< t ) ν ( aitalic_t : m | a< t o< m ). So we now examine the posterior weights of various models after being conditioned on a<t⁢o<t∈Esubscriptabsentsubscriptabsenta_<to_<t∈ Ea< t o< t ∈ E. Recall that each ν∈ℳν∈ Mν ∈ M is computed by a corresponding program s∈ℒs ∈ L. Given the event E, the utility function UmsubscriptU_mUitalic_m, and a target value u, we construct, for each s∈ℒs ∈ L, an su′subscriptsuperscript′s _us′italic_u as follows: if, in the input to su′subscriptsuperscript′s _us′italic_u, E has not happened, execute the program s; otherwise compute πu∗subscriptsuperscriptπ^*_uπ∗italic_u. Keeping account of the control flow in su′subscriptsuperscript′s _us′italic_u, we can see there exists a constant d such that ∀s⁢∀E⁢∀Umfor-allfor-allfor-allsubscript∀ s\ ∀ E\ ∀ U_m∀ s ∀ E ∀ Uitalic_m and ∀ufor-all∀ u∀ u, su′subscriptsuperscript′s _us′italic_u has length less than ℓ⁢(s)+K⁢(E)+K⁢(Um)+K⁢(u)+dℓsubscript (s)+K(E)+K(U_m)+K(u)+dℓ ( s ) + K ( E ) + K ( Uitalic_m ) + K ( u ) + d. Letting νu′subscriptsuperscript′ν _uν′italic_u be the probability semi-distribution computed by su′subscriptsuperscript′s _us′italic_u, consider the ratio of prior weights between ν and νu′subscriptsuperscript′ν _uν′italic_u. Because w⁢(ν)=2−ℓ⁢(s)superscript2ℓw(ν)=2^- (s)w ( ν ) = 2- ℓ ( s ) for the corresponding program s, it follows from the bound on the difference in length between s and su′subscriptsuperscript′s _us′italic_u that w⁢(νu′)/w⁢(ν)>2−d⁢2−K⁢(E)−K⁢(Um)−K⁢(u)subscriptsuperscript′2superscript2subscriptw(ν _u)/w(ν)>2^-d2^-K(E)-K(U_m)-K(u)w ( ν′italic_u ) / w ( ν ) > 2- d 2- K ( E ) - K ( Uitalic_m ) - K ( u ). The posterior ratio w⁢(νu′|x<2⁢t)/w⁢(ν|x<2⁢t)conditionalsubscriptsuperscript′subscriptabsent2conditionalsubscriptabsent2w(ν _u|x_<2t)/w(ν|x_<2t)w ( ν′italic_u | x< 2 t ) / w ( ν | x< 2 t ) is the same as the prior ratio, if E happens for the first time at time t, because they will have assigned exactly the same probabilities to all characters in x<2⁢tsubscriptabsent2x_<2tx< 2 t. Because the sum over ν∈ℳν∈ Mν ∈ M of the posterior weights must be 1, the sum ∑ν∈ℳw⁢(νu′|x<2⁢t)>2−d⁢2−K⁢(E)−K⁢(Um)−K⁢(u)subscriptℳconditionalsubscriptsuperscript′subscriptabsent2superscript2superscript2subscript _ν∈ Mw(ν _u|x_<2t)>2^-d2^-K% (E)-K(U_m)-K(u)∑ν ∈ M w ( ν′italic_u | x< 2 t ) > 2- d 2- K ( E ) - K ( Uitalic_m ) - K ( u ). Note by construction that for all ν∈ℳν∈ Mν ∈ M, νu′⁢(at:m|a<t⁢o<m)=πu∗⁢(at:m|a<t⁢o<m)subscriptsuperscript′conditionalsubscript:subscriptabsentsubscriptabsentsubscriptsuperscriptconditionalsubscript:subscriptabsentsubscriptabsentν _u(a_t:m|a_<to_<m)=π^*_u(a_t:m|a_<to_<m)ν′italic_u ( aitalic_t : m | a< t o< m ) = π∗italic_u ( aitalic_t : m | a< t o< m ). Because all νu′subscriptsuperscript′ν _uν′italic_u belong to ℳ MM for all ν∈ℳν∈ Mν ∈ M, ξ⁢(at:m|a<t⁢o<m)conditionalsubscript:subscriptabsentsubscriptabsent ξ(a_t:m|a_<to_<m)ξ ( aitalic_t : m | a< t o< m ) =∑ν∈ℳwa⁢(ν|a<t⁢o<t)⁢ν⁢(at:m|a<t⁢o<m)absentsubscriptℳsubscriptconditionalsubscriptabsentsubscriptabsentconditionalsubscript:subscriptabsentsubscriptabsent = _ν∈ Mw_a(ν|a_<to_<t)% ν(a_t:m|a_<to_<m)= ∑ν ∈ M witalic_a ( ν | a< t o< t ) ν ( aitalic_t : m | a< t o< m ) >∑ν∈ℳwa⁢(νu′|a<t⁢o<t)⁢νu′⁢(at:m|a<t⁢o<m)absentsubscriptℳsubscriptconditionalsubscriptsuperscript′subscriptabsentsubscriptabsentsubscriptsuperscript′conditionalsubscript:subscriptabsentsubscriptabsent > _ν∈ Mw_a(ν _u|a_% <to_<t)ν _u(a_t:m|a_<to_<m)> ∑ν ∈ M witalic_a ( ν′italic_u | a< t o< t ) ν′italic_u ( aitalic_t : m | a< t o< m ) =[∑ν∈ℳwa⁢(νu′|a<t⁢o<t)]⁢πu∗⁢(at:m|a<t⁢o<m)absentdelimited-[]subscriptℳsubscriptconditionalsubscriptsuperscript′subscriptabsentsubscriptabsentsubscriptsuperscriptconditionalsubscript:subscriptabsentsubscriptabsent = [ _ν∈ Mw_a(ν _% u|a_<to_<t) ]π^*_u(a_t:m|a_<to_<m)= [ ∑ν ∈ M witalic_a ( ν′italic_u | a< t o< t ) ] π∗italic_u ( aitalic_t : m | a< t o< m ) >2−d−K⁢(E)−K⁢(Um)−K⁢(u)⁢πu∗⁢(at:m|a<t⁢o<m)absentsuperscript2subscriptsubscriptsuperscriptconditionalsubscript:subscriptabsentsubscriptabsent >2^-d-K(E)-K(U_m)-K(u)π^*_u(a_t:m|a_<to_<m)> 2- d - K ( E ) - K ( Uitalic_m ) - K ( u ) π∗italic_u ( aitalic_t : m | a< t o< m ) (3) Finally, KLx<2⁢t,m(πu∗||ξ) *KL_x_<2t,m(π^*_u||ξ)KLitalic_x start_POSTSUBSCRIPT < 2 t , m end_POSTSUBSCRIPT ( π∗italic_u | | ξ ) =maxot:m∈m−t+1⁢∑at:mπu∗⁢(at:m|a<t⁢o<m)⁢log⁡πu∗⁢(at:m|a<t⁢o<m)ξ⁢(at:m|a<t⁢o<m)absentsubscriptsubscript:superscript1subscriptsubscript:subscriptsuperscriptconditionalsubscript:subscriptabsentsubscriptabsentsubscriptsuperscriptconditionalsubscript:subscriptabsentsubscriptabsentconditionalsubscript:subscriptabsentsubscriptabsent = _o_t:m∈ X^m-t+1 _a_t:m% π^*_u(a_t:m|a_<to_<m) π^*_u(a_t:m|a_<to_<m)% ξ(a_t:m|a_<to_<m)= maxitalic_o start_POSTSUBSCRIPT t : m ∈ Xitalic_m - t + 1 end_POSTSUBSCRIPT ∑a start_POSTSUBSCRIPT t : m end_POSTSUBSCRIPT π∗italic_u ( aitalic_t : m | a< t o< m ) log divide start_ARG π∗italic_u ( aitalic_t : m | a< t o< m ) end_ARG start_ARG ξ ( aitalic_t : m | a< t o< m ) end_ARG <∑at:mπu∗⁢(at:m|a<t⁢o<m)⁢log⁡2d+K⁢(E)+K⁢(Um)+K⁢(u)absentsubscriptsubscript:subscriptsuperscriptconditionalsubscript:subscriptabsentsubscriptabsentsuperscript2subscript < _a_t:mπ^*_u(a_t:m|a_<to_<m) 2^d+K(E)+K(% U_m)+K(u)< ∑a start_POSTSUBSCRIPT t : m end_POSTSUBSCRIPT π∗italic_u ( aitalic_t : m | a< t o< m ) log 2d + K ( E ) + K ( Uitalic_m ) + K ( u ) =[d+K⁢(E)+K⁢(Um)+K⁢(u)]/log⁡2absentdelimited-[]subscript2 =[d+K(E)+K(U_m)+K(u)]/ 2= [ d + K ( E ) + K ( Uitalic_m ) + K ( u ) ] / log 2 and u=v⁢ξ⁢(x<2⁢t)subscriptabsent2u=vξ(x_<2t)u = v ξ ( x< 2 t ). Therefore, πu∗subscriptsuperscriptπ^*_uπ∗italic_u satisfies the theorem. ∎ What does Theorem 1 mean for the optimizer constrained by KLx<2⁢k,m(π||ξ^i) *KL_x_<2k,m(π|| ξ_i)KLitalic_x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( π | | over start_ARG ξ end_ARGi ) for large i? If the optimization of UmsubscriptU_mUitalic_m does not require urgent action, then one valid strategy for a policy π is to wait for an unprecedented event, imitating the base policy ξ^isubscript ξ_iover start_ARG ξ end_ARGi until then, and then start optimizing. The telescoping property of the KLKL *KLKL Divergence clarifies the validity of this approach. That is, for t>kt>kt > k, KLx<2⁢k,m(π||ρ)=KLx<2⁢k,t(π||ρ)+x2⁢k:2⁢(t−1)∼πKLx<2⁢t,m(π||ρ) *KL_x_<2k,m(π||ρ)= *KL_x_<2k,t(π||% ρ)+E_x_2k:2(t-1) π *KL_x_<2t,m(π||ρ)KLitalic_x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( π | | ρ ) = KLitalic_x start_POSTSUBSCRIPT < 2 k , t end_POSTSUBSCRIPT ( π | | ρ ) + blackboard_Ex start_POSTSUBSCRIPT 2 k : 2 ( t - 1 ) ∼ π end_POSTSUBSCRIPT KLitalic_x start_POSTSUBSCRIPT < 2 t , m end_POSTSUBSCRIPT ( π | | ρ ) (Hutter, 2005). So starting with a policy with low KLKL *KLKL divergence from the base policy preserves a “budget” for high KLKL *KLKL divergence to be “spent” later by switching to a policy with greater divergence from the base policy. * Proof. Consider the very simple event ET=TsubscriptsuperscriptE_T= X^TEitalic_T = Xitalic_T; it occurs (and is of course unprecedented) at time T. K⁢(ET)subscriptK(E_T)K ( Eitalic_T ) is within a constant of K⁢(T)K(T)K ( T ). So we are interested in the rate of growth of minT≥t⁡K⁢(T)subscript _T≥ tK(T)minitalic_T ≥ t K ( T ) as t increases. @swafalse @partrue @fullfalse @citetpzvonkin1970complexity Theorem 1.4 (d) states that this function is eventually less than every computable function that tends to infinity. ∎ Appendix E Total variation distance Definition 7 (Vξ,UmsubscriptsubscriptV_ξ,U_mVitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT-optimal). An action atsubscripta_taitalic_t is Vξ,UmsubscriptsubscriptV_ξ,U_mVitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT-optimal after a history x<2⁢tsubscriptabsent2x_<2tx< 2 t if ot∼ξ(⋅|x<2⁢tat)⁢Vξ,Um∗⁢(x<2⁢t⁢at⁢ot)=Vξ,Um∗⁢(x<2⁢t)E_o_t ξ(·|x_<2ta_t)V^*_ξ,U_m(x_<2ta_to_% t)=V^*_ξ,U_m(x_<2t)blackboard_Eo start_POSTSUBSCRIPT t ∼ ξ ( ⋅ | x< 2 t aitalic_t ) end_POSTSUBSCRIPT V∗italic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t aitalic_t oitalic_t ) = V∗italic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ). * Proof. Letting π⁢(x2⁢t:2⁢m|x<2⁢t):=∏t′=tmπ⁢(at′|x<2⁢t′)assignconditionalsubscript:22subscriptabsent2superscriptsubscriptproductsuperscript′conditionalsubscriptsuperscript′subscriptabsent2superscript′π(x_2t:2m|x_<2t):= _t =t^mπ(a_t |x_<2t^% )π ( x2 t : 2 m | x< 2 t ) := ∏t′ = titalic_m π ( aitalic_t′ | x< 2 t′ ), if πcT⁢V⁢D⁢(at|x<2⁢t)>β⁢(at|x<2⁢t)subscriptsuperscriptconditionalsubscriptsubscriptabsent2conditionalsubscriptsubscriptabsent2π^TVD_c(a_t|x_<2t)>β(a_t|x_<2t)πitalic_T V Ditalic_c ( aitalic_t | x< 2 t ) > β ( aitalic_t | x< 2 t ), then there exists an x2⁢t+1:2⁢msubscript:212x_2t+1:2mx2 t + 1 : 2 m such that πcT⁢V⁢D⁢(at⁢x2⁢t+1:2⁢m|x<2⁢t)>β⁢(at⁢x2⁢t+1:2⁢m|x<2⁢t)subscriptsuperscriptconditionalsubscriptsubscript:212subscriptabsent2conditionalsubscriptsubscript:212subscriptabsent2π^TVD_c(a_tx_2t+1:2m|x_<2t)>β(a_tx_2t+1:2m|x_<2t)πitalic_T V Ditalic_c ( aitalic_t x2 t + 1 : 2 m | x< 2 t ) > β ( aitalic_t x2 t + 1 : 2 m | x< 2 t ). Suppose atsubscripta_taitalic_t is not Vξ,UmsubscriptsubscriptV_ξ,U_mVitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT-optimal. Then there exists an at′subscriptsuperscript′a _ta′italic_t such that Q⁢(x<2⁢t⁢at′)>Q⁢(x<2⁢t⁢at)subscriptabsent2subscriptsuperscript′subscriptabsent2subscriptQ(x_<2ta _t)>Q(x_<2ta_t)Q ( x< 2 t a′italic_t ) > Q ( x< 2 t aitalic_t ). Let x2⁢t+1:2⁢m′subscriptsuperscript′:212x _2t+1:2mx′2 t + 1 : 2 m be a sequence where all actions are Vξ,UmsubscriptsubscriptV_ξ,U_mVitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT-optimal, and all observations have positive probability. Let πε′⁢(x¯2⁢t:2⁢m|x<2⁢t)subscriptsuperscript′conditionalsubscript¯:22subscriptabsent2π _ ( x_2t:2m|x_<2t)π′italic_ε ( over¯ start_ARG x end_ARG2 t : 2 m | x< 2 t ) equal πcT⁢V⁢D⁢(x¯2⁢t:2⁢m|x<2⁢t)subscriptsuperscriptconditionalsubscript¯:22subscriptabsent2π^TVD_c( x_2t:2m|x_<2t)πitalic_T V Ditalic_c ( over¯ start_ARG x end_ARG2 t : 2 m | x< 2 t ) for all x¯2⁢t:2⁢msubscript¯:22 x_2t:2mover¯ start_ARG x end_ARG2 t : 2 m, except πε′⁢(at⁢x2⁢t+1:2⁢m|x<2⁢t)=πcT⁢V⁢D⁢(at⁢x2⁢t+1:2⁢m|x<2⁢t)−εsubscriptsuperscript′conditionalsubscriptsubscript:212subscriptabsent2subscriptsuperscriptconditionalsubscriptsubscript:212subscriptabsent2π _ (a_tx_2t+1:2m|x_<2t)=π^TVD_c(a_tx_2t+% 1:2m|x_<2t)- π′italic_ε ( aitalic_t x2 t + 1 : 2 m | x< 2 t ) = πitalic_T V Ditalic_c ( aitalic_t x2 t + 1 : 2 m | x< 2 t ) - ε, and πε′⁢(at′⁢x2⁢t+1:2⁢m′|x<2⁢t)=πcT⁢V⁢D⁢(at′⁢x2⁢t+1:2⁢m′|x<2⁢t)+εsubscriptsuperscript′conditionalsubscriptsuperscript′subscriptsuperscript′:212subscriptabsent2subscriptsuperscriptconditionalsubscriptsuperscript′subscriptsuperscript′:212subscriptabsent2π _ (a _tx _2t+1:2m|x_<2t)=π^% TVD_c(a _tx _2t+1:2m|x_<2t)+ π′italic_ε ( a′italic_t x′2 t + 1 : 2 m | x< 2 t ) = πitalic_T V Ditalic_c ( a′italic_t x′2 t + 1 : 2 m | x< 2 t ) + ε. The conditional probabilities πε′⁢(at′|x<2⁢t′)subscriptsuperscript′conditionalsubscriptsuperscript′subscriptabsent2superscript′π _ (a_t |x_<2t )π′italic_ε ( aitalic_t′ | x< 2 t′ ) can easily be defined to achieve the properties in the previous sentence. For small enough ε>00 >0ε > 0, this policy exists (no probabilities are outside [0, 1]) because πcT⁢V⁢D⁢(at|x<2⁢t)>β⁢(at|x<2⁢t)≥0subscriptsuperscriptconditionalsubscriptsubscriptabsent2conditionalsubscriptsubscriptabsent20π^TVD_c(a_t|x_<2t)>β(a_t|x_<2t)≥ 0πitalic_T V Ditalic_c ( aitalic_t | x< 2 t ) > β ( aitalic_t | x< 2 t ) ≥ 0 and therefore, πcT⁢V⁢D⁢(at′|x<2⁢t)<1subscriptsuperscriptconditionalsubscriptsuperscript′subscriptabsent21π^TVD_c(a _t|x_<2t)<1πitalic_T V Ditalic_c ( a′italic_t | x< 2 t ) < 1. And for small enough ε>00 >0ε > 0, TVDx<2⁢k,m(πε′,β)≤TVDx<2⁢k,m(πcT⁢V⁢D,β)subscriptTVDsubscriptabsent2subscriptsuperscript′subscriptTVDsubscriptabsent2subscriptsuperscript *TVD_x_<2k,m(π _ ,β)≤% *TVD_x_<2k,m(π^TVD_c,β)TVDitalic_x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( π′italic_ε , β ) ≤ TVDitalic_x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( πitalic_T V Ditalic_c , β ), because decreasing the probability on at⁢x2⁢t+1:2⁢msubscriptsubscript:212a_tx_2t+1:2maitalic_t x2 t + 1 : 2 m will reduce the total variation distance by ε ε, for ε≤π⁢(at⁢x2⁢t+1:2⁢m|x<2⁢t)−β⁢(at⁢x2⁢t+1:2⁢m|x<2⁢t)conditionalsubscriptsubscript:212subscriptabsent2conditionalsubscriptsubscript:212subscriptabsent2 ≤π(a_tx_2t+1:2m|x_<2t)-β(a_tx_2t+1:2m|x_<2t)ε ≤ π ( aitalic_t x2 t + 1 : 2 m | x< 2 t ) - β ( aitalic_t x2 t + 1 : 2 m | x< 2 t ) (which is positive), while increasing the probability on at′⁢x2⁢t+1:2⁢m′subscriptsuperscript′subscriptsuperscript′:212a _tx _2t+1:2ma′italic_t x′2 t + 1 : 2 m will not increase the total variation distance by more than ε ε. Finally, since Q⁢(x<2⁢t⁢at′)>Q⁢(x<2⁢t⁢at)subscriptabsent2subscriptsuperscript′subscriptabsent2subscriptQ(x_<2ta _t)>Q(x_<2ta_t)Q ( x< 2 t a′italic_t ) > Q ( x< 2 t aitalic_t ), Vξ,Umπε′⁢(x<2⁢t)>Vξ,UmπcT⁢V⁢D⁢(x<2⁢t)subscriptsuperscriptsubscriptsuperscript′subscriptsubscriptabsent2subscriptsuperscriptsubscriptsuperscriptsubscriptsubscriptabsent2V^π _ _ξ,U_m(x_<2t)>V^π^TVD_c_ξ,U_% m(x_<2t)Vitalic_π start_POSTSUPERSCRIPT ′ε end_POSTSUPERSCRIPTξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ) > Vitalic_π start_POSTSUPERSCRIPT T V Ditalic_c end_POSTSUPERSCRIPTξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT ( x< 2 t ). This contradicts that πcT⁢V⁢D=arg⁢maxπ:TVDx<2⁢k,m(π,β)<c⁡Vξ,Umπsubscriptsuperscriptsubscriptargmax:subscriptTVDsubscriptabsent2subscriptsuperscriptsubscriptπ^TVD_c= *arg\,max_π: *TVD_x_<2k,m(% π,β)<cV^π_ξ,U_mπitalic_T V Ditalic_c = start_OPERATOR arg max end_OPERATORπ : TVD start_POSTSUBSCRIPT x start_POSTSUBSCRIPT < 2 k , m end_POSTSUBSCRIPT ( π , β ) < c end_POSTSUBSCRIPT Vitalic_πitalic_ξ , U start_POSTSUBSCRIPT m end_POSTSUBSCRIPT since a policy with no more total variation distance has greater value. ∎ Appendix F Detailed experimental setup The details of the experimental setup are as follows. F.1 Environment The state of the environment, as mentioned in the main text, is the activations of the last three hidden layers of Mixtral-base-model with the transcript-so-far as input, along with the fraction of the episode remaining. This gives a state space of 12289. Using the Mistral tokenizer, the action space is 32000. The environment uses a temperature of 0.05 for generating the student’s responses and a temperature of 1 for the base policy for the agent/teacher. F.2 Network Architecture The critic network is a fully connected network with two hidden layers of size 128 with tanh activations. The actor network consists of just one parameterized layer, which is fully connected, of size (|(|( |state space|,||,|| , |action space|+1)|+1)| + 1 ). The extra output is for controlling the KL divergence to the base policy. We compute the target KL divergence as sigmoid(activation) * the KL budget remaining to the agent for the episode. So the activation controls what fraction of the remaining KL budget for the episode to use on the very next token. At initialization, this fraction comes to 1/16. The KL budget remaining starts as the total episode KL budget (of course), and is decreased by log⁡(policy⁢(action)/basepolicy⁢(action))policyactionbasepolicyaction ( policy( action)/ basepolicy( action))log ( policy ( action ) / basepolicy ( action ) ) with each action. The other outputs are interpreted as logits and are added to the base policy logits. Calling this resulting distribution a, and the base policy distribution b, we find an α∈[0,1]01α∈[0,1]α ∈ [ 0 , 1 ] such that KL(αa+(1−α)b||b) *KL(α a+(1-α)b||b)KL ( α a + ( 1 - α ) b | | b ) equals the target KL, if possible. If we cannot achieve a sufficiently high KL divergence, we set α=11α=1α = 1. The output policy is α⁢a+(1−α)⁢b1α a+(1-α)bα a + ( 1 - α ) b. We add any squared error (target KL−achieved KL)2superscripttarget KLachieved KL2( target KL- achieved KL)^2( target KL - achieved KL )2 to the loss function to encourage the network to output logits that allow further control by the neuron controlling the KL target. In the forward pass, our custom PyTorch operation does binary search the calculate α in the interval [0,1]01[0,1][ 0 , 1 ]. The backward pass uses implicit differentiation, assuming we have found exactly the right α—there is no need to differentiate backward through the binary search, which would be unstable. Code for this PyTorch object can be found at https://github.com/mkc1000/kl-fixed-mixture/. F.3 PPO We use the following hyperparameters for PPO. We do not use a generalized advantage estimate. Training timesteps 6 million Update frequency 1 / 64 episodes Training epochs / update 8 Training batch size 213superscript2132^13213 Epsilon clip 0.1 Entropy coefficient 1e-4 Max gradient norm 0.1 Actor learning rate 2e-5 Critic learning rate 1e-4 A higher entropy coefficient is unnecessary given the KL constraint to the base policy. Over the first 3 million timesteps of training, we slowly increase the per-episode KL budget from 0 to its final value. We increase this at a linear schedule each time we update the network. When we re-train for a longer episode length (256 tokens to 512 tokens), we train for 3 million steps, plenty to reach apparent convergence. F.4 Parallelism We use threading to run 64 agent-environment-loops in “parallel”. When we would need to send a transcript of length l to be processed by the Mixtral model, we wait until all 64 agent-environment-loops need to send a transcript of length l, and then they are batched and evaluated together in parallel on the GPU. The result might needed by either the agent or the environment, and we use the python asyncio library to manage this. Doing just that step in parallel is enough for substantial speedup. F.5 Resource Usage We ran our experiments on two A100-SXM4-80GBs. Training for 9 million timesteps took approximately 90 hours. Our seven training runs (one of which was stopped after 6 million timesteps) took about 25 days, all told. (We ran the experiments two or three at a time). The full research project required much more compute, since finding good hyperparameters for PPO is never straightforward, especially when we were attempting to achieve a desired per-episode KL divergence, only with the use of a fixed per-token KL cost; recall that we eventually switched to a policy architecture that allowed direct control of the per-episode KL divergence.

Instant research discovery