Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound

Introduction

Reinforcement learning (RL) is about learning to make sequential decisions in an unknown environment through trial and error. It finds wide applications in robotics Kober et al., (2013), autonomous driving Shalev-Shwartz et al., (2016), game AI Silver et al., (2017) and beyond. We consider a basic RL model - the Markov decision process (MDP). In the MDP, an agent at a state $s\in\mathcal{S}$ is able to play an action $a\in\mathcal{A}$, where $\mathcal{S}$ and $\mathcal{A}$ are the state and action spaces. Then the system transitions to another state $s^{\prime}\in\mathcal{S}$ according to an unknown probability $P(s^{\prime}~{}|~{}s,a)$, while returning an immediate reward $r(s,a)\in$. The goal of the agent is to obtain the maximal possible return after playing for a period of time - even though she has no knowledge about the transition probabilities at the beginning.

The performance of a learning algorithm is measured by “regret”. Regret is the difference between the cumulative reward obtained using the best possible policy and the cumulative reward obtained by the learning algorithm. In the tabular setting where $\mathcal{S}$ and $\mathcal{A}$ are finite sets, there exist algorithms that achieve asymptotic regret $O(\sqrt{|\mathcal{S}||\mathcal{A}|T})$ (e.g. Jaksch et al., (2010); Osband and Van Roy, (2016); Osband et al., (2017); Agrawal and Jia, (2017); Azar et al., (2017); Dann et al., (2018); Jin et al., (2018)), where $T$ is the number of time steps. However, the aforementioned regret bound depends polynomially on ${|\mathcal{S}|}$ and $|\mathcal{A}|$, sizes of the state and action space, which can be very large or even infinite. For instance, the game of Go has $3^{361}$ unique states, and a robotic arm has infinitely many continuous-valued states. In the most general sense, the regret $O(\sqrt{|\mathcal{S}||\mathcal{A}|T})$ is nonimprovable in the worst case Jaksch et al., (2010). This issue is more generally known as the “curse of dimensionality” of control and dynamic programming Bellman, (1966).

To tackle the dimensionality, a common practice is to use features to parameterize high-dimensional value and policy functions in compact presentations, with the hope that the features can capture leading structures of the MDP. In fact, there are phenomenal empirical successes of reinforcement learning using explicit features and/or neural networks as implicit features (see e.g., Mnih et al., (2015)). However, there is a lack of theoretical understanding about using features for exploration in RL and its learning complexity. In this paper, we are interested in the following theoretical question:

Furthermore, we consider online RL in a reproducing kernel space. Kernel methods are well known to be powerful to capture nonlinearity and high dimensionality in many machine learning tasks Shawe-Taylor et al., (2004). We are interested in using kernel methods to capture nonlinearity in the state-transition dynamics of MDP. A kernel space may consist of infinitely many implicit feature functions. We study the following questions: How to use kernels in online reinforcement learning? Can one achieve low regret even though the kernel space is infinite-dimensional? The goal of this paper is to answer the aforementioned questions affirmatively. In particular, we would like to design algorithms that take advantages of given features and kernels to achieve efficient exploration.

In the kernel setting, this condition is equivalent to that the transition probability model $P$ belongs to the product space of the reproducing kernel spaces. This condition is essentially equivalent to using the features $\phi$ to represent value functions Parr et al., (2008). When the probability transition model $P$ cannot be fully embedded using $\phi$, then value function approximation using $\phi$ may lead to arbitrarily large Bellman error Yang and Wang, (2019).

We propose an algorithm, which is referred to as MatrixRL, that actively explores the state-action space by estimating the core matrix via ridge regression. The algorithm balances the exploitation-exploration tradeoff by constructing a confidence ball of core matrix for optimistic dynamic programming. It can be thought of as a “matrix bandit” algorithm which generalizes the idea of linear bandit (e.g. Dani et al., (2008); Li et al., (2010); Chu et al., (2011)). It is proved to achieve the regret bound either

