Overview

This is my note for Chapter 7 of Reinforcement Learning Theory.

Strategic Exploration in Tabular MDPs

Assumptions in this chapter:

• Finite horizon

• Unknown Transition

Learning Protocol

1. Learner initializes a policy ${\pi }^1$$\pi^1$

2. At episode $n$$n$, learner executes ${\pi }^n$$\pi^n$: $\{s_h^n,a_h^n,r_h^n{\}}_{h=0}^{H-1},$$\{s_{h}^{n},a_{h}^{n},r_{h}^{n}\}_{h=0}^{H-1},$ with $a_h^n={\pi }^n(s_h^n),r_h^n=r(s_h^n,a_h^n),s_{h+1}^n\sim P(\cdot |s_h^n,a_h^n)$$a_{h}^{n}=\pi^{n}(s_{h}^{n}),r_{h}^{n}=r(s_{h}^{n},a_{h}^{n}),s_{h+1}^{n}\sim P(\cdot|s_{h}^{n},a_{h}^{n})$

3. Learner updates policy ${\pi }^{n+1}$$\pi^{n+1}$

The performance measure for $K$$K$ episodes:

If we convert this problem to MAB and run UCB, what is the complexity?

Unique policies: $(|\mathcal{A}{|}^{|\mathcal{S}|}{)}^H$$(|\mathcal A|^{|\mathcal S|})^{H}$ -> all treated as arms

Therefore UCB gives $O(\sqrt{|\mathcal{A}{|}^{|\mathcal{S}|H}K})$$O(\sqrt{|\mathcal A|^{|\mathcal S|H}K})$ which is really bad.

WHY? Policies should not be treated as independent arms!

UCB-VI

• Use all previous data to estimate transactions ${\hat{P}}_1^k,\dots ,{\hat{P}}_{H-1}^k$$\widehat{P}_1^k,\ldots,\widehat{P}_{H-1}^k$

• Design reward bonus $b_h^k(s,a),\mathrm{\forall }s,a,h$$b^k_h(s,a),\forall s,a,h$

• Optimistic planning with learned model: ${\pi }^k=\text{Value-Iter}(\{{\hat{P}}_h^k,r_h+b_h^k{\}}_{h=1}^{H-1})$$\pi^k=\text{Value-Iter}\left(\{\widehat{P}_h^k,r_h+b_h^k\}_{h=1}^{H-1}\right)$

Let us consider the very beginning of episode $k$$k$:

Part 1: Model estimation

And we have empirical estimation:

Part 2: Reward Bonus Design and Value Iteration

We use a bonus to encourage exploration:

Now we perform VI starting from $H$$H$:

Remarks: The $H$$H$ truncation for ${\hat{Q}}_h^n(s,a)$$\widehat{Q}_{h}^{n}(s,a)$ is due to that the reward is bounded and thus no policy's Q value will be larger than $H$$H$ ($\parallel {\hat{V}}_h^n{\parallel }_{\mathrm{\infty }}\le H,\mathrm{\forall }h,n$$\|\widehat{V}_h^n\|_\infty \le H, \forall h, n$).

Analysis

Theorem 7.1 (Regret Bound of UCBVI). UCBVI achieves the following regret bound

Remarks: A sharper bound of $\tilde{O}\left(H^2\sqrt{SAK}\right)$$\tilde{O}\left(H^2\sqrt{SAK}\right)$ can be obtained. UCBVI is suboptimal w.r.t. $H^2$$H^2$.

Remarks: Note that here is an expectation statement, but a high probability version should not be hard with a martingale argument.

Sketch of proof:

• Bonus $b_h^n(s,a)$$b_h^n(s,a)$ is related to $(({\hat{P}}_h^k(\cdot |s,a)-P_h(\cdot |s,a))\cdot V_{h+1}^{\star })$$\left(\left(\widehat{P}_h^k(\cdot|s,a)-P_h(\cdot|s,a)\right)\cdot V_{h+1}^{\star}\right)$

• VI with bonus inside the learned model gives optimism, i.e., ${\hat{V}}_h^k(s)\ge V_h^{\star }(s),\mathrm{\forall }h,n,s,a$$\widehat{V}^k_h(s)≥ V_h^\star(s), \forall h,n,s,a$

• Upper bound per-episode regret:$V_0^{\star }(s_0)-V_0^{{\pi }^k}(s_0)\le {\hat{V}}_0^n(s_0)-V_0^{{\pi }^k}(s_0)$$V_0^{\star}(s_0)-V_0^{\pi^k}(s_0)\leq\widehat{V}_0^n(s_0)-V_0^{\pi^k}(s_0)$

