Horizon-Free Regret for Linear Markov Decision Processes

Thanks for your detailed review! Please find our discussions on the computational complexity and the significance of in the common response. For other questions, please find our response below.

About connection between $\sum_{k=1}^K \sum_{i=1}^{\log_2(H)+1}\max_{h'\in H_i}\sum_{h\in H_i}\mathbb{V}(P_{s_h^k,a_h^k},V_{h'+1}^*)$ and $\max_{h'\in [H]}\sum_{k=1}^K \sum_{h=1}^H \mathbb{V}(P_{s_h^k,a_h^k},V_{h'+1}^*)$ (Here we use $H_i$ ($V_i$) to replace $\mathcal{H}_i$ $(\mathcal{V}_i)$ so that the Latex editor works):

We try to give a more detailed explanation as following: Our initial target is to bound \sum_{k=1}^K \min\left\\{ \sum_{h=1}^H \sqrt{ (\phi_h^k)^{\top} (\Lambda^k(V_{h+1}^*))^{-1}\phi_h^k } ,1\right\\}.

Following the naive maximal variance approach, we need to bound the later term $\max_{h'\in [H]}\sum_{k=1}^K \sum_{h=1}^H \mathbb{V}(P_{s_h^k,a_h^k},V_{h'+1}^*)$, which is still hard (as presented by the counter example). Instead, we turn to bound \max_{h'\in [H]}\sum_{k=1}^K \sum_{h=1}^H \mathbb{V}(P_{s_h^k,a_h^k},V_{h'+1}^*)\leq \sum_{i=1}^{\log_2(H)+1}\sum_{k=1}^K \min\left\\{ \sum_{h\in H_i}\sqrt{ (\phi_h^k)^{\top}(\Lambda^k(V_{h+1}^*))^{-1}\phi_h^k } ,1\right\\}, where we could use the bound for the first term $\sum_{k=1}^K \sum_{i=1}^{\log_2(H)+1}\max_{h'\in H_i}\sum_{h\in H_i}\mathbb{V}(P_{s_h^k,a_h^k},V_{h'+1}^*)$.

About convex assumption of feature space:

Indeed, for any feature space $\Phi$, we can perform any feature in the convex hull of $\Phi$. Suppose there are two actions $a_1$ and $a_2$ with feature $\phi_1$ and $\phi_2$ respectively, then we can create a new (virtual) action with feature $p \phi_1+(1-p)\phi_2$ by playing $a_1$ with probability $p$ and $a_2$ with probability $1-p$. Therefore this assumption is without the loss of generality.

About the statement "$\mathbb{V}(P_{s,a},v)= \phi(s,a)^{\top} (\theta(v^2)) - (\phi(s,a)^{\top}\theta(v))^2$" in page 7:

We can write $\mathbb{V}(P_{s,a},v)= \phi(s,a)^{\top} (\theta(v^2)) - (\phi(s,a)^{\top}\theta(v))^2$ as $\mathrm{Trace}(L^{\top}(s,a) B(v))$ where

B(v)= \left[\begin{array}{cc} -\theta(v)\theta^{\top}(v) , & \theta(v^2)/2,\\ \theta^{\top}(v^2)/2 ,& 0 \end{array}\right]

Thank you for your time and efforts in reviewing our work. We have provided detailed clarification to address the issues raised in your comments. If our response has addressed your concerns, we would be grateful if you could re-evaluate our work.

If you have any additional questions or comments, we would be happy to have further discussions.

Thanks,

The authors

Thanks for your detailed review! Please find our discussion on the computational complexity in the common response. For other questions, please find our response below.

About paper structure: We have adjusted the structure of this paper and presented the algorithm before introducing the techniques.

About the typos: We have fixed the typos accordingly in the revision. Thanks for the effort to check the correctness of this work.

About Algorithm 1:

About $\mathcal{W}(\epsilon)$:

$\mathcal{W}$ is a continuous set and $\mathcal{W}_{\epsilon}$ is the discretization of $\mathcal{W}$.

You are correct that $\mathcal{W}(\epsilon)$ and $\mathcal{W}_{\epsilon}$ denote the same set.