depending on regularity properties of the features. MatrixRL can be implemented efficiently in space $O(d^{2})$. Each step can be carried out in closed form. Next we extend the MatrixRL to work with the kernel spaces with $k_{\phi}(\cdot,\cdot)=\langle\phi(\cdot),\phi(\cdot)\rangle$ and $k_{\psi}(\cdot,\cdot)=\langle\psi(\cdot),\psi(\cdot)\rangle$, and show that it admits a kernelized version. The kernelized MatrixRL achieves a regret bound of

where $\widetilde{d}$ is the effective dimension of kernel space, even if there may be infinitely many features. The regret bounds using features or kernels do not depend on sizes of the state and action spaces, making efficient exploration possible in high dimensions.

Note that for linear bandit, the regret lower bound is known to be $\widetilde{\Omega}(d\sqrt{T})$ Dani et al., (2008). Since linear bandit is a special case of RL, our regret bounds match the lower bound up to polylog factors in $d$ and $T$. To our best knowledge, for reinforcement learning using features/kernels, our result gives the first regret bound that is simultaneously near-optimal in time $T$, polynomial in the planning horizon $H$, and near-optimal in the feature dimension $d$.

2 Related Literature

In the tabular case where there are finitely many states and actions without any structural knowledge, complexity and regret for RL has been extensively studied. For $H$-horizon episodic RL, efficient methods typically achieve regret that scale asymptotically as $O(\sqrt{HSAT})$ (see for examples Jaksch et al., (2010); Osband and Van Roy, (2016); Osband et al., (2017); Agrawal and Jia, (2017); Azar et al., (2017); Dann et al., (2018); Jin et al., (2018)). In particular, Jaksch et al., (2010) provided a regret lower bound $\Omega(\sqrt{HSAT})$ for $H$-horizon MDP. There is also a line of works studying the sample complexity of obtaining a value or policy that is at most $\epsilon$-suboptimal Kakade, (2003); Strehl et al., (2006, 2009); Szita and Szepesvári, (2010); Lattimore and Hutter, (2014); Azar et al., (2013); Dann and Brunskill, (2015); Sidford et al., (2018). The optimal sample complexity for finding an $\epsilon$-optimal policy is O\big{(}|\mathcal{S}||\mathcal{A}|(1-\gamma)^{-2}\epsilon^{-2}\big{)} Sidford et al., (2018) for a discounted MDP with discount factor $\gamma$. The optimal lower bound has been proven in Azar et al., (2013).

There is also a line of works on solving MDPs with a function approximation. For instance Baird, (1995); Tsitsiklis and Van Roy, (1997); Parr et al., (2008); Mnih et al., (2013, 2015); Silver et al., (2017); Yang and Wang, (2019). There are also phenomenal empirical successes in deep reinforcement learning as well (e.g., Silver et al., (2017)). However there are not many works on the regret analysis of RL with function approximators. Very recently, Azizzadenesheli et al., (2018) studied the regret bound for linear function approximator. However their bound has factor that can be exponential in $H$. Chowdhury and Gopalan, (2019) considers the regret bound for kernelized MDP. However, they need a Gaussian process prior and assumes that the transition is deterministic with some controllable amount of noise – a very restrictive setting. Another work Modi and Tewari, (2019) also considers the linear setting for RL. However, the regret bound is linearly depending on the number of states. To the best of our knowledge, we are not aware of other works that achieve regret bound for RL with function approximators that is simultaneously near optimal in $T$, polynomial in $H$, and has no dependence with the state-action space size.

Our results are also related to the literature of linear bandits. Bandit problems can be viewed as a special case as Markov decision problems. There is a line of works on linear bandit problems and their regret analysis Dani et al., (2008); Rusmevichientong and Tsitsiklis, (2010); Li et al., (2010); Abbasi-Yadkori et al., (2011); Chu et al., (2011). For a more detailed survey, please refer to Bubeck et al., (2012). Part of our results are inspired by the kernelization for the linear bandit problems, e.g. Valko et al., (2013); Chowdhury and Gopalan, (2017), who studied the regret bound when the features of each arm lies in some reproducing kernel Hilbert space.

