{'fraction_non_alphanumeric': 0.05364823348694316, 'fraction_numerical': 0.010330261136712749, 'mean_word_length': 3.8117147080561713, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Delegative Reinforcement Learning: learning to avoid traps with a little help

Most known regret bounds for reinforcement learning are either episodic or assume an environment without traps. We derive a regret bound without making either assumption, by allowing the algorithm to occasionally delegate an action to an external advisor. We thus arrive at a setting of active one-shot model-based reinforcement learning that we call DRL (delegative reinforcement learning.) The algorithm we construct in order to demonstrate the regret bound is a variant of Posterior Sampling Reinforcement Learning supplemented by a subroutine that decides which actions should be delegated. The algorithm is not anytime, since the parameters must be adjusted according to the target time discount. Currently, our analysis is limited to Markov decision processes with finite numbers of hypotheses, states and actions.


INTRODUCTION
A reinforcement learning agent is a system that interacts with an unknown environment in a manner that is designed to maximize the expectation of a utility function that can be written as a sum of rewards over time (sometimes weighted by a time-discount function.) A standard metric for evaluating the performance of such an agent is the regret: the difference between the expected utility of the agent in a given environment, and the expected utility of an optimal policy for the same environment. This metric allows formalizing the notion of "the agent learns the environment" by requiring that the regret has sublinear growth in the planning horizon (usually assuming the utility function is a finite, undiscounted, sum of rewards.) For example, if we consider stateless environments, reinforcement learning reduces to a multi-armed bandit for which algorithms with guaranteed sublinear regret bounds are well-known (see e.g. Bubeck & Cesa-Bianchi (2012).) However, the desideratum of sublinear regret is impossible to achieve even for a finite class of environments without making further assumptions, and this is because of the possible presence of "traps". A trap is a state which, once reached, forces a linear lower bound on regret. Consider the following example. The agent starts at state s 1 , and as long as it takes action a, it receives a reward of 1. However, if it ever takes action b, it will reach state s 2 and remain there, receiving a reward of 0 forever, whatever it does. Thus, s 2 is a trap. On the other hand, it is impossible to design an algorithm which guarantees never entering traps for an arbitrary environment. For example, consider the environment that has the same structure except actions a and b are exchanged. In this case, if the transition matrix is not known a priori, no algorithm can learn the correct behavior, and every algorithm will have linear regret in at least one of the two environments.
There are two widespread approaches to deriving regret bounds which circumvent this problem. One is simply assuming that the environment contains no traps in some formal sense (see e.g. Nguyen et al. (2013).) The other is "episodic learning" (see e.g. Osband & Van Roy (2014).) In episodic learning, the timeline is divided into intervals ("episodes") and, either the state is assumed to reset to the initial state after each episode, or regret is defined s.t. the contribution of each episode is the difference between following the given policy and following the given policy during previous episodes but the optimal policy in the current episode. The latter metric doesn't consider entering a trap to be a fatal event, since in the following episodes this event will be considered as "given." That is, a policy that enters trap can still achieve sublinear regret in this sense. In fact, algorithms designed to achieve sublinear regret for sufficiently general classes of environments have the property that they eventually enter every trap they encounter (such algorithms have a random exploration phase, like e.g. ǫ-exploration in Q-learning.) In terms of practical applications, it means that most known approaches to reinforcement learning that have theoretical performance guarantees either assume that no mistake is "fatal", or that numerous "fatal" mistakes in the training process are acceptable. These assumptions are unacceptable in applications such as controlling a very expensive, breakable piece of machinery (e.g. spaceship) or performing a task that involves significant risk to human lives (e.g. surgery or rescue,) assuming that the algorithm cannot be reliably trained in a simulation since the simulation doesn't reflect all the intricacies of the physical world.
This problem clearly cannot be overcome without using prior knowledge about the environment. In itself, prior knowledge is not such a strong assumption, since at least for any task that can be accomplished by a person, this prior knowledge is already available to us. The challenge is then transferring this knowledge to algorithm. This transfer can be accomplished either by manually transforming the knowledge into a formal mathematical specification, or by establishing a learning protocol that involves a human in the loop. Since human knowledge is often complex, difficult to formalise and partly intuitive, the latter option seems especially attractive.
These idea of using prior knowledge or human intervention to avoid traps has been explored by several authors (see García & Fernández (2015) for a survey.) However, to the best of our knowledge, no previous author has established a regret bound in such a setting. In the present work, we derive such a regret bound, specifically for the setting that Clouse (1997) called "ask for help" and we call "delegative reinforcement learning" (DRL), and specifically for a class of environments which consists of some finite number of Markov decision processes with a finite number of states.
In DRL, an agent interacts with an environment during an infinite sequence of "rounds". On each round, the agent selects an action and the environment transits to a new state which is observed by the agent. The agent then receives a reward which depends on the state. There are two kinds of actions the agent can take: a "direct" action a ∈ A and the special delegation action ⊥. If the agent takes action ⊥, the advisor takes some action b ∈ A which affects the environment in the same way as if it was taken directly. The agent then observes both b and the new state of the environment. The utility function and regret are defined via geometric time discount with a constant γ.
The algorithm we construct in order to show the regret bound is a variant of posterior sampling reinforcement learning (see Osband et al. (2013)). Denoting α := 1 − γ, the timeline is divided into intervals of length O α − 1 /4 . At the start of each interval, the algorithm samples a hypothesis out of its current belief state, and starts carrying out an optimal policy for this hypothesis. On each round, it checks whether the desired action is known to be "safe" with high probability in a particular formal sense. If it is safe, the action is taken. If it isn't safe, delegation is performed. Moreover, the belief state evolves using all observations, but hypotheses whose probability falls below O α 1 /4 are discarded altogether. We then show that (i) given relatively mild assumptions about the advisor (namely, that it only takes safe actions and it takes the optimal action with at least some small probability,) the regret is bounded by O α − 3 /4 1 (in particular it is sublinear in α −1 ) and (ii) the number of delegations behaves like O α − 1 /4 2 . Here, we only gave the dependence on α, but the expressions we obtain are more detailed and reflect the dependence on the number of hypothesis (which we assume to be finite), the derivative of the value functions of the hypotheses and the minimal probability with which the advisor takes an optimal action. The structure of the paper is as follows. Section 2 gives all the necessary definition and formally states the results. Appendix A explains the algorithm implicit in the main theorem and gives an outline of the proofs. Appendix B completes the details of the proofs.

RESULTS
We start by recalling some basic definitions and properties of Markov decision processes. See e.g. Feinberg & Shwartz (2002) for a detailed overview with proofs. First, some notation.
Given measurable spaces X and Y , the notation K : Here, the action ⊥ represents delegation and the A M[υ] factor in S M[υ] represents the action taken by the advisor in the last round (or ⊥ if there was no delegation.) We will also use the following shorthand notations Definition 10. Given any MDP M and γ ∈ (γ M , 1), we define The above quantity is closely related to the bias span parameter, which is known to figure in regret bounds in the no-traps setting (see Bartlett (2009)). Intuitively, it measures how costly can a nonfatal error be (the normalized value lost as a result of such an error is approximately bounded by (1−γ)t M (γ)). It can also be related to the mixing time of the Markov chain resulting from following the optimal policy in the MDP (if P is the maximal period of the chain, and the total variation distance from equilibrium falls as F λ n , then t M ≤ F 1+λ 1−λ + P ), but discussing this in detail is out of the present scope. We can now formulate the main theorem.
For any n ∈ N, we use the notation We also denote Theorem 1. There is some constant C ∈ (0, ∞) s.t. the following holds. Fix some ǫ, η ∈ (0, 1), T ∈ N + , non-empty finite sets S, A, some s 0 ∈ S and some R : and υ k : . We regard the pairs (T k , υ k ) as the set of hypotheses, where T k represents the transition kernel and υ k the advisor policy. Assume that for each k ∈ [N ], υ k is ǫ-sane for the MDP M k := S, A, s 0 , T k , R . Denote That is, we have a Bayesian regret bound for learning the true MDP starting from a prior that is a uniform distribution over N hypotheses, each of which is a joint hypothesis about the transition kernel and the advisor. The bound is formulated in terms of N . It trivially implies a worst-case regret bound as well, at the cost of another factor of N . No doubt it is possible to derive other type of regret bounds for the DRL setting, e.g. in terms of the number of states and actions, but we leave it for future work.
Observe that Theorem 1 is non-trivial even without equation 20, since, Definition 8 is s.t. a policy that always delegates might fail to achieve any meaningful regret bound. Indeed, we can consider the special case of a multi-armed bandit, in which all actions are safe and therefore even the random policy is ǫ-sane (as long as ǫ < 1 |A| ). Such a policy has normalized regret Ω(1), except for the degenerate case when all actions have the same reward.
Note that η and T are external parameters of the policy that we can choose however we like (η is a probability threshold below which we stop considering hypotheses, and T is the length of episodes for the purpose of posterior sampling; see appendix A.) Taking appropriate values (that depend on γ, N , ǫ, |A| andt; when γ approaches 1, η should fall as (1 − γ) 1 4 and T should grow as (1 − γ) − 1 4 ) yields the following Corollary 1. There is some constant C ∈ (0, ∞) s.t. the following holds. Assume the setting of Theorem 1. Assume further that We start by giving an explicit description of an algorithm that implements the policy π † .
By condition ii of Definition 8, for each k ∈ [N ] we can choose some π ⋆k : S → A s.t. for any s ∈ S, π ⋆k (s) ∈ A ⋆ M k (s) and υ k π ⋆k (s) s > ǫ. The algorithm is then a variant of posterior sampling reinforcement learning in time intervals of size T (see Osband et al. (2013)), where sampling hypothesis k leads to using policy π ⋆k but delegating when we are uncertain the action is safe. Also, we repeatedly discard hypotheses with probability below η from our belief distribution. If the currently sampled hypothesis is discarded, the algorithm continues to select safe actions until the end of the time interval, delegating whenever no action is certainly safe.
Note that, when the algorithm references υ k one lines 9 and 18, it doesn't mean delegation. Instead, the algorithm just examines the k-th hypothesis about what the advisor may do.
The form of inequalities (19) and (20) is s.t. we can assume w.l.o.g. that η < 1 N and ǫ < 1 |A| . In particular, the former assumption ensures that we get no division by 0 in line 38 of the algorithm. Line 32 might in principle involve division by 0, in which case the behavior of the algorithm can be arbitrary. For example, we may assume that in this case belief becomes the uniform distribution again (but it doesn't matter.) Lines 33-38 discard hypotheses that are too unlikely in order for the agent to take calculated risks (take an action even when there is a small probability of it being unsafe). Technically, in the proof they are necessary in order to apply certain mutual information inequalities (see below.) On the other hand, we also need belief to coincide with the actual posterior given all observations, which seems like a contradiction. In order to resolve this, we introduce a class of imaginary environments L k! k∈ [N ] in which there is an additional observed signal β taking values in [N ] ⊔ {⊥} that, in environment L k! , takes the value k when belief(k) < η and ⊥ otherwise. Lines 33-38 then correspond to conditioning belief on the observation β = ⊥. That is, in the imaginary setting these lines are replaced by the following: We will thereby derive the regret bound by (i) deriving a regret bound in the imaginary setting and (ii) bounding the difference between the imaginary setting and the real setting.
Given an MDP M and any π : Observe that, in the imaginary setting, the policy π !k : S * • ×S • k − → A • implemented by our algorithm (which depends explicitly on k because k determines β) has the property This is thanks to the condition at line 9 and property i of Definition 8.
Combining π !k with the advisor υ k we get the policy υ k π !k : S * × S k − → A which satisfies (using property i of Definition 8 again) The regret incurred during each "episode" of length T can be divided into short-term (associated with the rewards during the episode) and long-term (associated with the rewards after the episode, or, equivalently, with the value of the state reached at the end of the episode.) To describe the short-term regret, we introduce the policies π ⋆k n : Here, |h| denotes the length of h. That is, for h ∈ S m , |h| := m.
Define R • : S • → [0, 1] by R • (s, a) := R(s). For each k ∈ [N ] and n ∈ N, define EU ⋆k n , EU !k n ∈ [0, 1] by Due to equation (27), the long-term regret per episode is O (t M k (γ) · (1 − γ)). The number of episodes that are significant in terms of time discount is 1 (1−γ)T . Therefore, the total contribution of the long-term regret is O . This gives us 5 In order to further analyze the short-term regret, we introduce the policies π ♯k n : S * × S We also define EU ♯k n ∈ [0, 1] by We can now rewrite EU ⋆k n − EU !k n as EU ⋆k n − EU ♯k n + EU ♯k n − EU !k n and bound the contribution of each term separately.
The difference between π ⋆k n and π ♯k n is that the latter sometimes delegates even in the n-th (and later) episodes 6 . Therefore, we can bound the difference in expected utilities by bounding the expected number of delegations. Now, delegation is only performed in one of two scenarios, corresponding to line 10 and line 14. In the scenario of line 10, we have the action π ⋆hypothesis (state) which, with probability at least η over hypotheses is taken with probability at least ǫ by the advisor (at least η since this is the minimal value belief(hypothesis) can have.) On the other hand, with probability at least η over hypotheses, the same action is never taken by the advisor (otherwise we wouldn't delegate.) Therefore, observing whether this action is taken by the advisor provides an amount of information about the environment that can be bounded below in terms of η and ǫ. In the scenario of line 14, there is no action which is known with probability at least 1 − η over hypotheses to be taken by the advisor with positive probability. Since observing the action actually taken by the advisor provides an example of an action which had positive probability, we gain an amount of information that can be bounded from below in terms of η. In both cases, we can show information gain is Ω(ηǫ) (see Proposition 3 7 .) Since the initial entropy is ln N , this means that the number of delegations is 5 See Proposition 2 for the detailed derivation. 6 Technically, π ⋆k n is a policy for M k so it's not strictly meaningful to say it "delegates" at all, but we think of it as delegating when the π !k "subroutine" inside it is called and delegates. 7 We think of K as the (unknown) correct hypothesis, X as the advisor action and a * as π ⋆hypothesis (state).
We bounded the expected number of delegations for π !k but not π ♯k n . Since π ♯k n differs from π !k only by always selecting the correct hypothesis at the n-th and further episodes, and since the probability of selecting the correct hypothesis at line 4 is at least η, we get Observing the rewards received during an episode yields information about the environment. The expected information gain can only vanish when you expect to receive the same rewards regardless of which hypothesis is correct, in which case the policy π ⋆hypothesis is optimal regardless of hypothesis. This allows us to derive a lower bound for the information gain in terms of the difference between the rewards received by π !k and π ♯k n . Denoting I n the expected information gain in episode n, we have (see Proposition 5 and further details in Appendix B) Using once again the fact that the initial entropy is ln N , this implies Combining inequalities (31), (35) and (37), we get Finally, we observe that, in the real setting (without the β signal,) line 35 can be reached at most N − 1 times before the first division by zero at line 32. Moreover, such division by zero will never happen unless the correct hypothesis is discarded. Each time line 35 is reached, the probability that belief assigns probability below η to the correct hypothesis is at most η. Therefore, the probability that the correct hypothesis is discarded is at most η(N −1). This allows us to bound the total variation distance between the real setting and imaginary setting by O(ηN ), producing inequality (19) 9 .
For reasons we already outlined, we have Using Markov's inequality, we get Using again the relationship we established between the real and imaginary settings, we get inequality (20) 10 .

B PROOF DETAILS
Definition 12. Given an MDP M and π : Given a set A, x ∈ A ω and n ∈ N, the notation x :n will indicate the prefix of x of length n. That is, x :n ∈ A n and x :n ⊏ x.
Proof. For the sake of encumbering the notation less, we will omit the argument γ in functions that depend on it. We will also omit the subscript M and denote s 0 := s M .
For any x ∈ S ω s.t. s 0 ⊏ x, it is easy to see that The reason inequality (19) has 1 ǫ + |A| instead of ǫ is because we needed to assume w.l.o.g. that ǫ < 1 |A| . On the other hand, the assumption 1 η < N is justified by the appearance of the ηN term in the bound. Also, we can use (1 − γ)T instead of 1 − γ T because the form of the bound allows assuming w.l.o.g. that (1 − γ)T ≪ 1. 10 The reason that the second term of the right hand side of inequality (20) has 1 η +N instead of η and 1 ǫ +|A| instead of ǫ is because we needed to assume w.l.o.g. that η < 1 N and ǫ < 1 |A| .
Taking expected value over x w.r.t. M π, we get Equation (3) implies that the second term vanishes, yielding the desired result. For any n ∈ N, define EU ⋆ n , EU 0 n ∈ [0, 1] by

Proposition 2. Consider an MDP
Then, Proof. For the sake of encumbering the notation less, we will use the shorthands R n := R M (x n ), V n := V M (x n , γ), V 0 n := V 0 M (x n ), Q πn := Q Mπ (x :n+1 , γ) and t := t M (γ). By Proposition 1, for any l ∈ N

Reg
l coincides with π ⋆ after lT , therefore the corresponding terms on the right hand side vanish.

Reg
Subtracting the equalities for l + 1 and l, we get π ⋆ l and π ⋆ l+1 coincide until lT , therefore Both π ⋆ l and π ⋆ l+1 coincide with π ⋆ after (l + 1)T , therefore By the mean value theorem, for each s ∈ S M we have It follows that It is easy to see that assumptions i and ii imply that V 0 n is a martingale for M π ⋆ and M π 0 and therefore We get Summing over l, we get Applying Proposition 1 to the right hand side and using equations (43) and (44) we get the desired result.
Given (Ω, P ∈ ∆Ω) a probability space, A, B finite sets and X : Ω → A, Y : Ω → B random variables, I [X; Y ] denotes the mutual information between X and Y . Given C another finite set and Z : Ω → C another random variable, I [X; Y | Z] : Ω → R will denote the random variable obtained by first conditioning on Z and then taking the mutual information between X and Y , not the expected value of this quantity, as sometimes used. X * P ∈ ∆A denotes the pushforward of P by X, i.e. the probability distribution of X. P | X : Ω → ∆Ω denotes the conditional probability measure (P conditioned on the value of X.) Given µ, ν ∈ ∆A, D KL (µ | ν) denotes the Kullb-Leibler divergence of µ from ν.
Proposition 3. Consider A a finite set, a * ∈ A, N ∈ N + , ǫ ∈ 0, |A| −1 , and η ∈ (0, 1). Consider also (Ω, P ) a probability space and random variables K : Ω → [N ] and X : Ω → A. Suppose that for every a ∈ A Proof. Define q ∈ (0, 1) by Let a q ∈ A be s.t. Pr [X = a q ] > qǫ and either a q = a * or Pr [X = a * ] ≤ qǫ. For every k ∈ supp K * P , denote If a q ∈ A k then either Pr [X = a q | K = k] = 0 or both Pr [X = a * ] ≤ qǫ and Pr [X = a * | K = k] > ǫ. In this case, conditioning by K = k causes either the probability of X = a q to go down from at least qǫ to 0 or the probability of X = a * to go up from at most qǫ to at least ǫ. We get We have It follows that In our notation, propositions about random variables are understood to hold almost surely.
Using assumption iii, we get By assumption ii, the event X n = ⊥ is determined by Θ n , Ψ n and Z n . Using assumption i, it follows that for any n ∈ N, a ∈ A and k ∈ [K] Using assumption ii, we get X n+1 = ⊥ =⇒ ∃k ∈ supp Z n : ¬D nak Using assumption iv Using assumption iii Applying Proposition 3 we conclude Combining inequality (49) with inequality (50), we get Given a measurable space X and µ, ν ∈ ∆X, d tv (µ, ν) will denote the total variation distance between µ and ν. Using assumption ii Using Pinsker's inequality Using assumption iii Using assumptions i and ii again, we get the desired result Given a proposition π, the notation [[π]] ∈ {0, 1} will mean 0 when the π is false and 1 when π is true.
Proof of Theorem 1. The form of inequalities (19) and (20) is s.t. we can assume w.l.o.g. that η < 1 N and ǫ < 1 |A| . We are going to construct a probability space (Ω, P ) and the random variables K : Ω → [N ] and for each n ∈ N We also define H † n : Ω → S n by By condition ii of Definition 8, for each k ∈ [N ] we can choose some π ⋆k : S → A s.t. for any s ∈ S, π ⋆k (s) ∈ A ⋆ M k (s) and υ k π k (s) s > ǫ. We postulate that K is uniformly distributed and for any k ∈ [N ], l ∈ N, m ∈ [T ], s ∈ S and a ∈ A • , denoting n = lT + m Note that the last equation has the form of a Bayesian update which is allowed to be arbitrary when update is on "impossible" information.
This probability space can be constructed using standard arguments from the Kolmogorov extension theorem.
We now define π † s.t. for any n ∈ N, a ∈ A • , h ∈ S n • and s ∈ S • In order to prove π † has the desired properties, we will define the stochastic processes Z,Z, J, Ψ, A, X and Θ, each process of the same type as its dagger counterpart (thus Ω is constructed to accommodate them.) These processes are required to satisfy the following: As before, we also define H n := (Θ 0 , Θ 1 . . . Θ n−1 ).
We now construct π !k : S * s.t. for any n ∈ N, a ∈ A • , h ∈ S n • and s ∈ S • Pr [H n = h, (Θ n , X n ) = s, K = k] > 0 =⇒ π !k (a | h, s) := Pr [A n = a | H n = h, (Θ n , X n ) = s, K = k] It is easy to see equation (27) holds, allowing us to apply Proposition 2 and get Here, EU ⋆k n and EU !k n are defined according to equations (29) and (30) respectively. We also define the π ♯k n : S * • × S • k − → A • by π ♯k n (a | h, s) := π !k (a | h) if |h| < nT Pr [A n = a | H n = h, (Θ n , X n ) = s, K = k, J n = k] otherwise Defining EU ♯k n according to equation (32), we have γ nT EU ⋆k n − EU ♯k n + EU ♯k n − EU !k n + 2t M k (γ) · 1 − γ 1 − γ T Using equation (34), we can apply Proposition 4. Indeed, conditions i, iii and iv are straightforward (for an appropriate definition ofΘ.) To verify condition ii, consider two cases. In the case Z n (J l ) > 0 (where l := ⌊ n /T ⌋,) we have Ψ n = ⊥ and hence A n = ⊥ (equivalently X n+1 = ⊥) if and only if ∃k ∈ supp Z n : υ k (Ψ n | Θ n ) = 0. This is equivalent to condition ii since, for any a = Ψ n , taking k = J l makes the proposition false due to the fact that υ J l π ⋆J l (Θ n ) Θ n > ǫ by construction of π ⋆k . In the case Z n (J l ) = 0, we have Ψ n = ⊥ and hence A n = ⊥ (equivalently X n+1 = ⊥) if and only if ∀a ∈ A∃k ∈ supp Z n : υ k (a | Θ n ) = 0. This is equivalent to condition ii since, in this case, a = Ψ n always. We get Define the random variables {U n : Ω → [0, 1]} n∈N by We apply Proposition 5 to each term in the sum over n.
Thus, we derived equation (38) and the rest of the proof can be completed as in appendix A.

3/4
By equation (21), the expression we round to get T is ≥ 1, therefore this rounding can be absorbed within the constant factor. Equations (23) and (24) follow straightforwardly 11 .

ACKNOWLEDGMENTS
This work was supported by the Machine Intelligence Research Institute (Berkeley, California, USA).
We wish to thank Alexander Appel for reviewing drafts of this work and providing helpful feedback.