Improved regret bound for DRL

[Vanessa Kosoy]

% operators that are separated from the operand by a space

% autosize deliminaters

% operators that require brackets

% operators that require parentheses

% Paper specific

There is a simple way to somewhat improve the regret bound for DRL we derived before. Specifically, we have the following

#Theorem 1

There is some $C\in (0,\infty )$ s.t. the following holds.

Consider $I$ an interface, $\alpha ,ϵ\in (0,1)$, $H=\{{\upsilon }^k=({\mu }^k,r^k)\in {{\rm Y}}_I{\}}_{k\in \left[N\right]}$ for some $N\in N$. For each $k\in \left[N\right]$, let ${\sigma }^k$ be an $ϵ$-sane policy for ${\upsilon }^k$. For each $k\in \left[N\right]$, let $M^k$ be the corresponding MDP. Denote

$$\tau :=\frac{1}{N}\sum _{k=0}^{N-1}\underset{s\in S^k}{max}\underset{\gamma \in [1-\alpha ,1)}{sup}\left|\frac{d{V}_{M^k}(s,\gamma )}{d\gamma }\right|+1$$

Assume that

i. For each $k\in \left[N\right]$, $\alpha \le 1-{\gamma }_{M^k}$.

ii. $$\alpha \le \frac{1}{N^2{\left(\ln N\right)}^{4/3}}{(\frac{1}{ϵ}+\left|A\right|)}^{-1}{\tau }^{8/3}$$

Then, there is an $\overline{I}$-policy ${\pi }^{\ast }$ s.t.

$$\frac{1}{N}\sum _{k=0}^N\left({\mathrm{EU}}_{{\upsilon }^k}^{\ast }\right(1-\alpha )-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k\right]}^{{\pi }^{\ast }}(1-\alpha \left)\right)\le C{\alpha }^{1/4}{N}^{1/2}{\left(\ln N\right)}^{1/3}{(\frac{1}{ϵ}+\left|A\right|)}^{1/4}{\tau }^{1/3}$$

---

This gives gives us better dependence on $N$ but worse dependence on $\tau$ compared to what we had before. However, we can also get the best of both bounds with a single algorithm, since the only difference between the algorithms is in the choice of the parameters $\eta$ and $T$ (which can be chosen to give the better of the two bounds for the given parameters).

To show Theorem 1, we use the following proposition which appears in Russo and Van Roy as Proposition 3 (see page 16):

#Proposition 1

Consider a probability space $(\Omega ,P\in \Delta \Omega )$, $N\in N$, $R\subseteq [0,1]$ a finite set and random variables $U:\Omega \to R$, $K:\Omega \to \left[N\right]$ and $J:\Omega \to \left[N\right]$. Assume that $K_{\ast }P=J_{\ast }P$ and $\underset{}{I}[K;J]=0$. Then

$$\underset{}{I}[K;J,U]\ge \frac{2}{N}{(\underset{}{E}[U\mid J=K,K]-\underset{}{E}\left[U\right])}^2$$

---

Theorem 1 is now proved exactly as before, with Proposition 1 replacing what was previously called Proposition B.3 and setting $\eta$ and $T$ to

$$\eta ={\alpha }^{1/4}{N}^{-1/2}{\left(\ln N\right)}^{1/3}{(\frac{1}{ϵ}+\left|A\right|)}^{1/4}{\tau }^{1/3}$$

$$T={\alpha }^{-1/4}{N}^{-1/2}{\left(\ln N\right)}^{-1/3}{(\frac{1}{ϵ}+\left|A\right|)}^{-1/4}{\tau }^{2/3}$$