We replaced $\mathcal{W}(\epsilon)$ by $\mathcal{W}_{\epsilon}$ and updated the paper accordingly. Thanks for pointing out!

$\tilde{\theta}(v)$ is not used in the line 10 of Alg 1 and after?

We do not use $\tilde{\theta}(v)$ in the main algorithm. $\tilde{\theta}$ in the output of Algorithm 3 is used in the statement and proof of Lemma 10, which states that $(\hat{\theta}, \tilde{\theta})$ is a close estimation of $(\theta(v),\theta(v^2) )$.

Assumption 2: Is assumption (2d) standard?

Assumption (2d) could be find in Section 8.1 in [Agarwal et al, 2019]. The commonly used assumption [Jin et. al., 2020, He et.al., 2022]: $P_{s,a,s} = \phi_{s,a}^{\top}\theta_{s’}$ with $\||\theta_{s’}\||_2 \leq \sqrt{d}$, implies assumption (2d). It is possible to obtain an $|S|$-independent regret bound due to the linear structure since we are only required to learn $\mu^{\top}v$ for certain vectors $v$.

Additional reference:

[Agarwal et al., 2019] Reinforcement learning: Theory and algorithms

[Jin et. al., 2020] Provably efficient reinforcement learning with linear function approximation

[He et. al. 2022] Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes.

Similarity with contextual linear bandit problem:

We believe linear MDP has the same intrinsic hardness as contextual linear bandit problem. The transitions are involved but it suffices to learn $\theta^*_h$ for $h \in [H]$ to make decisions.

About VOFUL:

VOFUL is an algorithm with variance-awared regret bound for linear bandits. The high-level idea is to construct a confidence region for the unknown parameter $\theta$ and then choose arm optimistically. Both VOFUL and OFUL rely on optimism but the algorithm structures are quite different.

Thank you for your time and efforts in reviewing our work. We have provided detailed clarification to address the issues raised in your comments. If our response has addressed your concerns, we would be grateful if you could re-evaluate our work.

If you have any additional questions or comments, we would be happy to have further discussions.

Thanks,

The authors

Thanks for the review! Please find our discussion on the computational complexity in the common response.

Thanks for your detailed feedback! We have updated our paper accordingly. Please find our response to your questions below.

About Lemma 4:

We revise the proof of Lemma 4 in the revision. We are sorry that in the previous version we mistakenly define $\bar{\phi} = \int_{\Phi}\phi du(\phi)$. Indeed we need add a regularization factor as $\bar{\phi} = \int_{\Phi}\phi du(\phi) / \int_{\Phi}du(\phi)$ to make sure $\bar{\phi}$ is the geometry center of $\Phi$.

Here we presented the response to your two questions regarding Lemma 4. Because of the symmetric structure of $\mathbb{R}^n$, we can assume that $\psi = [1,0,0,\ldots,0]^{\top}$. Now we try to explain your questions.

Why $\frac{f(l-y)}{y^{d-1}}\leq \frac{f(l-x)}{x^{d-1}}$:

We have added a detailed proof in the appendix page 13 (marked in red). At a high-level, $f(x)$ denote the $d-1$-dimensional volume of the slice $\mathcal{V}(x):=\Phi \cap \{\phi_1 = x | \phi\in \mathbb{R}^d \}$ (here $\phi_1$ denotes the first dimension of $\phi$). Note that $\mathcal{V}(l)$ is non-empty, and $\Phi$ is convex and closed. Let $\tilde{\phi}$ be an arbitrary element of $\mathcal{V}(l)$. We then have that $\frac{x}{y}\mathcal{V}(l-y) + \frac{y-x}{y}\tilde{\phi}:= \{ \frac{x}{y}\phi+\frac{y-x}{y}\tilde{\phi}｜ \phi\in \mathcal{V}(l-y) \}\subset \mathcal{V}(l-x)$, which implies the $d-1$-dimensional volume of $\mathcal{V}(l-x)$ is at least $(\frac{x}{y})^{d-1}$ fraction of that of $\mathcal{V}(l-y)$ for $0<x\leq y \leq l$.

