Model-based Reinforcement Learning \\ and the Eluder Dimension
Ian Osband
Stanford University
iosband@stanford.edu
We consider the problem of learning to optimize an unknown Markov decision process (MDP). We show that, if the MDP can be parameterized within some known function class, we can obtain regret bounds that scale with the dimensionality, rather than cardinality, of the system. We characterize this dependence explicitly as $\tilde{O(\sqrt{d_K d_E T)$ where $T$ is time elapsed, $d_K$ is the Kolmogorov dimension and $d_E$ is the eluder dimension. These represent the first unified regret bounds for model-based reinforcement learning and provide state of the art guarantees in several important settings. Moreover, we present a simple and computationally efficient algorithm posterior sampling for reinforcement learning (PSRL) that satisfies these bounds.
EluderL2.tex
\documentclass{article}

%---------------------------------------------------------------------------------------------------------------------------------------------
% Including Packages
\usepackage{nips14submit_e,times}
\usepackage{color}
\usepackage{algorithm, algpseudocode}
\usepackage{ mathrsfs }
\usepackage{ dsfont }
\usepackage{lmodern}
\usepackage{array}
\usepackage{bbm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[mathscr]{eucal}
\usepackage{graphicx}
\usepackage{mathrsfs}
\usepackage{psfrag}
\usepackage{color}
\usepackage{here}
%\usepackage[margin=1in]{geometry}
\usepackage{wasysym}
%\usepackage[T1]{fontenc}
%\usepackage[charter]{mathdesign}
%\usepackage{eulervm}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsthm}
%\usepackage{ntheorem}
\usepackage{lipsum}
%\setlength{\parskip}{2pt}%
%\setlength{\parindent}{12pt}%


%\theoremstyle{break}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{lemma2}{Lemma}
\newtheorem{mydef}{Definition}
\newtheorem{prop}{Proposition}
\newtheorem{claim}{Claim}
\newtheorem{assumption}{Assumption}
%---------------------------------------------------------------------------------------------------------------------------------------------
% Setting up macro shortcuts
\newcommand{\Exp}{\mathds{E}}
\newcommand{\Expk}{\mathds{E}_{k}}
\newcommand{\Prob}{\mathds{P}}
\newcommand{\Real}{\mathds{R}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\Ind}{\mathds{1}}

\newcommand{\Xc}{\mathcal{X}}
\newcommand{\Yc}{\mathcal{Y}}
\newcommand{\Zc}{\mathcal{Z}}
\newcommand{\Pc}{\mathcal{P}}
\newcommand{\Qc}{\mathcal{Q}}
\newcommand{\Fc}{\mathcal{F}}
\newcommand{\Gc}{\mathcal{G}}
\newcommand{\Rc}{\mathcal{R}}
\newcommand{\Sc}{\mathcal{S}}
\newcommand{\Ac}{\mathcal{A}}
\newcommand{\Mc}{\mathcal{M}}
\newcommand{\Tc}{\mathcal{T}}
\newcommand{\Ec}{\mathcal{E}}
\newcommand{\Dc}{\mathcal{D}}
\newcommand{\Dep}{ \Delta^H,\Delta^F,\mathcal{F},\epsilon }

\newcommand{\conf}{\mathcal{F}^d_t}

\newcommand{\vect}[1]{\boldsymbol{#1}}
\newcommand{\opt}{M^*}
\newcommand{\sampled}{{M_k}}
\newcommand{\Pstar}{P^{*}(\cdot \mid s_t, a_t)}
\newcommand{\Pk}{P_{k}(\cdot \mid s_t, a_t)}
\newcommand{\Pdiff}{(P_{k}-P^{*})(\cdot \mid s_t, a_t)}
\newcommand{\Rdiff}{(r_k-r^{*})(s_t, a_t)}
\newcommand{\optPol}{\mu^{*}}
\newcommand{\sampledPol}{\mu_{k}}
\newcommand{\bellmanSampled}{\mathcal{T}_{\mu_{k}(\cdot,i)}^{k}}
\newcommand{\bellmanTrue}{\mathcal{T}_{\mu_{k}(\cdot,i)}^{*}}
\newcommand{\bellmanSampledA}{\mathcal{T}_{\mu_{k}(\cdot,1)}^{k}}
\newcommand{\bellmanTrueA}{\mathcal{T}_{\mu_{k}(\cdot,1)}^{*}}
\newcommand{\vSampled}{V_{\mu_k, 1}^{k}}
\newcommand{\vSampledi}{V_{\mu_k, i}^{k}}
\newcommand{\vTrue}{V_{\tau, \mu_k}^{*}}

%--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

\title{Model-based Reinforcement Learning \\ and the Eluder Dimension}
\author{Ian Osband \\
Stanford University \\
\texttt{iosband@stanford.edu} \\
\And
Benjamin Van Roy \\
Stanford University \\
\texttt{bvr@stanford.edu}}


\nipsfinalcopy

\begin{document}
\maketitle


%--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\begin{abstract}
We consider the problem of learning to optimize an unknown Markov decision process (MDP).
We show that, if the MDP can be parameterized within some known function class, we can obtain regret bounds that scale with the dimensionality, rather than cardinality, of the system.
We characterize this dependence explicitly as $\tilde{O}(\sqrt{d_K d_E T})$ where $T$ is time elapsed, $d_K$ is the Kolmogorov dimension and $d_E$ is the \emph{eluder dimension}.
These represent the first unified regret bounds for model-based reinforcement learning and provide state of the art guarantees in several important settings.
Moreover, we present a simple and computationally efficient algorithm \emph{posterior sampling for reinforcement learning} (PSRL) that satisfies these bounds.

\end{abstract}


%--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Introduction}

We consider the reinforcement learning (RL) problem of optimizing rewards in an unknown Markov decision process (MDP) \cite{burnetas1997optimal}.
In this setting an agent makes sequential decisions within its enironment to maximize its cumulative rewards through time.
We model the environment as an MDP, however, unlike the standard MDP planning problem the agent is unsure of the underlying reward and transition functions.
Through exploring poorly-understood policies, an agent may improve its understanding of its environment but it may improve its short term rewards by exploiting its existing knowledge \cite{lai1985asymptotically,kaelbling1996reinforcement}.

The focus of the literature in this area has been to develop algorithms whose performance will be close to optimal in some sense.
There are numerous criteria for statistical and computational efficiency that might be considered.
Some of the most common include PAC (Probably Approximately Correct) \cite{valiant1984theory}, MB (Mistake Bound) \cite{littlestone1988learning}, KWIK (Knows What It Knows) \cite{li2011knows} and regret \cite{jaksch2010near}.
We will focus our attention upon regret, or the shortfall in the agent's expected rewards compared to that of the optimal policy.
We believe this is a natural criteria for performance during learning, although these concepts are closely linked.
A good overview of various efficiency guarantees is given in section 3 of Li et al. \cite{li2011knows}.

% Plan for the rest:
% - Model-based vs Model-free, we only get good regret bounds with model-based.
% - The problem is that for *anything* we are running into lower bounds on regret already.
% - People have looked at special settings --> move beyond these limits.
% - Simple general algorithm PSRL and capture complexity in terms of the Eluder dimension

Broadly, algorithms for RL can be separated as either model-based, which build a generative model of the environment, or model-free which do not.
Algorithms of both type have been developed to provide PAC-MDP bounds polynomial in the number of states $S$ and actions $A$ \cite{kearns2002near,brafman2003r,strehl2006pac}.
However, model-free approaches can struggle to plan efficient exploration.
The only near-optimal regret bounds to time $T$ of $\tilde{O}(S\sqrt{AT})$ have only been attained by model-based algorithms \cite{jaksch2010near,osband2013more}.
But even these bounds grow with the cardinality of the state and action spaces, which may be extremely large or even infinite.
Worse still, there is a lower bound $\Omega ( \sqrt{SAT} )$ for the expected regret in an arbitrary MDP \cite{jaksch2010near}.

In special cases, where the reward or transition function is known to belong to a certain functional family, existing algorithms can exploit the structure to move beyond this ```tabula rasa'' (where nothing is assumed beyond $S$ and $A$) lower bound.
The most widely-studied parameterization is the degenerate MDP with no transitions, the mutli-armed bandit \cite{auer2003using,bubeck2011xarmed,russo2013}.
Another common assumption is that the transition function is linear in states and actions.
Papers here establigh regret bounds $\tilde{O}(\sqrt{T})$ for linear quadratic control \cite{abbasi2011improved}, but with constants that grow exponentially with dimension.
Later works remove this exponential dependence, but only under significant sparsity assumptions \cite{ibrahimi2012efficient}.
The most general previous analysis considers rewards and transitions that are $\alpha$-H\"{o}lder in a $d$-dimensional space to establish regret bounds $\tilde{O}(T^{(2d+\alpha)/(2d+2\alpha)})$ \cite{ortner2012online}.
However, the proposed algorithm UCCRL is not computationally tractable and the bounds approach linearity in many settings.

In this paper we analyse the simple and intuitive algorithm \emph{posterior sampling for reinforcement learning} (PSRL) \cite{thompson1933,strens2000bayesian,osband2013more}.
PSRL was initially introduced as a heuristic method \cite{strens2000bayesian}, but has since been shown to satisfy state of the art regret bounds in finite MDPs \cite{osband2013more} and also exploit the structure of factored MDPs    \cite{osband2014near}.
We show that this same algorithm satisfies general regret bounds that depends upon the dimensionality, rather than the cardinality, of the underlying reward and transition function classes.
To characterize the complexity of this learning problem we extend the definition of the eluder dimension, previously introduced for bandits \cite{russo2013eluder}, to capture the complexity of the reinforcement learning problem.
Our results provide a unified analysis of model-based reinforcement learning in general and provide new state of the art bounds in several important problem settings.


%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Problem formulation}

We consider the problem of learning to optimize a random finite horizon MDP $M = (\Sc, \Ac, R^M, P^M, \tau, \rho)$ in repeated finite episodes of interaction.
$\Sc$ is the state space, $\Ac$ is the action space, $R^M(s,a)$ is the reward distribution over $\Real$ and $P^M(\cdot|s,a)$ is the transition distribution over $\Sc$ when selecting action $a$ in state $s$, $\tau$ is the time horizon, and $\rho$ the initial state distribution.
All random variables we will consider are on a probability space $(\Omega, \mathscr{F}, \mathbb{P})$.

A policy $\mu$ is a function mapping each state $s \in \Sc$ and $i = 1,\ldots,\tau$ to an action $a \in \Ac$.
For each MDP $M$ and policy $\mu$, we define a value function $V$:
\begin{equation}
\label{eq: value fn}
V^{M}_{\mu, i}(s) := \Exp_{M,\mu}\big[ \sum_{j=i}^{\tau} \overline{r}^M(s_j,a_j) \Big| s_i = s\big]
\end{equation}
where $\overline{r}^M(s,a) := \Exp[r | r \sim R^M(s,a)]$ and the subscripts of the expectation operator indicate that $a_j = \mu(s_j, j)$, and $s_{j+1} \sim P^M(\cdot| s_j, a_j)$ for $j = i, \ldots, \tau$.  A policy $\mu$ is said to be optimal for MDP $M$ if $V^{M}_{\mu, i}(s) = \max_{\mu'} V^{M}_{\mu', i}(s)$ for all $s \in \Sc$ and $i=1,\ldots,\tau$. We will associate with each MDP $M$ a policy $\mu^M$ that is optimal for $M$.

We require that the state space $\Sc$ is a subset of $\Real^d$ for some finite $d$ with a $\| \cdot \|_2$-norm induced by an inner product.
These result actually extend to general Hilbert spaces, but we will not deal with that in this paper.
This allows us to decompose the transition function as a mean value in $\Sc$ plus additive noise $s' \sim P^M(\cdot|s,a) \implies s' = \overline{p}^M(s,a) + \epsilon_P$.
At first this may seem to exclude discrete MDPs with $S$ states from our analysis.
However, we can represent the discrete state as a probability vector $s_t \in \Sc = [0,1]^S \subset \Real^S$ with a single active component equal to 1 and 0 otherwise.
In fact, the notational convention that $\Sc \subseteq \Real^d$ should not impose a great restriction for most practical settings.


For any distribution $\Phi$ over $\Sc$, we define the one step future value function $U$ to be the expected value of the optimal policy with the next state distributed according to $\Phi$.
\begin{equation}
\label{eq: future value}
U^M_{i}(\Phi) := \Exp_{M,\mu^M}\big[ V^M_{\mu^M,i+1}(s) \big| s \sim \Phi \big].
\end{equation}
One natural regularity condition for learning is that the future values of similar distributions should be similar.
We examine this idea through the Lipschitz constant on the means of these state distributions.
We write $\Ec(\Phi) := \Exp[s | s \sim \Phi] \in \Sc$ for the mean of a distribution $\Phi$ and express the Lipschitz continuity for $U_i^M$ with respect to the $\|\cdot\|_2$-norm of the mean:
\begin{equation}
\label{eq: future Lipschitz}
| U^M_i(\Phi) - U^M_i(\tilde{\Phi}) | \le K^M_i(\Dc) \| \Ec(\Phi) - \Ec(\tilde{\Phi}) \|_2 {\rm \ for \ all \ } \Phi, \tilde{\Phi} \in \Dc
\end{equation}
We define $K^M(\Dc) := \max_{i} K^M_i(\Dc)$ to be a global Lipschitz contant for the future value function with state distributions from $\Dc$.
Where appropriate, we will condense our notation to write $K^M := K^M(\mathscr{D}(M))$ where $\mathscr{D}(M) := \{P^M(\cdot |s,a) | s \in \Sc, a \in \Ac \}$ is the set of all possible one-step state distributions under the MDP $M$.

The reinforcement learning agent interacts with the MDP over episodes that begin at times $t_k = (k-1) \tau + 1$, $k=1,2,\ldots$.
% At each time $t$, the agent selects an action $a_t$, observes a scalar reward $r_t$, and then transitions to $s_{t+1}$.
% If an agent follows a policy $\mu$ then when in state $s$ at time $t$ during episode $k$, it selects an action $a_t=\mu(s, t - t_k)$.
Let $H_t = (s_1,a_1,r_1,\ldots,s_{t-1},a_{t-1},r_{t-1})$ denote the history of observations made \emph{prior} to time $t$.
A reinforcement learning algorithm is a deterministic sequence $\{\pi_k | k = 1, 2, \ldots\}$ of functions, each mapping $H_{t_k}$ to a probability distribution $\pi_{k}(H_{t_k})$ over policies which the agent will employ during the $k$th episode.
We define the regret incurred by a reinforcement learning algorithm $\pi$ up to time $T$ to be
$$\text{Regret}(T, \pi, M^*) := \sum_{k=1}^{\lceil T/\tau \rceil} \Delta_k,$$
where $\Delta_k$ denotes regret over the $k$th episode, defined with respect to the MDP $M^*$ by
$$\Delta_k := \int_{s \in \Sc} \rho(s) \left(V^{M^*}_{\mu^*, 1} - V^{M^{*}}_{\mu_k, 1}\right)(s) $$
with $\mu^* = \mu^{M^*}$ and $\mu_{k}\sim \pi_{k}(H_{t_k})$. Note that regret is not deterministic since it can depend on the random MDP $M^*$, the algorithm's internal random sampling and, through the history $H_{t_k}$, on previous random transitions and random rewards. We will assess and compare algorithm performance in terms of regret and its expectation.



%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Main results}
We now review the algorithm PSRL, an adaptation of Thompson sampling \cite{thompson1933} to reinforcement learning.
PSRL was first proposed by Strens \cite{strens2000bayesian} and later was shown to satisfy efficient regret bounds in finite MDPs \cite{osband2013more}.
The algorithm begins with a prior distribution over MDPs.
At the start of episode $k$, PSRL samples an MDP $M_k$ from the posterior.
PSRL then follows the policy $\mu_k = \mu^{M_k}$ which is optimal for this \emph{sampled} MDP during episode $k$.

\begin{algorithm}[H]
\caption{\protect\\ Posterior Sampling for Reinforcement Learning (PSRL)}
\label{alg: PS}
{\small
\begin{algorithmic}[1]
    \State \textbf{Input: }Prior distribution $\phi$ for $M^*$, t=1
    \For{episodes $k=1,2,..$}
    \State{sample $M_k \sim \phi(\cdot | H_t)$}
    \State{compute $\mu_k = \mu^{M_k}$}
	    \For{timesteps $j=1,..,\tau$}
	        \State{apply $a_t \sim \mu_k(s_t,j)$}
	        \State{observe $r_t$ and $s_{t+1}$}
	        \State{advance $t=t+1$}
	    \EndFor
	\EndFor
\end{algorithmic}
}
\end{algorithm}

To state our results we first introduce some notation.
For any set $\Xc$ and $\Yc \subseteq \Real^d$ for $d$ finite let $\Pc^{C,\sigma}_{\Xc,\Yc}$ be the family the distributions from $\Xc$ to $\Yc$ with mean $\|\cdot\|_2$-bounded in $[0,C]$ and additive $\sigma$-sub-Gaussian noise.
We let $N(\Fc,\alpha,\|\cdot\|_2)$ be the $\alpha$-covering number of $\Fc$ with respect to the $\|\cdot\|_2$-norm and write $n_\Fc = \log(8 N(\Fc,1/T^2,\|\cdot\|_2)T)$ for brevity.
Finally we  write $d_E(\Fc) = {\rm dim}_E(\Fc,T^{-1})$ for the eluder dimension of $\Fc$ at precision $T^{-1}$, a notion of dimension specialized to sequential measurements described in Section \ref{sec: eluder}.

Our main result, Theorem \ref{thm: main regret}, bounds the expected regret of PSRL at any time $T$.

\begin{theorem}[Expected regret for PSRL in parameterized MDPs]
\label{thm: main regret} \hspace{0.00000000000001mm} \newline
Fix a state space $\Sc$, action space $\Ac$, function families
$\Rc \subseteq \Pc^{C_\Rc,\sigma_\Rc}_{\Sc \times \Ac,\Real}$ and
$\Pc \subseteq \Pc^{C_\Pc,\sigma_\Pc}_{\Sc \times \Ac,\Sc}$ for any $C_\Rc, C_\Pc, \sigma_\Rc, \sigma_\Pc >0$.
Let $M^*$ be an MDP with state space $\Sc$, action space $\Ac$, rewards $R^* \in \Rc $ and transitions $P^* \in \Pc $.
If $\phi$ is the distribution of $M^*$ and $K^* = K^{M^*}$ is a global Lipschitz constant for the future value function as per \eqref{eq: future Lipschitz} then:
% {\small
% \begin{eqnarray}
% \label{eq: reg proof}
% 	\Exp[{\rm Regret}(T,\pi^{PS},M^*)] \le
% 	\bigg[ C_\Rc + C_\Pc \bigg] +
% 	\bigg[ 1 + \tau C_\Rc d_\Rc + 8\sqrt{d_\Rc(4C_\Rc + \sqrt{2\sigma_\Rc^2 \log(32T^3)})}
% 	+ 8\sqrt{2 \sigma_\Rc^2 n_\Rc d_\Rc T} \bigg] \nonumber \\
% 	& \hspace{-155mm} + \Exp[K^*]\left(1+\frac{1}{T-1}\right)\left( 1 + \tau C_\Pc d_\Pc + 8\sqrt{d_\Pc(4C_\Pc + \sqrt{2\sigma_\Pc^2 \log(32T^3)})}
% 	+ 8\sqrt{2 \sigma_\Pc^2 n_\Pc d_\Pc T} \right)
% \end{eqnarray}
% }
\begin{eqnarray}
\label{eq: reg proof}
    \Exp[{\rm Regret}(T,\pi^{PS},M^*)] \le \big[ C_\Rc + C_\Pc \big] + \tilde{D}(\Rc)
    + + \Exp[K^*]\left(1+\frac{1}{T-1}\right) \tilde{D}(\Pc)
\end{eqnarray}
Where for $\Fc$ equal to either $\Rc$ or $\Pc$ we will use the shorthand: \\
$\tilde{D}(\Fc) := 1 + \tau C_\Fc d_E(\Fc) + 8\sqrt{d_E(\Fc)(4C_\Fc + \sqrt{2\sigma_\Fc^2 \log(32T^3)})} + 8\sqrt{2 \sigma_\Fc^2 n_\Fc d_E(\Fc) T}$.
\end{theorem}
Theorem \ref{thm: main regret} is a general result that applies to almost all RL settings of interest.
In particular, we note that any bounded function is sub-Gaussian.
To clarify the assymptotics if this bound we use another classical measure of dimensionality.
\begin{mydef}
\label{def: kol}
The Kolmogorov dimension of a function class $\Fc$ is given by:
$$ {\rm dim}_K(\Fc) := \limsup_{\alpha \downarrow 0} \frac{\log(N(\Fc,\alpha,\|\cdot\|_2))}{\log(1/\alpha)} .$$
\end{mydef}
Using Definition \ref{def: kol} in Theorem \ref{thm: main regret} we can obtain our Corollary.
\begin{corollary}[Assymptotic regret bounds for PSRL in parameterized MDPs]
\label{cor: ass regret} \hspace{0.00000000000001mm} \newline
Under the assumptions of Theorem \ref{thm: main regret} and writing $d_K(\Fc) := {\rm dim}_K(\Fc)$:
\begin{equation}
	\Exp[{\rm Regret}(T,\pi^{PS},M^*)] = \tilde{O} \left( \ \sigma_\Rc \sqrt{d_K(\Rc) d_E(\Rc) T}
		+ \Exp[K^*] \sigma_\Pc \sqrt{d_K(\Pc) d_E(\Pc) T} \ \right)
\end{equation}
Where $\tilde{O}(\cdot)$ ignores terms logarithmic in $T$.
\end{corollary}

In Section \ref{sec: eluder} we provide bounds on the eluder dimension of several function classes.
These lead to explicit regret bounds in a number of important domains such as discrete MDPs, linear-quadratic control and even generalized linear systems.
In all of these cases the eluder dimension scales comparably with more traditional notions of dimensionality.
For clarity, we present bounds in the case of linear-quadratic control.

\begin{corollary}[Assymptotic regret bounds for PSRL in bounded linear quadratic systems]
\label{cor: LQR} \hspace{0.00000000000001mm} \newline
Let $M^*$ be an $n$-dimensional linear-quadratic system with $\sigma$-sub-Gaussian noise.
If the state is $\| \cdot \|_2$-bounded by $C$ and $\phi$ is the distribution of $M^*$, then:
\begin{equation}
	\Exp[{\rm Regret}(T,\pi^{PS},M^*)] = \tilde{O} \left( \sigma C \lambda_1 n^2 \sqrt{T} \ \right).
\end{equation}
Here $\lambda_1$ is the largest eigenvalue of the matrix $Q$ given as the solution of the Ricatti equations for the unconstrained optimal value function $V(s) = -s^T Q s$ \cite{bertsekas1995dynamic}.
\begin{proof}
We simply apply the results of for eluder dimension in Section \ref{sec: eluder} to Corollary \ref{cor: ass regret} and upper bound the Lipschitz constant of the constrained LQR by $2 C \lambda_1$, see Appendix \ref{app: Bounded LQR}.
\end{proof}
\end{corollary}

Algorithms based upon posterior sampling are intimately linked to those based upon optimism \cite{russo2013}.
In Appendix \ref{app: UCRL-Eluder} we outline an optimistic variant that would attain similar regret bounds but with high probility in a frequentist sense.
Unfortunately this algorithm remains computationally intractable even when presented with an approximate MDP planner.
Further, we believe that PSRL will generally be more statistically efficient than an optimistic variant with similar regret bounds since the algorithm is not affected by loose analysis \cite{osband2013more}.


%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Eluder dimension}
\label{sec: eluder}
To quantify the complexity of learning in a potentially infinite MDP, we extend the existing notion of eluder dimension for real-valued functions \cite{russo2013eluder} to vector-valued functions.
For any $\Gc \subseteq \Pc^{C,\sigma}_{\Xc,\Yc}$ we define the set of mean functions $\Fc = \Exp[\Gc] := \{f | f=\Exp[G] \text{ for } G \in \Gc \}$.
If we consider sequential observations $y_i \sim G^*(x_i)$ we can equivalently write them as $y_i = f^*(x_i) + \epsilon_i$ for some $f^*(x_i) = \Exp[y | y \sim G^*(x_i)]$ and $\epsilon_i$ zero mean noise.
Intuitively, the eluder dimension of $\Fc$ is the length $d$ of the longest possible sequence $x_1,..,x_d$ such that for all $i$, knowing the function values of $f(x_1),..,f(x_i)$ will not reveal $f(x_{i+1})$.

\begin{mydef}[$ (\mathcal{F},\epsilon)-dependence$]
\hspace{0.00000000000001mm} \newline
We will say that $x \in \mathcal{X}$ is $(\Fc,\epsilon)$-dependent on $\{x_1,...,x_n\} \subseteq \Xc $
$$ \iff \forall f,\tilde{f} \in \Fc, \ \ \sum_{i=1}^{n} \| f(x_i) - \tilde{f}(x_i) \|_2^2 \le \epsilon^2 \implies \| f(x) - \tilde{f}(x)\|_2 \le \epsilon.$$
$x \in \mathcal{X}$ is $(\epsilon,\mathcal{F})$-independent of $\{x_1,..,x_n\}$ iff it does not satisfy the definition for dependence.
\end{mydef}

\begin{mydef}[Eluder Dimension]
\label{def: Eluder} \hspace{0.00000000000001mm} \newline
The eluder dimension ${\rm dim}_E(\Fc,\epsilon)$ is the length of the longest possible sequence of elements in $\Xc$ such that for some $\epsilon' \ge \epsilon$ every element is $(\Fc,\epsilon')$-independent of its predecessors.
\end{mydef}

Traditional notions from supervised learning, such as the VC dimension, are not sufficient to characterize the complexity of reinforcement learning.
In fact, a family learnable in constant time for supervised learning may require arbitrarily long to learn to control well \cite{russo2013eluder}.
The eluder dimension mirrors the linear dimension for vector spaces, which is the length of the longest sequence such that each element is linearly independent of its predecessors, but allows for nonlinear and approximate dependencies.
We overload our notation for $\Gc \subseteq \Pc^{C,\sigma}_{\Xc,\Yc}$ and write ${\rm dim}_E(\Gc,\epsilon) := {\rm dim}_E(\Exp[\Gc],\epsilon)$, which should be clear from the context.



%--------------------------------------------------------------------------------------------------------
\subsection{Eluder dimension for specific function classes}
Theorem \ref{thm: main regret} gives regret bounds in terms of the eluder dimension, which is well-defined for any $\Fc, \epsilon$.
However, for any given $\Fc,\epsilon$ actually calculating the eluder dimension may take some additional analysis.
We now provide bounds on the eluder dimension for some common function classes in a similar approach to earlier work for real-valued functions \cite{russo2013}.
These proofs are available in Appendix \ref{app: eluder dims}.

\begin{prop}[Eluder dimension for finite $\mathcal{X}$]
\hspace{0.00000000000001mm} \newline
A counting argument shows that for $| \mathcal{X} | = X$ finite, any $\epsilon>0$ and any function class $\Fc$:
$$ {\rm dim}_E( \mathcal{F}, \epsilon) \le X $$
This bound is tight in the case of independent measurements.
\end{prop}

\begin{prop}[Eluder dimension for linear functions]
\label{prop: eluder lin}
\hspace{0.00000000000001mm} \newline
Let $\mathcal{F} = \{ f \ | f(x) = \theta \phi(x)  \text{ for } \theta \in \Real^{n \times p}, \phi \in \Real^p ,
\|\theta \|_2 \le C_\theta , \|\phi\|_2 \le C_\phi \}$
then $\forall \mathcal{X}$:
$$ {\rm dim}_E(\Fc, \epsilon) \le p(4n-1)\frac{e}{e-1} \log\left[ \left(1+\left( \frac{2C_\phi C_\theta}{\epsilon}\right)^2 \right)\left(4n-1\right) \right] + 1 = \tilde{O}(np) $$
\end{prop}

\begin{prop}[Eluder dimension for quadratic functions]
\hspace{0.00000000000001mm} \newline
Let $\mathcal{F} = \{ f \ | f(x) = \phi(x)^T \theta \phi(x)  \text{ for } \theta \in \Real^{p \times p}, \phi \in \Real^p ,
\|\theta \|_2 \le C_\theta , \|\phi\|_2 \le C_\phi \}$
then $\forall \Xc$:
$$ {\rm dim}_E(\Fc, \epsilon) \le p(4p-1)\frac{e}{e-1} \log\left[ \left(1+\left( \frac{2 p C_\phi^2 C_\theta}{\epsilon}\right)^2 \right)\left(4p-1\right) \right] + 1 = \tilde{O}(p^2). $$
\end{prop}

\begin{prop}[Eluder dimension for generalized linear functions]
\hspace{0.00000000000001mm} \newline
Let $g(\cdot)$ be a component-wise independent function on $\Real^n$ with derivative in each component bounded  $\in [\underline{h},\overline{h}]$ with $\underline{h}>0$.
Define $r = \frac{\overline{h}}{\underline{h}} > 1$ to be the condition number.
If $\mathcal{F} = \{ f \ | f(x) = g(\theta \phi(x))  \text{ for } \theta \in \Real^{n \times p}, \phi \in \Real^p ,
\|\theta \|_2 \le C_\theta , \|\phi\|_2 \le C_\phi \}$
then for any $\Xc$:
{\small
$${\rm dim}_E(\Fc, \epsilon) \le p \left(r^2(4n-2)+1\right)\frac{e}{e-1} \left(\log \left[\left(r^2(4n-2)+1 \right) \left(1+ \left(\frac{2C_\theta C_\phi}{\epsilon} \right)^2\right) \right] \right) + 1 = \tilde{O}(r^2 np)$$
}
\end{prop}

%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Confidence sets}
\label{sec: conf}
We now follow the standard argument that relates the regret of an optimistic or posterior sampling algorithm to the construction of confidence sets \cite{jaksch2010near,osband2013more}.
We will use the eluder dimension build confidence sets for the reward and transition which contain the true functions with high probability and then bound the regret of our algorithm by the maximum deviation within the confidence sets.
For observations from $f^* \in \Fc$ we will center the sets around the least squares estimate $\hat{f}_t^{LS} \in \arg \min_{f \in \Fc} L_{2,t}(f)$ where $L_{2,t}(f) := \sum_{i=1}^{t-1} \|f(x_t) - y_t \|^2_2$ is the cumulative squared prediciton error.
The confidence sets are defined $\Fc_t = \Fc_t(\beta_t) := \{ f \in \Fc | \| f-\hat{f}_t^{LS} \|_{2,E_t} \le \sqrt{\beta_t} \}$ where $\beta_t$ controls the growth of the confidence set and the empirical 2-norm is defined $\|g\|_{2,E_t}^2 := \sum_{i=1}^{t-1} \|g(x_i)\|_2^2$.

For $\Fc \subseteq \Pc^{C,\sigma}_{\Xc,\Yc}$, we define the distinguished control parameter:
\begin{equation}
\label{eq: beta star}
	\beta^*_t(\Fc,\delta,\alpha) := 8 \sigma^2 \log(N(\Fc,\alpha,\|\cdot\|_2)/\delta) +
	2 \alpha t \left(8C + \sqrt{8\sigma^2 \log(4t^2/\delta)}) \right)
\end{equation}
This leads to confidence sets which contain the true function with high probability.

\begin{prop}[Confidence sets with high probability]
\label{prop: conf sets} \hspace{0.00000000000001mm} \newline
For all $\delta>0$ and $\alpha >0$ and the confidence sets $\Fc_t = \Fc_t(\beta^*_t(\Fc,\delta,\alpha))$ for all $t \in \Nat$ then:
$$\Prob \left( f^* \in \bigcap_{t=1}^\infty \Fc_t \right) \ge 1-2\delta $$
\begin{proof}
We combine standard martingale concentrations with a discretization scheme.
The argument is essentially the same as Proposition 6 in \cite{russo2013}, but extends statements about $\Real$ to vector-valued functions.
A full derivation is available in the Appendix \ref{app: conf sets}.
\end{proof}
\end{prop}

\subsection{Bounding the sum of set widths}
We now bound the deviation from $f^*$ by the maximum deviation within the confidence set.
% Since the true function $f^*$ lies within the confidence set with high probability, so will any $\tilde{f}$ drawn from posterior sampling, since they are equal in distribution.
% The optimistic variant will explicitly restrict itself to $\Fc_t$ so that it makes sense for us to focus our analysis where both the true and imagined $f^*$ both lie within $\Fc_t$.

\begin{mydef}[Set widths]
\hspace{0.00000000000001mm} \newline
For any set of functions $\Fc$ we define the width of the set at $x$ to be the maximum L2 deviation between any two members of $\Fc$ evaluated at $x$.
$$ w_\Fc(x) := \sup_{\overline{f},\underline{f} \in \Fc} \| \overline{f}(x) - \underline{f}(x)\|_2$$
\end{mydef}

We can bound for the number of large widths in terms of the eluder dimension.

\begin{lemma}[Bounding the number of large widths]
\hspace{0.00000000000001mm} \newline
\label{lem: big widths}
If $\{ \beta_t >0 \big| t \in \Nat \}$ is a nondecreasing sequence with $\Fc_t = \Fc_t(\beta_t)$ then
$$ \sum_{k=1}^m \sum_{i=1}^\tau \Ind \{w_{\Fc_{t_k}}(x_{t_k+i}) > \epsilon \} \le
	\left( \frac{4\beta_T}{\epsilon^2}+ \tau \right) {\rm dim}_E(\Fc,\epsilon) $$

\begin{proof}
This result follows from proposition 8 in \cite{russo2013} but with a small adjustment to account for episodes. A full proof is given in Appendix \ref{app: large widths}.
\end{proof}
\end{lemma}

We now use Lemma \ref{lem: big widths} to control the cumulative deviation through time.
\begin{prop}[Bounding the sum of widths]
\hspace{0.00000000000001mm} \newline
\label{prop: widths}
If $\{ \beta_t >0 \big| t \in \Nat \}$ is nondecreasing with $\Fc_t = \Fc_t(\beta_t)$ and $\|f\|_2 \le C$ for all $f \in \Fc$ then:
\begin{equation}
	\sum_{k=1}^m \sum_{i=1}^\tau w_{\Fc_{t_k}}(x_{t_k+i}) \le
	1 + \tau C {\rm dim}_E(\Fc,T^{-1}) + 4\sqrt{\beta_T {\rm dim}_E(\Fc,T^{-1}) T}
\end{equation}

\begin{proof}
Once again we follow the analysis of Russo \cite{russo2013} and strealine notation by letting $w_t = w_{\Fc_{t_k}}(x_{t_k+i})$ abd $d = {\rm dim}_E(\Fc,T^{-1})$.
Reordering the sequence $(w_1,..,w_T) \rightarrow (w_{i_1},..,w_{i_T})$ such that $w_{i_1}\ge..\ge w_{i_T}$
we have that:
$$ \sum_{k=1}^m \sum_{i=1}^\tau w_{\mathcal{F}_{t_k}}(x_{t_k+i})  = \sum_{t=1}^T w_{i_t} \le 1 + \sum_{i=1}^T w_{i_t} \Ind \{ w_{i_t} \ge T^{-1} \} $$.

By the reordering we know that $w_{i_t} > \epsilon$ means that $\sum_{k=1}^m \sum_{i=1}^\tau \Ind \{w_{\Fc_{t_k}}(x_{t_k+i}) > \epsilon \} \ge t $.
From Lemma \ref{lem: big widths}, $\epsilon \le \sqrt{\frac{4 \beta_T d}{t - \tau d}}$.
So that if $w_{i_t} > T^{-1}$ then $w_{i_t} \le \min \{ C , \sqrt{\frac{4 \beta_T d}{t - \tau d}} \}$. Therefore,
$$\sum_{i=1}^T w_{i_t} \Ind \{ w_{i_t} \ge T^{-1} \} \le \tau C d + \sum_{t=\tau d +1}^T \sqrt{\frac{4 \beta_T d}{t - \tau d}} \le
\tau C d + 2 \sqrt{\beta_T} \int_0^T \sqrt{ \frac{d}{t} } \,dt \le \tau C d + 4 \sqrt{\beta_T d T}$$

\end{proof}

\end{prop}


%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Analysis}
We will now show reproduce the decomposition of expected regret in terms of the Bellman error \cite{osband2013more}.
From here, we will apply the confidence set results from Section \ref{sec: conf} to obtain our regret bounds.
We streamline our discussion of $P^{M}, R^{M}, V^{M}_{\mu,i}, U^{M}_{i}$ and $\Tc^M_\mu$ by simply writing $*$ in place of $M^*$ or $\mu^*$ and $k$ in place of $M_k$ or $\mu_k$ where appropriate; for example $V^*_{k,i} := V^{M^*}_{\tilde{\mu}_k,i}$.

The first step in our ananlysis breaks down the regret by adding and subtracting the \emph{imagined} optimal reward of $\mu_k$ under the MDP $M_k$.
\begin{equation}
	\Delta_k = \left( V^*_{*,1} - V^*_{k,1} \right)(s_0)
	= \left( V^*_{*,1} - V^k_{k,1} \right)(s_0) + \left( V^k_{k,1} - V^*_{k,1} \right)(s_0)
\end{equation}
Here $s_0$ is a distinguished initial state, but moving to general $\rho(s)$ poses no real challenge.
Algorithms based upon optimism bound $( V^*_{*,1} - V^k_{k,1} ) \le 0$ with high probability.
For PSRL we use Lemma \ref{lem: ps} and the tower property to see that this is zero in expectation.
\begin{lemma}[Posterior sampling]
\label{lem: ps}
\hspace{0.00000000000001mm} \newline
If $\phi$ is the distribution of $M^*$ then, for any $\sigma(H_{t_k})$-measurable function $g$,
\begin{equation}
\label{eq: ps}
	\Exp [g(M^*) | H_{t_k} ] = \Exp [g(M_k) | H_{t_k} ]
\end{equation}
\end{lemma}

We introduce the Bellman operator $\mathcal{T}_{\mu}^{M}$, which for any MDP $M = (\Sc, \Ac, R^M, P^M, \tau, \rho)$, stationary policy $\mu:\Sc \rightarrow \Ac$ and value function $V:\Sc \rightarrow \mathds{R}$, is defined by
$$\mathcal{T}_{\mu}^{M} V(s) := \overline{r}^{M} (s, \mu(s)) + \int_{s' \in \Sc} P^{M}(s' | s, \mu(s)) V(s').$$
This returns the expected value of state $s$ where we follow the policy $\mu$ under the laws of $M$, for one time step.
The following lemma gives a concise form for the dynamic programming paradigm in terms of the Bellman operator.

\begin{lemma}[Dynamic programming equation]
\label{lem: DPl} \hspace{0.000000001mm} \newline
For any MDP $M = (\Sc, \Ac, R^M, P^M, \tau, \rho)$ and policy $\mu:\Sc \times \{1,\ldots,\tau\} \rightarrow \Ac$, the value functions $V^M_\mu$ satisfy
\begin{equation}\label{eq: DP}
V_{\mu,i}^{M} = \mathcal{T}_{\mu(\cdot,i)}^M V_{\mu,i+1}^M
\end{equation}
for $i=1\dots \tau$, with $V_{\mu,\tau+1}^{M} := 0$.
\end{lemma}

Through repeated application of the dynamic programming operator and taking expectation of martingale differences we can mirror earlier analysis \cite{osband2013more} to equate expected regret with the cumulative Bellman error:
\begin{equation}
\label{eq: reg bellman}
	\Exp [ \Delta_k ] = \sum_{i=1}^\tau (\Tc^k_{k,i}-\Tc^*_{k,i})V^k_{k,i+1}(s_{t_k+i})
\end{equation}


\subsection{Lipschitz continuity}
\label{sec: lipschitz}
Efficient regret bounds for MDPs with an infinite number of states and actions require some regularity assumption.
One natural notion is that nearby states might have similar optimal values, or that the optimal value function function might be Lipschitz.
Unfortunately, any discontinuous reward function will usually lead to discontious values functions so that this assumption is violated in many settings of interest.
However, we only require that the \emph{future} value is Lipschitz in the sense of equation \eqref{eq: future Lipschitz}.
This will will be satisfied whenever the underlying value function is Lipschitz, but is a strictly weaker requirement since the system noise helps to smooth future values.

Since $\Pc$ has $\sigma_P$-sub-Gaussian noise we write $s_{t+1} = \overline{p}^M(s_t,a_t)+\epsilon^P_t$ in the natural way.
We now use equation \eqref{eq: reg bellman} to reduce regret to a sum of set widths.
To reduce clutter and more closely follow the notation of Section \ref{sec: eluder} we will write $x_{k,i}=(s_{t_k+i},a_{t_k+i})$.
% where $a_{t_k+i} \sim \mu^{M_k}(s_{t_k+i})$.
\begin{eqnarray}
	\Exp [ \Delta_k ] &\le& \Exp \left[ \sum_{i=1}^\tau \left\{  \overline{r}^k(x_{k,i}) - \overline{r}^*(x_{k,i})
	+  U^k_{i}(P^k(x_{k,i})) - U^k_{i}(P^*(x_{k,i})) \right\} \right] \nonumber \\
	&\le& \Exp\left[ \sum_{i=1}^\tau \left\{ | \overline{r}^k(x_{k,i}) - \overline{r}^*(x_{k,i})|
	+ K^k \|\overline{p}^k(x_{k,i}) - \overline{p}^*(x_{k,i}) \|_2 \right\}\right]
\end{eqnarray}
Where $K^k$ is a global Lipschitz constant for the future value function of $M_k$ as per \eqref{eq: future Lipschitz}.

We now use the results from Sections \ref{sec: eluder} and \ref{sec: conf} to form the corresponding confidence sets $\Rc_k := \Rc_{t_k}(\beta^*(\Rc,\delta,\alpha))$ and $\Pc_k := \Pc_{t_k}(\beta^*(\Pc,\delta,\alpha))$ for the reward and transition functions respectively.
Let $A = \{R^*, R_k \in \Rc_k \ \forall k \}$ and $B = \{P^*,P_k \in \Pc_k \ \forall k \}$ and condition upon these events to give:
\begin{eqnarray}
\label{eq: reg widths}
	\Exp[{\rm Regret}(T,\pi^{PS},M^*)] &\le&
	\Exp\left[ \sum_{k=1}^m \sum_{i=1}^\tau
		\left\{ | \overline{r}^k(x_{k,i}) - \overline{r}^*(x_{k,i})|
		+ K^k \|\overline{p}^k(x_{k,i}) - \overline{p}^*(x_{k,i}) \|_2 \right\}\right] \nonumber \\
	&& \hspace{-10mm} \le \sum_{k=1}^m \sum_{i=1}^\tau \left\{ w_{\Rc_k}(x_{k,i}) +
		 \Exp[K^k|A,B] w_{\Pc_k}(x_{k,i}) + 8 \delta (C_\Rc + C_\Pc) \right\}
\end{eqnarray}
The posterior sampling lemma ensures that $\Exp[K^k] = \Exp[K^*]$ so that
$\Exp[K^k|A,B] \le \frac{\Exp[K^*]}{\Prob(A,B)} \le \frac{\Exp[K^*]}{1-8\delta}$
by a union bound on $\{A^c \cup B^c\}$.
We fix $\delta = 1/8T$ to see that:
{\small
$$ \Exp[{\rm Regret}(T,\pi^{PS},M^*)] \le (C_\Rc + C_\Pc) +
	\sum_{k=1}^m \sum_{i=1}^\tau w_{\Rc_k}(x_{k,i})
	+ \Exp[K^*] \left(1+\frac{1}{T-1} \right)\sum_{k=1}^m \sum_{i=1}^\tau w_{\Pc_t}(x_{k,i})  $$
}
We now use equation \eqref{eq: beta star} together with Proposition \ref{prop: widths} to obtain our regret bounds.
For ease of notation we will write $d_E(\Rc) = {\rm dim}_E(\Rc,T^{-1})$ and $d_E(\Pc) = {\rm dim}_E(\Pc,T^{-1})$.
\begin{eqnarray}
	\Exp[{\rm Regret}(T,\pi^{PS},M^*)] &\le&
	2 + (C_\Rc + C_\Pc) + \tau(C_\Rc d_E(\Rc)+ C_\Pc d_E(\Pc)) + \nonumber \\
	&& \  4 \sqrt{\beta_T^*(\Rc,1/8T,\alpha) d_E(\Rc) T} + 4 \sqrt{\beta_T^*(\Pc,1/8T,\alpha) d_E(\Pc) T}
\end{eqnarray}
We let $\alpha = 1/T^2$ and write $n_\Fc = \log(8 N(\Fc,1/T^2,\|\cdot\|_2)T)$ for $\Rc$ and $\Pc$ to complete our proof of Theorem \ref{thm: main regret}:
\begin{eqnarray}
\label{eq: reg proof}
    \Exp[{\rm Regret}(T,\pi^{PS},M^*)] \le \big[ C_\Rc + C_\Pc \big] + \tilde{D}(\Rc)
     + \Exp[K^*]\left(1+\frac{1}{T-1}\right) \tilde{D}(\Pc)
\end{eqnarray}
Where $\tilde{D}(\Fc)$ is shorthand for $ 1 + \tau C_\Fc d_E(\Fc) + 8\sqrt{d_E(\Fc)(4C_\Fc + \sqrt{2\sigma_\Fc^2 \log(32T^3)})} + 8\sqrt{2 \sigma_\Fc^2 n_\Fc d_E(\Fc) T}$.
The first term $[C_\Rc + C_\Pc]$ bounds the contribution from missed confidence sets.
The cost of learning the reward function $R^*$ is bounded by $\tilde{D}(\Rc)$.
In most problems the remaining contribution bounding transitions and lost future value will be dominant.
Corollary \ref{cor: ass regret} follows from the Definition \ref{def: kol} together with $n_\Rc$ and $n_\Pc$.


%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Conclusion}
We present a new analysis of \emph{posterior sampling for reinforcement learning} that leads to a general regret bound in terms of the dimensionality, rather than the cardinality, of the underlying MDP.
These are the first regret bounds for reinforcement learning in such a general setting and provide new state of the art guarantees when specialized to several important problem settings.
That said, there are a few clear shortcomings which we do not address in the paper.
First, we assume that it is possible to draw samples from the posterior distribution exactly and in some cases this may require extensive computational effort.
Second, we wonder whether it is possible to extend our analysis to learning in MDPs without episodic resets.
Finally, there is a fundamental hurdle to model-based reinforcement learning that planning for the optimal policy even in a \emph{known} MDP may be intractable.
We assume access to an approximate MDP planner, but this will generally require lengthy computations.
We would like to examine whether similar bounds are attainable in model-free learning \cite{van2014generalization}, which may obviate complicated MDP planning, and examine the computational and statistical efficiency tradeoffs between these methods.

\subsubsection*{Acknowledgments}
Osband is supported by Stanford Graduate Fellowships courtesy of PACCAR inc.
This work was supported in part by Award CMMI-0968707 from the National Science Foundation.


%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\newpage
\small{
\bibliography{referenceInformation.bib}
\bibliographystyle{unsrt}
}
\newpage




%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\appendix

\section{Confidence sets with high probability}
\label{app: conf sets}
In this appendix we will build up to a proof of Proposition \ref{prop: conf sets}, that the confidence sets defined by $\beta^*$ in equation \ref{eq: beta star} hold with high probability.
We begin with some elementary results from martingale theory.

\begin{lemma}[Exponential Martingale]
\hspace{0.000000001mm} \newline
Let $Z_i \in L^1$ be real-calued random variables adapted to $\mathcal{H}_i$.
We define the conditional mean $\mu_i = \Exp[ Z_i | \mathcal{H}_{i-1} ] $ and conditional cumulant generating function $\psi_i(\lambda) = \log \Exp [ \exp \left(\lambda ( Z_i -\mu_i)\right) | \mathcal{H}_{i-1} ] $, then
$$ M_n ( \lambda ) = \exp \left( \sum_1^n \lambda (Z_i -\mu_i) - \psi_i(\lambda) \right) $$
is a martingale with $\Exp[M_n(\lambda)] = 1$.
\end{lemma}

\begin{lemma}[Concentration Guarantee]
\label{lem: mg conc} \hspace{0.000000001mm} \newline
For $Z_i$ adapted real $L^1$ random variables adapted to $\mathcal{H}_i$. We define the conditional mean $\mu_i = \Exp[ Z_i | \mathcal{H}_{i-1} ] $ and conditional cumulant generating function $\psi_i(\lambda) = \log \Exp [ \exp \left(\lambda ( Z_i -\mu_i)\right) | \mathcal{H}_{i-1} ] $.
$$ \Prob \left( \bigcup_{n=1}^\infty \{ \sum_1^n \lambda (Z_i -\mu_i) - \psi_i(\lambda) \ge x\} \right) \le e^{-x}$$
\end{lemma}

Both of these lemmas are available in earlier discussion for real-valued variables \cite{russo2013}.
We now specialize our discussion to the vector space $\Yc \subseteq \Real^d$ where the inner product $<y,y> = \|y \|_2^2$.
To simplify notation we will write $f^*_t := f^*(x_t)$ and $f_t = f(x_t)$ for arbitrary $f\in \Fc$.
We now define
\begin{eqnarray*}
	Z_t &=& \|f_t^* - y_t \|_2 - \| f_t - y_t \|_2 \\
	&=& <f_t^* - y_t, f_t^* - y_t> - <f_t - y_t, f_t - y_t, f_t - y_t> \\
	&=& -<f_t - f_t^*, f_t - f_t^*> + 2<f_t - f_t^*, y_t-f_t^*> \\
	&=& - \|f_t - f_t^* \|_2 + 2<f_t - f_t^*, \epsilon_t>
\end{eqnarray*}
so that clearly $\mu_t = - \|f_t - f_t^* \|_2$.
Now since we have said that the noise is $\sigma$-sub-Gaussian,
$ \Exp [ \exp \left( < \phi, \epsilon > \right) ] \le \exp \left( \frac{ \| \phi \|_2^2 \sigma^2}{2} \right)
\text{ } \forall \phi \in \mathcal{Y}$.
From here we can deduce that:
\begin{eqnarray*}
	\psi_t(\lambda) &=& \log \Exp [ \exp \left(\lambda ( Z_t -\mu_t)\right) | \mathcal{H}_{t-1} ]  \\
	&=& \log \Exp[ \exp (2 \lambda <f_t - f_t^*, \epsilon_t>)] \\
	&\le& \frac{\|2 \lambda (f_t - f_t^*) \|_2^2 \sigma^2}{2}.
\end{eqnarray*}

We now write $\sum_{i=1}^{t-1} Z_i = L_{2,t}(f^*) - L_{2,t}(f)$ according to our earlier definition of $L_{2,t}$.
We can apply Lemma \ref{lem: mg conc} with $\lambda = 1/{4\sigma^2}$, $x=log(1/\delta)$ to obtain:
$$ \Prob \{ \left( L_{2,t}(f) \ge L_{2,t}(f^*) + \frac{1}{2} \| f- f^*\|_{2,E_t} - 4\sigma^2\log(1/\delta) \right) \text{ } \forall t \} \ge 1-\delta$$
substituting $f = \hat{f}$ to be the least squares solution which minimizes $L_{2,t}(f)$ we can remove $L_{2,t}(\hat{f}) - L_{2,t}(f^*) \le 0$.
From here we use an $\alpha$-cover discretization argument to complete the proof of Proposition \ref{prop: conf sets}.

Let $\mathcal{F}^\alpha \subset \mathcal{F}$ be an $\alpha$-2 cover of $\mathcal{F}$
such that $\forall f \in \mathcal{F}$ there is some $ \| f^\alpha - f \|_2 \le \alpha$.
We can use a union bound on $\mathcal{F}^\alpha$ so that $\forall f \in \mathcal{F}$:
\begin{eqnarray}
\label{eq: L err bounds}
	L_{2,t}(f) - L_{2,t}(f^*) \ge \frac{1}{2} \|f-f^*\|_{2,E_t} - 4\sigma^2\log(N(\mathcal{F},\alpha,\|\cdot\|_2)/\delta) + DE(\alpha) \\
	\text{For } DE(\alpha) = \min_{f^\alpha \in \Fc^\alpha} \left\{ \frac{1}{2} \|f^\alpha-f^*\|_{2,E_t}^2 -
	\frac{1}{2} \| f-f^* \|_{2,E_t}^2 + L_{2,t}(f) - L_{2,t}(f^\alpha) \right\} \nonumber
\end{eqnarray}
We will now seek to bound this discretization error with high probability.

\begin{lemma}[Bounding discretization error]
\label{lem: disc err} \hspace{0.000000001mm} \newline
If $\| f^\alpha(x) - f(x) \|_2 \le \alpha$ for all $x \in \Xc$ then with probability at least $1-\delta$:
$$DE(\alpha) \le \alpha t \left[8C + \sqrt{8\sigma^2\log(4t^2/\delta)} \right] $$
\begin{proof}
For non-trivial bounds we will consider the case of $\alpha \le C$ and note that via Cauchy-Schwarz:
$$ \|f^\alpha(x) \|_2^2 - \|f(x)\|_2^2 \le \max_{\|y\|_2\le \alpha} \|f(x)+y\|_2^2 - \|f\|_2^2 \le 2C\alpha + \alpha^2.$$
From here we can say that
\begin{eqnarray*}
	\|f^\alpha(x) - f^*(x) \|_2^2 - \|f(x)-f^*(x)\|_2^2 = \|f^\alpha(x)\|_2^2 - \|f(x)\|_2^2 + 2<f^*(x),f(x)-f^\alpha(x)>
		\le 4C\alpha \\
	\|y - f(x)\|_2^2 - \|y-f^\alpha(x)\|_2^2 = 2<y,f^\alpha(x)-f(x)> + \|f(x)\|_2^2 - \|f^\alpha(x)\|_2^2
		\le 2\alpha |y| + 2C \alpha + \alpha^2
\end{eqnarray*}
Summing these expressions over time $i=1,..,t-1$ and using sub-gaussian high probability bounds on $|y|$ gives our desired result.
\end{proof}
\end{lemma}

Finally we apply Lemma \ref{lem: disc err} to equation \ref{eq: L err bounds} and use the fact that $\hat{f}^{LS}_t$ is the $L_{2,t}$ minimizer to obtain the result that with probability at least $1-2\delta$:
$$ \| \hat{f}^{LS}_t - f^* \|_{2,E_t} \le \sqrt{\beta^*_t(\Fc,\alpha,\delta) }$$
Which is our desired result.


%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Bounding the number of large widths}
\label{app: large widths}

\begin{lemma2}[Bounding the number of large widths]
\hspace{0.00000000000001mm} \newline
If $\{ \beta_t >0 \big| t \in \Nat \}$ is a nondecreasing sequence with $\Fc_t = \Fc_t(\beta_t)$ then
$$ \sum_{k=1}^m \sum_{i=1}^\tau \Ind \{w_{\Fc_{t_k}}(x_{t_k+i}) > \epsilon \} \le
	\left( \frac{4\beta_T}{\epsilon^2}+ \tau \right) {\rm dim}_E(\Fc,\epsilon) $$

\begin{proof}
We first imagine that $w_{\Fc_t}(x_t) > \epsilon$ and is $\epsilon$-dependent on $K$ disjoint subsequences of $x_1,..,x_{t-1}$.
If $x_t$ is $\epsilon$-dependent on $K$ disjoint subsequences then there exist $\|\overline{f} - \underline{f} \|_{2,E_t} > K \epsilon^2$. By the triangle inequality $\|\overline{f} - \underline{f} \|_{2,E_t} \le 2\sqrt{\beta_t} \le 2\sqrt{\beta_T}$ so that $K < 4\beta_T / \epsilon^2$.

In the case without episodic delay, Russo went on to show that in any sequence of length $l$ there is some element which is $\epsilon$-dependent on at least $\frac{l}{{\rm dim}_E(\Fc,\epsilon)}-1$ disjoint subsequences \cite{russo2013}.
Our analysis follows similarly, but we may lose up to $\tau-1$ proper subsequences due to the delay in updating the episode.
This means that we can only say that $K \ge \frac{l}{{\rm dim}_E(\Fc,\epsilon)}-\tau$.
Considering the subsequence $w_{\Fc_{t_k}}(x_{t_k+i}) > \epsilon$ we see that $l \le \left( \frac{4\beta_T}{\epsilon^2}+ \tau \right) {\rm dim}_E(\Fc,\epsilon)$ as required.
\end{proof}
\end{lemma2}

%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\section{Eluder dimension for specific function classes}
\label{app: eluder dims}
In this section of the appendix we will provide bounds upon the eluder dimension for some canonical function classes.
Recalling Definition \ref{def: Eluder}, ${\rm dim}_E(\Fc,\epsilon)$ is the length $d$ of the longest sequence $x_1,..,x_d$ such that for some $\epsilon' \ge \epsilon$:
\begin{equation}
\label{eq: w_k}
	w_k = \sup \left\{ \|(\overline{f} - \underline{f}) (x_k)\|_2 \ \bigg| \  \|\overline{f}-\underline{f}\|_{2,E_t} \le \epsilon' \right\}
	> \epsilon'
\end{equation}
for each $k\le d$.
\subsection{Finite domain $\Xc$}
Any $x \in \Xc$ is $\epsilon$-dependent upon itself for all $\epsilon>0$.
Therefore for all $\epsilon>0$ the eluder dimension of $\Fc$ is bounded by $|\Xc|$.

\subsection{Linear functions $f(x) = \theta \phi(x)$}
Let $\mathcal{F} = \{ f \ | f(x) = \theta \phi(x)  \text{ for } \theta \in \Real^{n \times p}, \phi \in \Real^p ,
\|\theta \|_2 \le C_\theta , \|\phi\|_2 \le C_\phi \}$.
To simplify our notation we will write $\phi_k = \phi(x_k)$ and $\theta = \theta_1 - \theta_2$.
From here, we may manipulate the expression
$$ \|\theta \phi \|_2^2 = \phi_k^T \theta^T\theta \phi_k = Tr(\phi_k^T \theta^T\theta \phi_k) = Tr(\theta \phi_k \phi_k^T \theta)$$
$$ \implies w_k = \sup_{\theta} \{ \|\theta \phi_k \|_2 \ \big| Tr(\theta \Phi_k \theta^T) \le \epsilon^2 \}
	\text{ where } \Phi_k := \sum_{i=1}^{k-1} \phi_i \phi_i^T $$
We next require a lemma which gives an upper bound for trace constrained optimizations.


\begin{lemma}[Bounding norms under trace constraints]
\label{lem: norms trace} \hspace{0.000000001mm} \newline
Let $\theta \in \Real^{n \times p}, \phi \in \Real^p$ and $V \in \Real_{++}^{p \times p}$, the set of positive definite $p\times p$ matrices, then:
$$ W^2  = \max_\theta \|\theta \phi \|_2^2  \text{ subject to } Tr(\theta V \theta^T) \le \epsilon^2 $$
is bounded above by $W^2 \le (2n-1) \epsilon^2 \| \phi \|^2_{V^{-1}}$ where $\| \phi \|_A^2 := \phi^T A \phi$.

\begin{proof}
We first note that $ \|\theta \phi \|_2^2 = Tr(\theta \phi \phi^T \theta^T) = \sum_1^n (\theta \phi)_i^2 \le \left( \sum_1^n (\theta \phi)_i \right)^2 $ by Jensen's inequality.
We define $\tilde{\Phi} \in \Real^{n \times p}$ such that each row of  $\tilde{\Phi} = \phi^T $. Then this inequality can be expressed as:
$$ W^2 = Tr(\theta \phi \phi^T \theta^T) \le Sum ( \theta \otimes \tilde{\Phi} )^2 $$
Where  $A\otimes B = C \text{ for } C_{ij} = A_{ij}B_{ij} \text{ and }Sum(C) := \sum_{i,j}C_{ij} $
We can now obtain an upper bound for our original problem through this convex relaxation:
$$ \max_\theta Sum ( \theta \otimes \tilde{\Phi} ) \text{ subject to } Tr(\theta V \theta^T) \le \epsilon^2 $$

We can now form the lagrangian $\mathcal{L}(\theta, \lambda) = -Sum ( \theta \otimes \tilde{\Phi} ) + \lambda ( Tr(\theta V \theta^T) - \epsilon^2)$.
Solving for first order optimality $\triangledown_\theta \mathcal{L} = 0 \implies \theta^* = \frac{1}{2\lambda} \tilde{\Phi} V^{-1}$.
From here we form the dual objective
$$g(\lambda) = -Sum (\frac{1}{2\lambda}\tilde{\Phi}V^{-1} \otimes \tilde{\Phi}) +
	Tr(\frac{1}{4\lambda}\tilde{\Phi}V^{-1}\tilde{\Phi}^T) - \lambda \epsilon^2$$
Here we solve for the dual-optimal $\lambda^*$
$\triangledown_\lambda g = 0 \implies  \frac{1}{2{\lambda^*}}^2 Sum (\frac{1}{2\lambda}\tilde{\Phi}V^{-1} \otimes \tilde{\Phi})
	-  \frac{1}{4{\lambda^*}}^2 Tr(\frac{1}{4\lambda}\tilde{\Phi}V^{-1}\tilde{\Phi}^T) = \epsilon^2$.
From the definition of $\tilde{\Phi}$,
$Sum ( \tilde{\Phi}V^{-1} \otimes \tilde{\Phi} ) = n \phi^T V^{-1} \phi$ and $Tr(\tilde{\Phi}V^{-1}\tilde{\Phi}^T) = \phi^T V^{-1}\phi$.
From this we can simplify our expression to conclude:

\begin{eqnarray*}
	\frac{n}{2{\lambda^*}^2} \phi^T V^{-1} \phi - \frac{1}{4{\lambda^*}^2} \phi^T V^{-1} \phi = \epsilon^2 \implies {\lambda^*}
	= \sqrt{ \frac{(n-1/2)}{2\epsilon^2} } \| \phi \|_{V^{-1}} \\
	\implies g(\lambda^*) = -\frac{n}{2\lambda^*} \|\phi \|_{V^{-1}}^2 + \frac{1}{4\lambda^*} \|\phi \|_{V^{-1}}^2 - \lambda^* \epsilon \\
	\text{ strong duality } \implies f(\theta^*) = g(\lambda^*) = \sqrt{2n-1} \epsilon \| \phi \|_{V^{-1}}
\end{eqnarray*}
From here we conclude that the optimal value of $W^2 \le f(\theta^*)^2 \le (2n-1) \epsilon^2 \|\phi\|_{V^{-1}}^2$.
\end{proof}
\end{lemma}

Using this lemma, we will be able to address the eluder dimension for linear functions.
Using the definition of $w_k$ from equation \ref{eq: w_k} together with $\Phi_k$ we may rewrite:
$$ w_k = \max_\theta \{ \sqrt{Tr(\theta \phi_k \phi_k^T \theta)} \ \big| \ Tr(\theta \Phi_k \theta^T) \le \epsilon^2\}.$$
Let $V_k := \Phi_k + \left(\frac{\epsilon}{2C_\theta}\right)^2 I $ so that $Tr(\theta \Phi_k \theta^T) \le \epsilon^2 \implies Tr(\theta V_k \theta^T) \le 2\epsilon^2$ through a triangle inequality.
Now applying Lemma \ref{lem: norms trace} we can say that $w_k \le \epsilon \sqrt{4n-2} \|\phi_k\|_{V_k^{-1}}$.
This means that if $w_k \ge \epsilon$ then $\|\phi_k\|_{V_k^{-1}}^2 > \frac{1}{4n-2} >0$.

We now imagine that $w_i \ge \epsilon$ for each $i<k$.
Then since $V_k = V_{k-1} + \phi_k \phi_k^T$ we can use the Matrix Determinant together with the above observation to say that:
\begin{equation}
\label{eq: det lower}
	det(V_k) = det(V_{k-1})(1+ \phi_k^T V_K^{-1} \phi_k) \ge det(V_{k-1})\left(1 + \frac{1}{4n-2}\right) \ge ..
		\ge \lambda^{p} \left( 1 + \frac{1}{4n-2} \right)^{k-1}
\end{equation}
for $\lambda := \left(\frac{\epsilon}{2C_\theta}\right)^2$.
To get an upper bound on the determinant we note that $det(V_k)$ is maximized when all eigenvalues are equal or equivalently:
\begin{equation}
\label{eq: det upper}
det(V_k) \le \left( \frac{Tr(V_k)}{p}\right)^p \le \left(\frac{C_\phi^2(k-1)}{p} + \lambda \right)^p
\end{equation}

Now using equations \ref{eq: det lower} and \ref{eq: det upper} together we see that $k$ must satistfy the inequality
$ \left( 1 + \frac{1}{4n-2} \right)^{(k-1)/p} \le \frac{C_\phi^2(k-1)}{\lambda  p} + 1$.
We now write $\zeta_0 = \frac{1}{4n-2}$ and $\alpha_0 = \frac{C_\phi^2}{\lambda} = \left( \frac{2C_\phi C_\theta}{\epsilon}\right)^2$ so that we can epress this as:
$$ (1 + \zeta_0)^{\frac{k-1}{p}} \le \alpha_0 \frac{k-1}{p} +1 $$
We now use the result that $B(x,\alpha) = \max\{B  \ \big| \ (1+x)^B \le \alpha B+1\} \le \frac{1+x}{x}\frac{e}{e-1} \{\log(1+\alpha)+\log(\frac{1+x}{x})\}$.
We complete our proof of Proposition \ref{prop: eluder lin} through computing this upper bound at $(\zeta_0, \alpha_0)$,
$$ {\rm dim}_E(\Fc, \epsilon) \le p(4n-1)\frac{e}{e-1} \log\left[ \left(1+\left( \frac{2C_\phi C_\theta}{\epsilon}\right)^2 \right)\left(4n-1\right) \right] + 1 = \tilde{O}(np). $$

%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\subsection{Quadratic functions $f(x) = \phi^T(x) \theta \phi(x) $}
Let $\mathcal{F} = \{ f \ | f(x) = \phi(x)^T \theta \phi(x)  \text{ for } \theta \in \Real^{p \times p}, \phi \in \Real^p ,
\|\theta \|_2 \le C_\theta , \|\phi\|_2 \le C_\phi \}$ then for any $\Xc$ we can say that:
$$ {\rm dim}_E(\Fc, \epsilon) \le p(4p-1)\frac{e}{e-1} \log\left[ \left(1+\left( \frac{2 p C_\phi^2 C_\theta}{\epsilon}\right)^2 \right)\left(4p-1\right) \right] + 1 = \tilde{O}(p^2). $$
Where we have simply applied the linear result with $\tilde{\epsilon} = \frac{\epsilon}{p C_\Pc}$.
This is valid since if we can identify the linear function $g(x) = \theta \phi(x)$ to within this tolerance then we will certainly know $f(x)$ as well.


\subsection{Generalized linear models}
Let $g(\cdot)$ be a component-wise independent function on $\Real^n$ with derivative in each component bounded  $\in [\underline{h},\overline{h}]$ with $\underline{h}>0$.
Define $r = \frac{\overline{h}}{\underline{h}} > 1$ to be the condition number.
If $\mathcal{F} = \{ f \ | f(x) = g(\theta \phi(x))  \text{ for } \theta \in \Real^{n \times p}, \phi \in \Real^p ,
\|\theta \|_2 \le C_\theta , \|\phi\|_2 \le C_\phi \}$
then for any $\Xc$:
$${\rm dim}_E(\Fc, \epsilon) \le p \left(r^2(4n-2)+1\right)\frac{e}{e-1} \left(\log \left[\left(r^2(4n-2)+1 \right) \left(1+ \left(\frac{2C_\theta C_\phi}{\epsilon} \right)^2\right) \right] \right) + 1 = \tilde{O}(r^2 np)$$

This proof follows exactly as per the linear case, but first using a simple reduction on the form of equation \eqref{eq: w_k}.
\begin{eqnarray*}
	w_k &=& \sup \left\{ \|(\overline{f} - \underline{f}) (x_k)\|_2 \ \bigg| \  \|\overline{f}-\underline{f}\|_{2,E_t} \le \epsilon' \right\} \\
	&\le& \max_{\theta_1, \theta_2} \left\{ \|g(\theta_1 \phi_k) - g(\theta_2 \phi_k) \|_2 \ \big| \
		\sum_{i=1}^{k-1} \|g(\theta_1 \phi_i) - g(\theta_2 \phi_i) \|_2^2 \le \epsilon^2 \right\} \\
	&\le& \max_\theta \left\{ \overline{h} \|\theta \phi_k \|_2 \ \big| \
		\sum_{i=1}^{k-1} \underline{h}^2 \| \theta \phi_i \|_2^2 \le \epsilon^2 \right\}
\end{eqnarray*}
To which we can now apply Lemma \ref{lem: norms trace} with the $\epsilon$ rescaled by $r$.
Following the same arguments as for linear functions now completes our proof.


%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

\section{Bounded LQR control}
\label{app: Bounded LQR}

We imagine a standard linear quadratic controller with rewards with $x = (s,a)$ the state-action vector.
The rewards and transitions are given by:
$$ R(x) = -x^T A x + \epsilon_R \ , \ P(x) = \Pi_C (Bx + \epsilon_P),$$
where $A \succcurlyeq 0$ is positive semi-definite and $\Pi_C$ projects x onto the $\| \cdot \|_2$-ball at radius $C$.

In the case of unbounded states and actions the Ricatti equations give the form of the optimal value function $V(s) = -s^T Q s$ for $Q \succcurlyeq 0$.
In this case we can see that the difference in values of two states:
$$ |V(s) - V(s')| = |-s^T Q s + {s'}^T Q s' | = |-(s + s')^T Q (s-s')| \le 2C\lambda_1 \|s-s'\|_2 $$
where $\lambda_1$ is the largest eigenvalue of $Q$ and $C$ is an upper bound on the $\| \cdot \|_2$-norm of both $s$ and $s'$.
We note that $2C \lambda_1$ works as an effective Lipshcitz constant when we know what $C$ can bound $s, s'$.

We observe that for any projection $\Pi_C(x) = \alpha x$ for $\alpha \in (0, 1]$ and that for all positive semi-definite matrices $A \succcurlyeq 0$, $(\alpha x)^T A (\alpha x) = \alpha^2 x^T A x \le x^T A x$.
Using this observation together with reward and transition functions we can see that the value function of the bounded LQR system is always greater than or equal to that of the unconstrained value function.
The effect of excluding the low-reward outer region, but maintaining the higher-reward inner region means that the value function becomes more flat in the bounded case, and so $2C \lambda_1$ works as an effective Lipschitz constant for this problem too.

%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

\section{UCRL-Eluder}
\label{app: UCRL-Eluder}
For completeness, we explicitly outline an optimistic algorithm which uses the confidence sets in our analysis of PSRL to guarantee similar regret bounds with high probability over all MDP $M^*$.
The algorithm follows the style of UCRL2 \cite{jaksch2010near} so that at the start of the $k$th episode the algorithm form $\Mc_k = \{M | P^M \in \Pc_k, R^M \in \Rc_k\}$ and then solves for the optimistic policy that attains the highest reward over any $M$ in $\Mc_k$.

\begin{algorithm}[H]
\caption{\protect\\ UCRL-Eluder}
\label{alg: UCRL-Eluder}

\begin{algorithmic}[1]
    \State \textbf{Input: } Confidence parameter $\delta>0$, t=1
    \For{episodes $k=1,2,..$}
    \State{form confidence sets $\Rc_k(\beta^*(\Rc,\delta,1/k^2))$ and $\Pc_k(\beta^*(\Pc,\delta,1/k^2))$}
    \State{compute $\mu_k$ optimistic policy over $\Mc_k = \{M | P^M \in \Pc_k, R^M \in \Rc_k\}$}
	    \For{timesteps $j=1,..,\tau$}
	        \State{apply $a_t \sim \mu_k(s_t,j)$}
	        \State{observe $r_t$ and $s_{t+1}$}
	        \State{advance $t=t+1$}
	    \EndFor
	\EndFor
\end{algorithmic}
\end{algorithm}

Generally, step 4 of this algorithm with not be computationally tractable even when solving for $\mu^M$ is possible for a given $M$.



\end{document}





EluderL2.bbl
\begin{thebibliography}{10}

\bibitem{burnetas1997optimal}
Apostolos Burnetas and Michael Katehakis.
\newblock Optimal adaptive policies for {M}arkov decision processes.
\newblock {\em Mathematics of Operations Research}, 22(1):222--255, 1997.

\bibitem{lai1985asymptotically}
Tze~Leung Lai and Herbert Robbins.
\newblock Asymptotically efficient adaptive allocation rules.
\newblock {\em Advances in applied mathematics}, 6(1):4--22, 1985.

\bibitem{kaelbling1996reinforcement}
Leslie~Pack Kaelbling, Michael~L Littman, and Andrew~W Moore.
\newblock Reinforcement learning: A survey.
\newblock {\em arXiv preprint cs/9605103}, 1996.

\bibitem{valiant1984theory}
Leslie~G Valiant.
\newblock A theory of the learnable.
\newblock {\em Communications of the ACM}, 27(11):1134--1142, 1984.

\bibitem{littlestone1988learning}
Nick Littlestone.
\newblock Learning quickly when irrelevant attributes abound: A new
  linear-threshold algorithm.
\newblock {\em Machine learning}, 2(4):285--318, 1988.

\bibitem{li2011knows}
Lihong Li, Michael~L Littman, Thomas~J Walsh, and Alexander~L Strehl.
\newblock Knows what it knows: a framework for self-aware learning.
\newblock {\em Machine learning}, 82(3):399--443, 2011.

\bibitem{jaksch2010near}
Thomas Jaksch, Ronald Ortner, and Peter Auer.
\newblock Near-optimal regret bounds for reinforcement learning.
\newblock {\em The Journal of Machine Learning Research}, 99:1563--1600, 2010.

\bibitem{kearns2002near}
Michael Kearns and Satinder Singh.
\newblock Near-optimal reinforcement learning in polynomial time.
\newblock {\em Machine Learning}, 49(2-3):209--232, 2002.

\bibitem{brafman2003r}
Ronen Brafman and Moshe Tennenholtz.
\newblock R-max-a general polynomial time algorithm for near-optimal
  reinforcement learning.
\newblock {\em The Journal of Machine Learning Research}, 3:213--231, 2003.

\bibitem{strehl2006pac}
Alexander Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael Littman.
\newblock Pac model-free reinforcement learning.
\newblock In {\em Proceedings of the 23rd international conference on Machine
  learning}, pages 881--888. ACM, 2006.

\bibitem{osband2013more}
Ian Osband, Daniel Russo, and Benjamin Van~Roy.
\newblock {(More) Efficient Reinforcement Learning via Posterior Sampling}.
\newblock {\em Advances in Neural Information Processing Systems}, 2013.

\bibitem{auer2003using}
Peter Auer.
\newblock Using confidence bounds for exploitation-exploration trade-offs.
\newblock {\em The Journal of Machine Learning Research}, 3:397--422, 2003.

\bibitem{bubeck2011xarmed}
S{\'e}bastien Bubeck, R{\'e}mi Munos, Gilles Stoltz, and Csaba Szepesv{\'a}ri.
\newblock X-armed bandits.
\newblock {\em Journal of Machine Learning Research}, 12:1587–1627, 2011.

\bibitem{russo2013}
Daniel Russo and Benjamin~Van Roy.
\newblock Learning to optimize via posterior sampling.
\newblock {\em CoRR}, abs/1301.2609, 2013.

\bibitem{osband2014near}
Ian Osband and Benjamin Van~Roy.
\newblock Near-optimal regret bounds for reinforcement learning in factored
  {MDP}s.
\newblock {\em arXiv preprint arXiv:1403.3741}, 2014.

\bibitem{abbasi2011improved}
Yassin Abbasi-Yadkori, D{\'a}vid P{\'a}l, and Csaba Szepesv{\'a}ri.
\newblock Improved algorithms for linear stochastic bandits.
\newblock {\em Advances in Neural Information Processing Systems}, 24, 2011.

\bibitem{ibrahimi2012efficient}
Morteza Ibrahimi, Adel Javanmard, and Benjamin Van~Roy.
\newblock Efficient reinforcement learning for high dimensional linear
  quadratic systems.
\newblock In {\em NIPS}, pages 2645--2653, 2012.

\bibitem{ortner2012online}
Ronald Ortner, Daniil Ryabko, et~al.
\newblock Online regret bounds for undiscounted continuous reinforcement
  learning.
\newblock In {\em NIPS}, pages 1772--1780, 2012.

\bibitem{russo2013eluder}
Daniel Russo and Benjamin Van~Roy.
\newblock Eluder dimension and the sample complexity of optimistic exploration.
\newblock In {\em Advances in Neural Information Processing Systems}, pages
  2256--2264, 2013.

\bibitem{thompson1933}
William Thompson.
\newblock On the likelihood that one unknown probability exceeds another in
  view of the evidence of two samples.
\newblock {\em Biometrika}, 25(3/4):285--294, 1933.

\bibitem{strens2000bayesian}
Malcom Strens.
\newblock A {B}ayesian framework for reinforcement learning.
\newblock In {\em Proceedings of the 17th International Conference on Machine
  Learning}, pages 943--950, 2000.

\bibitem{bertsekas1995dynamic}
Dimitri Bertsekas.
\newblock {\em Dynamic programming and optimal control}, volume~1.
\newblock Athena Scientific Belmont, MA, 1995.

\bibitem{van2014generalization}
Benjamin Van~Roy and Zheng Wen.
\newblock Generalization and exploration via randomized value functions.
\newblock {\em arXiv preprint arXiv:1402.0635}, 2014.

\end{thebibliography}