Problem Formulation

In a episodic Markov decision process (MDP for short), there is a set of states $\mathcal{S}$ and a set of actions $\mathcal{A}$, which are not necessarily finite. At any state $s\in\mathcal{S}$, an agent is allowed to play an action $a\in\mathcal{A}$. She receives an immediate reward $r(s,a)\in$ after playing $a$ at $s$, the process will transition to the next state $s^{\prime}\in\mathcal{S}$ with probability $P(s^{\prime}~{}|~{}s,a)$, where $P$ is the collection of transition distributions. After $H$ time steps, the system restarts at a prespecified state $s_{0}$. The full instance of an MDP can be described by the tuple $M=(\mathcal{S},\mathcal{A},P,r,s_{0},H).$ The agent would like to find a policy $\pi:\mathcal{S}\times[H]\rightarrow\mathcal{A}$ that maximizes the long-term expected reward starting from every state $s$ and every stage $h\in[H]$, i.e.,

In the online RL setting, the learning algorithm interacts with the environment episodically. Each episode starts from state $s_{0}$ takes $H$ steps to finish. We let $n$ denote the current number of episodes and denote $t=(n-1)H+h$ the current time step. We equalize $t$ and $(n,h)$ and may switch between the two nations. We use the following definition of regret.

Suppose we run algorithm $\mathcal{K}$ in the online environment of an MDP $\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,s_{0},H)$ for $T=NH$ steps. We define the regret for algorithm $\mathcal{K}$ as

Throughout this paper, we focus on RL problems where the probability transition kernel $P(\cdot~{}|~{}\cdot)$ can be fully embedded in a given feature space.

Here, we call the matrix $M^{*}$ as a transition core.

Note that when $\phi,\psi$ are features associated with two reproducing kernel spaces $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$, this assumption requires that $P$ belong to their product kernel space $\mathcal{H}_{1}\times\mathcal{H}_{2}$.

RL Exploration in Feature Space

In this section, we study the near optimal way to balance exploration and exploitation in RL using a given set of features. We aim to develop an online RL algorithm with regret that depends only on the feature size $d$ but not on the size of the state-action space. Our algorithm is inspired by the LinUCB algorithm Chu et al., (2011) and its variants Dani et al., (2008) and can be viewed as a “matrix bandit” method.

The high level idea of the algorithm is to approximate the unknown transition core $M^{*}$ using data that has been collected so far. Suppose at the time step $t=(n,h)$ (i.e. episode $n\leq N$ and stage $h\leq H$), we obtain the following state-action-state transition triplet: $(s_{t},a_{t},\widetilde{s}_{t}),$ where $\widetilde{s}_{t}:=s_{t+1}$. For simplicity, we denote the associated features by

Let $K_{\psi}:=\sum_{\widetilde{s}\in\mathcal{S}}\psi(\widetilde{s})\psi(\widetilde{s})^{\top}$. We construct our estimator of $M^{*}$ as:

Let us explain the intuition of $M_{n}$. Note that

Therefore $M_{n}$ is the solution to the following ridge regression problem:

Upper confidence RL using a matrix ball.

In online RL, a critical step is to estimate future value of the current state and action use dynamic programming. To better balance exploitation and exploration, we use a matrix ball to construct optimistic value function estimator. At episode $n$:

Here the matrix ball $B_{n}=B_{n}^{(1)}$ is constructed as

where $\beta_{n}$ is a parameter to be determined later, and $\|Y\|_{2,1}=\sum_{i}\sqrt{\sum_{j}Y{(i,j)}^{2}}$. At time $(n,h)$, suppose the current state is $s_{n,h}$, we play the optimistic action $a_{n,h}=\arg\max_{a}Q_{n,h}(s_{n,h},a).$ The full algorithm is given in Algorithm 1.

2 Regret Bounds for MatrixRL

Let $C_{M},C_{\phi},C_{\psi}$ and $C_{\psi}^{\prime}$ be positive parameters.