About (16):

After correcting the definition $\bar{\phi}$,

$

z &= \frac{\int_{\Phi}\phi^{\top}\psi du(\phi)}{\int_{\phi}du(\phi)} \nonumber \ & = \lim_{\epsilon\to 0}\sum_{i=0}^{\left\lceil l/\epsilon\right\rceil}\frac{\int_{\phi\in \Phi, \phi^{\top}\psi \in [i\epsilon,(i+1)\epsilon) } \phi^{\top}\psi du(\phi) }{\int_{\Phi}du(\phi)}\nonumber \ & = \lim_{\epsilon\to 0}\sum_{i=0}^{\left\lceil l/\epsilon\right\rceil}\frac{\int_{\phi\in \Phi, \phi^{\top}\psi \in [i\epsilon,(i+1)\epsilon) } i\epsilon du(\phi) }{\int_{\Phi}du(\phi)}\nonumber \ & = \lim_{\epsilon\to 0}\sum_{i=0}^{\left\lceil l/\epsilon\right\rceil}f(i\epsilon)i\epsilon^2\nonumber \ & = \int_{0}^l f(x)xdx. \nonumber

$

By re-arrange the inequality, and noting that $int_{0}^{l}f(x)dx = 1$ we have that

$

\int_{ 0\leq x \leq z}f(x)\cdot (z-x) d(x)= \int_{ z\leq x\leq l} f(x)(x-z)dx, \nonumber

$

About Lemma 11:

About Equation (a). We make a re-arrangement as $\sum_{h=h_1}^{h_2} v^2(s^k_{h+1}) \leq \sum_{h=h_1}^{h_2} v^2(s^k_{h}) + v^2(s_{h_2+1}^k)\leq \sum_{h=h_1}^{h_2} v^2(s^k_{h})+1$

About $\bar{v}(s)$: It should be $\bar{v}(s) = \max\{ \max_a P_{s,a}v, v(s) \}$.

About Equation $c$. with the definition of $\bar{v}(s)$ above, we have $\max\{ v(s_h^k)-P_{s,a}v, 0 \} \leq \max\{ \bar{v}(s_h^k)-P_{s,a}v,0 \} =\bar{v}(s_h^k)-P_{s,a}v.$

About Equation (d). The term c should be replaced by $\|\bar{v}-v\|_{\infty}$. Sorry for this mistake.

Typos:

About $\sigma$: we use $\sigma^2$ to denote the variance term throughout the paper. We fix the typos in the revision.

About $O$ in the proof of Lemma 5. $O$ should be $\max_j \sum_{i=1}^n \phi_i^{\top}\psi_j$. We fix this inequality and delete $O$.

About $Var$ in Eq.(28): we replace it by $\mathbb{V}$.

About Eq.(29): We add the bracket to $i$.

About Eq.(30): We replace $\bar{\Lambda}^k$ by $\bar{\Lambda}^k_{(i)}$ in the analysis after Eq.(30). The equation $\bar{\Lambda}^k_{(i)}+\sum_{h\in H_i}\frac{\phi_{h}^{k}(\phi_{h}^{k})^{\top}}{\max_{v\in V_i}(\sigma_{h}^{k}(v))^2} \preccurlyeq \bar{\Lambda}^k_{(i)} + \sum_{h=1}^H\frac{\phi_{h}^{k} (\phi_{h}^{k})^{\top}}{\max_{v\in V_i}(\sigma_{h}^{k}(v))^2} =\bar{\Lambda}^{k+1}_{(i)}$

should be replaced by $\bar{\Lambda}^k_{(i)} + \sum_{h\in H_{i}}\frac{\phi_{h}^{k} (\phi_{h}^{k})^{\top}}{\max_{v\in V_i}(\sigma_{h}^{k}(v))^2} =\bar{\Lambda}^{k+1}_{(i)}$

About $\|\bar{v}-v\|_i$: it should be $\|\bar{v}-v\|_{\infty}$.

About norm type in Lemma 12: it should be $\infty$ norm