TLDR: I derive a variant of the RL regret bound by Osband and Van Roy (2014), that applies to learning without resets of environments without traps. The advantage of this regret bound over those known in the literature, is that it scales with certain learning-theoretic dimensions rather than number of states and actions. My goal is building on this result to derive this type of regret bound for DRL, and, later on, other settings interesting from an AI alignment perspective.

Previously I derived a regret bound for deterministic environments that scales with prior entropy and "prediction dimension". That bound behaves as $O (\sqrt{1 - γ})$ in the episodic setting but only as $O (\sqrt[3]{1 - γ})$ in the setting without resets. Moreover, my attempts to generalize the result to stochastic environments led to bounds that are even weaker (have a lower exponent). Therefore, I decided to put that line of attack on hold, and use Osband and Van Roy's technique instead, leading to an $O (\sqrt{1 - γ})$ bound in the stochastic setting without resets. This bound doesn't scale down with the entropy of the prior, but this does not seem as important as dependence on $γ$ .

Results

Russo and Van Roy (2013) introduced the concept of "eluder dimension" for the benefit of the multi-armed bandit setting, and Osband and Van Roy extended it to a form suitable for studying reinforcement learning. We will consider the following, slightly modified version of their definition.

Given a real vector space $Y$ , we will use $P S D (Y)$ to denote the set of positive semidefinite bilinear forms on $Y$ and $P D (Y)$ to denote the set of positive definite bilinear forms on $Y$ . Given a bilinear form $B : Y \times Y \to R$ , we will slightly abuse notation by also regarding it as a linear functional $B : Y \otimes Y \to R$ . Thereby, we have $B (v \otimes w) = B (v, w)$ and $B v^{\otimes 2} = B (v, v)$ . Also, if $Y$ is finite-dimensional and $B$ is non-degenerate, we will denote $B^{- 1} : Y^{*} \times Y^{*} \to R$ the unique bilinear form which satisfies

$\forall v \in Y, α \in Y^{*} : (\forall β \in Y^{*} : B^{- 1} (α, β) = β v) ⟺ (\forall w \in Y : B (v, w) = α w)$

Definition 1

Consider a set $X$ , a real vector space $Y$ , some $F \subseteq {X \to Y}$ and a family ${B_{x} \in P S D (Y)}_{x \in X}$ . Consider also $n \in N$ , a sequence ${x_{k} \in X}_{k \in [n]}$ and $x^{*} \in X$ . $x^{*}$ is said to be $(F, B)$ -dependant on ${x_{k}}$ when, for any $f, ~ f \in F$

$n - 1 \sum k = 0 B_{x_{k}} {(f (x_{k}) - ~ f (x_{k}))}^{\otimes 2} \leq 1 ⟹ B_{x^{*}} {(f (x^{*}) - ~ f (x^{*}))}^{\otimes 2} \leq 1$

Otherwise, $x^{*}$ is said to be $(F, B)$ -independent of ${x_{k}}$ .

Definition 2

Consider a set $X$ , a real vector space $Y$ and some $F \subseteq {X \to Y}$ . The Russo-Van Roy-Osband dimension (RVO dimension) ${dim}_{R V O} F$ is the

...