$\forall~{}(s,a)\in\mathcal{S}\times\mathcal{A}:\quad\|\phi(s,a)\|_{2}^{2}\leq C_{\phi}d$;

With these conditions we are ready to provide the regret bound.

Suppose Assumption 1 and Assumption 2 hold. Then after $T=NH$ steps, Algorithm 1 achieves regret bound:

if we let $\beta_{k}=c\cdot(C_{M}+{C_{\psi}^{\prime}}^{2})\cdot\ln(NHC_{\phi})\cdot d,$ for some absolute constant $c>0$.

Further, if the feature space $\Psi$ admits a tighter bound for value function in this space, we can slightly modify our algorithm to achieve sharper regret bound. To do this, we need to slightly change our Assumption 2 to Assumption 2′.

Let $C_{M},C_{\phi},C_{\psi}$ and $C_{\psi}^{\prime}$ be positive parameters.

$\forall~{}(s,a)\in\mathcal{S}\times\mathcal{A}:\quad\|\phi(s,a)\|_{2}^{2}\leq C_{\phi}d$;

We modify the algorithm slightly by using a Frobenious-norm matrix ball instead of the 2-1 norm and computing sharper confidence bounds. Let $B_{n}=B_{n}^{(2)}$ in (3.1), where

Then a sharper regret bound can be established.

Suppose Assumption 1 and Assumption 2′ hold. Then after $T=NH$ steps, Algorithm 1, with $B_{n}=B_{n}^{(2)}$ applied in (3.1), achieves regret

provided $\beta_{n}=c\cdot(C_{M}+{C_{\psi}^{\prime}}^{2})\cdot\ln(NHC_{\phi})\cdot d,$ for some absolute constant $c>0$.

The only stronger condition needed by Assumption 2′ is $\|\Psi^{\top}v\|_{2}\leq C_{\psi}\|v\|_{\infty}$. It can be satisfied if $\Psi$ is a set of sparse features, or if $\Psi$ is a set of highly concentrated features.

We remark that in Theorem 1 and Theorem 2, we need to know the value $N$ in $\beta_{n}$ before the algorithm runs. In the case when $N$ is unknown, one can use the doubling trick to learn $N$ adaptively: first we run the algorithm by picking $N=2$, then for $N=4,8,\ldots,2^{i}$ until the true $N$ is reached. It is standard knowledge that this trick increase the overall regret by only a constant factor (e.g. Besson and Kaufmann, (2018)).

Proof Sketch. The proof consists of two parts. We show that when the core matrix $M^{*}$ belongs to the sequence of constructed balls $\{B_{n}\}$, the estimated Q-functions provide optimistic estimates of the optimal values, therefore the algorithm’s regret can be bounded using the sum of confidence bounds on the sample path. The second part constructs a martingale difference sequence by decomposing a matrix into an iterative sum and uses a probabilistic concentration argument to show that the “good” event happens with sufficiently high probability. Full proofs of Theorems 1 and 2 are deferred to the appendix.

Near optimality of regret bounds. The regret bound in Theorem 2 matches the optimal regret bound $\widetilde{O}(d\sqrt{T})$ for linear bandit Dani et al., (2008). In fact, linear bandit is a special case of RL: the planning horizon $H$ is $1$. Therefore our bound is nearly optimal in $d$ and $T$.

Implementation. Algorithm 1 can be implemented easily in space $O(d^{2})$. When implementing Step 6 using (3.1), we do not need to compute the entire $Q$ function as the algorithm only queries the $Q$-values at particular encountered state-action pairs. For the computation of $\Psi^{\top}V_{k,h+1}$, we can apply random sampling over the columns of $\Psi^{\top}$ to accelerate the computation (see e.g. Drineas and Mahoney, (2016) for more details). We can also apply the random sampling method to compute the matrix $K_{\psi}$ and $K_{\psi}^{-1}$ approximately.