• Apply simulation lemma ${\hat{V}}_0^k(s_0)-V^{{\pi }^k}(s_0)$$\widehat{V}_0^k(s_0)-V^{\pi^k}(s_0)$

Step 1:

Lemma 7.2 (State-action wise model error). Fix $\delta \in (0,1)$$\delta \in (0,1)$. For all $k\in [0,\dots ,K-1],s\in \mathcal{S},a\in \mathcal{A},h\in$$k\in[0,\ldots,K-1],s\in\mathcal{S},a\in\mathcal{A},h\in$ $[0,\dots ,H-1],$$[0,\ldots,H-1],$ with probability at least $1-\delta ,$$1-\delta,$ we have that for any $f:\mathcal{S}\mapsto [0,H]$$f:\mathcal{S}\mapsto[0,H]$:

Proof: Azuma-Hoeffding + Union Bound

Remarks: Here the union bound includes $f$$f$, so we need to utiliza an $ϵ$$\epsilon$-net argument. Refer to https://arxiv.org/pdf/1011.3027.pdf Lemma 5.2. for why we have $|{\mathcal{N}}_{ϵ}|\le (1+2H\sqrt{|\mathcal{S}|}/ϵ{)}^{|\mathcal{S}|}$$|\mathcal N_\epsilon| \le (1 + 2H\sqrt {|\mathcal S|} /\epsilon)^{|\mathcal S|}$ for $f:\mathcal{S}\mapsto [0,H].$$f: \mathcal S \mapsto [0, H].$ (Note that $\parallel f{\parallel }_2\le H\sqrt{|\mathcal{S}|}$$\|f\|_2 \le H \sqrt{|\mathcal S|}$, so we essentially need an $ϵ$$\epsilon$-net for an L2 ball with radii $H\sqrt{|\mathcal{S}|}$$H \sqrt{|\mathcal S|}$)

Remarks: After Union Bound, we only need to bound the points in the $ϵ$$\epsilon$-net.

Lemma 7.3 (State-action wise average model error under $V^{\star }$$V^\star$). Fix ∈(0,1). For all $k\in [1,\dots ,K-1],s\in \mathcal{S},a\in$$k\in[1,\ldots,K-1],s\in\mathcal{S},a\in$ $\mathcal{A},h\in [0,\dots ,H-1],$$\mathcal{A},h\in[0,\ldots,H-1],$and consider $V_h^{\star }:\mathcal{S}\to [0,H],$$V_h^{\star}:\mathcal{S}\to[0,H],$ with probability at least $1-\delta ,$$1-\delta,$ we have:

Proof: This is simply Lemma 7.2 without union bound on $f$$f$.

Step 2:

Denote ${\mathcal{E}}_{model}$$\mathcal{E}_{model}$ as the above events.

Lemma 7.4 (Optimism). Assume ${\mathcal{E}}_{model}$$\mathcal{E}_{model}$ is true. For all episode $k$$k$, we have:

where ${\hat{V}}_h^k$$\widehat{V}_h^k$ is computed based on Vl in Eg.0.3.

Proof: We use induction to exploit the fact that VI is an iterative algo. Proof at P76 of the book.

Lemma 7.5. Consider arbitrary $K$$K$ sequence of trajectories ${\tau }^k=\{s_h^k,a_h^k{\}}_{h=0}^{H-1}$$\tau^k=\{s_h^k,a_h^k\}_{h=0}^{H-1}$ for $k=0,\dots ,K-1$$k=0,\ldots,K-1$ We have

Proof at P77 of the book

Now we can give proof to the main theorem.

Proof at P77 of the book.

Remarks: The simulation lemma is at lecture (basically induction). Also check this note for simulation lemma.

Remarks: Note that ${\hat{V}}_{h+1}^{{\pi }_k}$$\widehat{V}_{h+1}^{\pi_k}$ is data-dependent, so we cannot apply Lemma 7.2. Instead, we need to use Hölder.

An Improved Regret Bound

In this section, we show a regret bound of $\tilde{O}(H^2\sqrt{|\mathcal{S}||\mathcal{A}|K}+H^3|\mathcal{S}{|}^2|\mathcal{A}|)$$\tilde{O}\left(H^2\sqrt{|\mathcal S||\mathcal A|K} + H^3|\mathcal S|^2|\mathcal A|\right)$. The core of the analysis is to use a sharper concentration (Bernstein) than Hoeffding. Check appendix A.7.