Previously, we defined a setting called "Delegative Inverse Reinforcement Learning" (DIRL) in which the agent can delegate actions to an "advisor" and the reward is only visible to the advisor as well. We proved a sublinear regret bound (converted to traditional normalization in online learning, the bound is $O (n^{2 / 3})$ ) for one-shot DIRL (as opposed to standard regret bounds in RL which are only applicable in the episodic setting). However, this required a rather strong assumption about the advisor: in particular, the advisor had to choose the optimal action with maximal likelihood. Here, we consider "Delegative Reinforcement Learning" (DRL), i.e. a similar setting in which the reward is directly observable by the agent. We also restrict our attention to finite MDP environments (we believe these results can be generalized to a much larger class of environments, but not to arbitrary environments). On the other hand, the assumption about the advisor is much weaker: the advisor is only required to avoid catastrophic actions (i.e. actions that lose value to zeroth order in the interest rate) and assign some positive probability to a nearly optimal action. As before, we prove a one-shot regret bound (in traditional normalization, $O (n^{3 / 4})$ ). Analogously to before, we allow for "corrupt" states in which both the advisor and the reward signal stop being reliable.

Appendix A contains the proofs and Appendix B contains propositions proved before.

Notation

The notation $K : X k \to Y$ means $K$ is Markov kernel from $X$ to $Y$ . When $Y$ is a finite set, this is the same as a measurable function $K : X \to Δ Y$ , and we use these notations interchangeably. Given $K : X k \to Y$ and $A \subseteq Y$ (corr. $y \in Y$ ), we will use the notation $K (A ∣ x)$ (corr $K (y ∣ x)$ ) to stand for ${Pr}_{y^{'} \sim K (x)} [y^{'} \in A]$ (corr. ${Pr}_{y^{'} \sim K (x)} [y^{'} = y]$ ). Given $Y$ is a finite set, $μ \in Δ Y^{ω}$ , $h \in Y^{*}$ and $y \in Y$ , the notation $μ (y ∣ h)$ means ${Pr}_{x \sim μ} [x_{| h |} = y ∣ x_{: | h |} = h]$ .

Given $Ω$ a measurable space, $μ \in Δ Ω$ , $n, m \in N$ , ${A_{k}}_{k \in [n]}$ , ${B_{j}}_{j \in [m]}$ finite sets and ${X_{k} : Ω \to A_{k}}_{k \in [n]}$ , ${Y_{j} : Ω \to B_{j}}_{j \in [m]}$ random variables (measurable mappings), the mutual information between the joint distribution of the $X_{k}$ and the joint distribution of the $Y_{j}$ will be denoted

$I ω \sim μ [X_{0}, X_{1} \dots X_{n - 1}; Y_{0}, Y_{1} \dots Y_{m - 1}]$

We will parameterize our geometric time discount by $γ = e^{- 1 / t}$ , thus all functions that were previously defined to depend on $t$ are now considered functions of $γ$ .

Results

We star

...