Closed-form confidence bounds. Equation (3.1) requires maximization over a matrix ball. However, it is not necessary to solve this maximization problem explicitly. The algorithm only requires an optimistic Q value. In fact, we can use a closed-form confidence bound instead of searching for the optimal $M$ in the confidence ball. It can be verified that Theorem 1 still holds (by following the same proofs of the theorem) if we replace the second equation of (3.1) as the following equation (see the proof of Theorem 2)

where $w_{n,h}:=\sqrt{\phi_{n,h}^{\top}(A_{n})^{-1}\phi_{n,h}}.$ Similarly, Theorem 2 still holds if we replace the the second equation of 3.1 with

Equations (7) and (8) can be computed easily. They can be viewed as the “dualization” of (3.1).

RL Exploration in Kernel Space

We are now ready to kernelize Algorithm 1. The full algorithm of Kernelized MatrixRL is given in Algorithm 2. Note that the new Q function estimator (6) is the dualization form of (3.1). Therefore Algorithm 2 is more general but essentially equivalent to Algorithm 1 if we let $k_{\phi}(x,y):=\phi(x)^{\top}\phi(y)$ and $k_{\psi}(x,y):=\psi(x)^{\top}\psi(y)$. See Section B for the proof.

2 Regret Bound for Kernelized MatrixRL

We define the effective dimension of the kernel space $\mathcal{H}_{\phi}$ as

Further, we need regularity assumptions for the kernel space.

Let $\mathcal{H}_{\psi}$ be generated by orthonormal basis on $\mathcal{S}$, i.e., there exists $\psi$ such that $\sum_{s\in\mathcal{S}}\psi(s)\psi(s)^{\top}=I$ and $k_{\psi}(s,s^{\prime})=\psi(s)^{\top}\psi(s^{\prime})$. There exists a constant $C_{\psi}$ such that

where $\|\cdot\|_{\mathcal{H}_{\psi}}$ denotes the Hilbert space norm.

The formal guarantee of Kernelized MatrixRL is presented as follows.

Suppose the probability transition kernel $P(\cdot\mid\cdot)$ belongs to the product Hilbert spaces, i.e., $P\in\mathcal{H}_{\phi}\times\mathcal{H}_{\psi}$. Let Assumption 3 hold. Then after $T=NH$ time steps, the regret of Algorithm 2 satisfies

provided $\eta_{n}=2C_{\psi}H\sqrt{\beta_{n}}$ and $\beta_{n}=\Theta(\|P\|_{\mathcal{H}_{\phi}\times\mathcal{H}_{\psi}}\cdot\ln(NH)\cdot\widetilde{d})$.

Note that in Assumption 3, we can additionally relax the assumption on the orthogonality of $\psi$. Similar regret bound can be proved with Assumption 2′. The proof of Theorem 3 is very similar to that of Theorem 2. Although Kernelized MatrixRL does not access the features, the proof is based on the underlying features and the equivalence between kernel representation and feature representation. We postpone it to Section B.

Remark. Similar as MatrixRL, Kernelized MatrixRL can be generalized to deal with unknown reward function by using the Kernelized Bandit Valko et al., (2013). Again, since linear bandit problems are special cases of kernel RL with $H=1$, our results match the linear bandit bound on $\widetilde{d}$ and $\sqrt{T}$. The computation time of Kernelized MatrixRL scales with time $T$ as $T^{2}$ (by applying randomized algorithms, e.g. Dani et al., (2008), in dealing with $\overline{\mathbf{K}}_{\Psi}$ matrices), still polynomial in $T$. We can apply the random features or sketching techniques for kernel to additionally accelerate the computation (e.g. Rahimi and Recht, (2008); Yang et al., (2017)).

Summary

This paper provided the algorithm MatrixRL for episodic reinforcement learning in high dimensions. It also provides the first regret bounds that are near-optimal in time $T$ and feature dimension $d$ and polynomial in the planning horizon $H$. MatrixRL uses given features (or kernels) to estimate a core transition matrix and its confidence ball, which is used to compute optimistic Q-functions for balancing the exploitation-exploration tradeoff. We prove that the regret of MatrixRL is bounded by {O}\big{(}H^{2}d\log T\sqrt{T}\big{)} where $d$ is the number of features, provided that the feature space satisfies some regularity conditions. MatrixRL has an equivalent kernel version, which does not require explicit features. The kernelized MatrixRL satisfies a regret bound {O}\big{(}H^{2}\widetilde{d}\log T\sqrt{T}\big{)}, where $\widetilde{d}$ is the effective dimension of the kernel space. For future work, it remains open if the regularity condition can be relaxed and if there is a more efficient way for constructing confidence balls in order to further reduce the regret.

References

Appendix A Analysis and Proofs

In this section we will focus on proving Theorem 1. In the proof we will also establish all the necessary analytical tools for proving Theorem 2 and Theorem 3. We provide the proofs of the last two theorems at the end of this section.

The proof of Theorem 1 consists of two steps: (a) We first show that if the true transition core $M^{*}$ is always in the confidence ball $B_{n}$, defined in Equation 5, we can then achieve the desired regret bound; (b) We then show that with high probability, the event required by (a) happens. We formalize the event required by step (a) as follows.

For all $n\in[N]$, we denote $E_{n}=1$ if $M^{*}\in B_{n^{\prime}}$ for all $n^{\prime}\in[n]$ and otherwise $E_{n}=0$.

Note that $E_{n}$ is completely determined by the game history up to episode $n$. In the next section, we show (a).

To better investigate the regret formulation (1), we rewrite it according to Algorithm 1. Note that conditioning on the history before episode $n$, the algorithm plays a fixed policy $\pi_{n}$ for episode $n$. Therefore, we have

where $R(n)=V^{*}_{1}(s_{0})-V^{\pi_{n}}_{1}(s_{0})$. We now show that the algorithm always plays an optimistic action (an action with value estimated greater than the optimal value of the state).

Suppose for $n\in[N]$, we have the good estimator event, $E_{n}=1$, happens. Then for $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, we have

We prove the lemma by induction on $h$. It is vacuously true for the case $h=H$ since $Q_{n,H}(s,a)=r(s,a)=Q^{*}_{H}(s,a)$. Suppose the lemma holds for some $1<h^{\prime}\leq H$. We then have

We now consider $h=h^{\prime}-1$. Note that

Next we show that the confidence ball $B_{n}$ actually gives a strong upper bound for the estimation error: the estimation error is “along” the direction of the exploration.

Next we show that the value iteration per-step does not introduce too much error.

Suppose for $n\in[N]$, $E_{n}=1$. Then for $h\in[H]$, we have

We are now ready to show the regret bound.

Suppose Assumption 2 holds, $1\leq\beta_{1}\leq\beta_{2}\leq\ldots\beta_{N}$, then,

Consider $R(n)$ for a fixed $n$. Denote $\mathcal{F}_{n,h}$ as the filtration of fixing the history up to time $(n,h)$ (i.e., fixing $s_{1,1},a_{1,1},s_{1,2},a_{1,2},\ldots,s_{n,h},a_{n,h}$ but not $s_{n,h+1}$). Since if $E_{n}=0$, we can always bound $R(n)\leq H$. We then have

The proof of this lemma is rather technical and requires some new notations, we postpone it to Section A.3. We are now ready to state the regret bound.

Suppose $1\leq\beta_{1}\leq\beta_{2}\leq\ldots\beta_{N}$ and $C_{\psi}\geq 1$, then

A.2 Concentration

In this section, we show that $E_{n}=1$ holds with high probability through out the online learning process. We begin with some notations and axillary random variables. For $(n^{\prime},h^{\prime}),(n,h)\in[N]\times[H]$, we denote $(n^{\prime},h^{\prime})<(n,h)$ if $(n^{\prime},h^{\prime})$ is lexicographically before $(n,h)$, i.e., either $n^{\prime}<n$ or $n=n^{\prime}$ but $h^{\prime}<h$. For each $(n,h)\in[N]\times[H]$, we denote

Notice that $A_{n}=A_{n,1}$ and $M_{n}=M_{n,1}$. Moreover, we denote

Similar to Lemma 9 of Dani et al., (2008), we have the following lemma.

$\sum_{(n^{\prime},h^{\prime})<[n,h]}\min(1,\widetilde{w}_{n^{\prime},h^{\prime}}^{2})\leq 2\ln\det(A_{n,h})\leq 2d\ln[(n-1)HC_{\phi}+(h-1)C_{\phi}+1]$

Firstly, we have $\min(1,\widetilde{w}_{n^{\prime},h^{\prime}}^{2})\leq 2\ln(1+\widetilde{w}_{n^{\prime},h^{\prime}}^{2})$. Next, consider $A_{n,h}$. We have

Note that $\det(A_{1,1})=1$, which proves the first inequality.

Next we consider the second inequality. Since $A_{n,h}$ is positive definite (PD), instead of considering the determinant directly, we consider the trace of $A_{n,h}$.

where we use the fact that $\|\phi_{n^{\prime},h}\|_{2}^{2}\leq C_{\phi}d$. Since $A_{n,h}$ is PD, for the worst case we have

We also let $\beta_{n,h}=\beta_{n}$ for all $n,h$. We consider the following random variables.

If we can bound $Z_{n,h}$ for all $n,h$, we can therefore conclude whether $M^{*}$ is in the ball $B_{n}$. To prove the that $Z_{n,h}$ is indeed small, we use similar techniques developed in Dani et al., (2008). We denote

The next lemma bounds the growth of $Z_{n,h}$.

The proof is very similar to Lemma 12 of Dani et al., (2008). For completeness, we present the proof here. We first introduce the following notation.

Let $(n,h)+1=(n,h+1)$ if $h<H$, or $(n+1,1)$ if $h=H$. We then have

Applying the matrix inversion lemma to $A_{(n,h)+1}$, we have

We now define a martingale difference sequence. In order to upper bound the variance of the random variables, we consider

Then $G_{n,h}$ is a martingale difference sequence with respect to $\mathcal{F}_{n,h}$.

Since $\mathcal{F}_{n,h}$ determines $M_{n,h}$, $\phi_{n,h}$, $\widetilde{w}_{n,h}$, and $Z_{n,h}$ (note that in the definition of $Z_{n,h}$, variable $\psi_{n,h}$ is not included), we have

We will show that with high probability, the martingale difference sum, $\sum_{(n^{\prime},h^{\prime})<(n,h)}G_{(n^{\prime},h^{\prime})}$ never grows too large.

To prove this lemma, we will apply the Freedman’s inequality.

Let $X_{1},X_{2},\ldots,X_{T}$ be a martingale difference sequence with respect to $Y_{1},Y_{2},\ldots,Y_{T}$. Let $b$ be an uniform upper bound on $X_{i}$. Let $V$ be the sum of conditional variances,

We first show the upper bounds on the step size of the martingale $G_{k,h}$.

Next we bound the conditional variance of $G_{n,h}$. We have,

Next by Freedman’s inequality (picking $a=\beta_{n,h}/2$ and $b=\sqrt{\beta_{n,h}}$), we have,

for some sufficiently large constant $c>0$ such that

Lastly, we show that $E_{n}=1$ holds with high probability through out.

We will show that $E_{n,h}=1$ for all $(n,h)\leq(N,H)$ given $\sum_{(n^{\prime},h^{\prime})\leq(n,h)}G_{n^{\prime},h^{\prime}}\leq\beta_{n,h}/2$ for all $(n,h)\leq(N,H)$, as this proves the lemma. We show this by induction on $n,h$. For the base case $(n,h)=(1,1)$, we have $Z_{1,1}=\|M^{*}\|_{F}^{2}\leq\beta_{1,1}$. By inductive hypothesis, $E_{n^{\prime},h^{\prime}}=1$ for all $(n^{\prime},h^{\prime})<(n,h)$. By Lemma 11, we have

for some sufficiently large constant $c>0$. ∎

A.3 Proof of Theorem 1

Before we prove Theorem 1, we first prove the Lemma 8

We will bound the right hand side by establishing an inequality with $\ln\det(A_{N+1})$. Recall that

Notice that each eigenvalue $\lambda_{i}$ of $I+\sqrt{A_{n}^{-1}}\sum_{h=1}^{H}\phi_{n,h}\phi_{n,h}^{\top}\sqrt{A_{n}^{-1}}$ is at least $1$ and

We let $\delta\leq 1/(NH)$. By Lemma 13 and 15, we pick

A.4 Proof of Theorem 2

The proof of Theorem 2 is nearly identical with that of Theorem 1. We will modify Lemma 5 and Lemma 6 to counter for the change of the confidence ball.

For a modification of Lemma 5, we show that for any $M\in B^{(2)}_{n}$,

The rest of the proof follows analogously from that of Theorem 1. ∎

Appendix B Derivation of Kernelization

For the analysis, let us presumably have the features $\phi,\psi$. In the actual algorithm we will avoid using features directly. At time $t=(n-1)H+h$, we denote

Note that $\Phi_{n,h}$ and $\Psi_{n,h}$ are the feature vectors of the encountered state-action pairs; $\Psi$ are the features of all states in $\mathcal{S}$. We also overload the notation by denoting $\Phi_{n}=\Phi_{n,H}$ and $\Psi_{n}=\Psi_{n,H}$. We then observe

can be represented without knowing the features. Similarly, we do not need features to compute $\mathbf{K}_{\psi,n,h}$ and $\overline{\mathbf{K}}_{\psi,n,h}$.

Kernelized Value Estimation

We introduce a dual matrix $\Theta_{n}$, and let $M_{n}=\Phi_{n-1}^{\top}\Theta_{n}\Psi_{n-1}$. Then we have

Therefore, it remains to represent $\Theta_{n+1}$ by the kernel matrices.

This completes the kernelization of the prediction.

Kernelized Confidence Bound

Next we write the confidence bound in the kernelized way as well. We represent $w_{n,h}$ the same way as in Valko et al., (2013). Note that

from which we solve $w_{n}(s,a)^{2}:=\phi(s,a)^{\top}(I+\Phi_{n-1}^{\top}\Phi_{kn-1})^{-1}\phi(s,a)$:

Kernelized Algorithm

We are now ready to write our $Q$-function estimator:

where $\eta_{n}$ is a parameter to be determined. With (3.1) replaced by (6) in Algorithm 1, we obtain our Kernelized MatrixRL, algorithm Algorithm 2.

B.1 Proof of Theorem 3

To prove the theorem, let us presumably have access to some features $\phi$ and $\psi$, which are of dimension $d$ and $d^{\prime}$, respective. For the infinite case we can take $d,d^{\prime}\rightarrow\infty$ and since the complexity does not depending on $d,d^{\prime}$ our proof still follows.

For simplicity, let us define $\mathcal{X}=\mathcal{S}\times\mathcal{A}$. Firstly, we notice that the quantity $\|P\|_{\mathcal{H}_{\phi}\times\mathcal{H}_{\psi}}$ is equivalent to $\|M\|_{F}$ in the finite dimensional setting. Let us define $C_{M}:=\|P\|_{\mathcal{H}_{\phi}\times\mathcal{H}_{\psi}}$. Since

Now, without changing our algorithm, we have that

Thus all the conditions except $C_{\phi}$ in 2′ are satisfied ($C_{\psi}^{\prime}=1$). It will become clear that $C_{\phi}$ is absorbed in the definition of $\widetilde{d}$.

Since Kernelized MatrixRL is equivalent to MatrixRL when the feature space is finite dimensional, the proof of Theorem 3 is nearly identical with that of Theorem 2. To introduce the dependence of the kernel complexity, we keep $\beta_{n}$ as the following form:

By following from the steps of the proof of Theorem 2, we obtain that

Since $\Phi_{n}^{\top}\Phi_{n}$ has the same non-zero eigenvalues with that of $\Phi_{n}\Phi_{n}^{\top}=\mathbf{K}_{\Phi_{n}}$, we have