Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback

Thank you for your support and valuable feedback. We will adopt your writing suggestions in our future version.

Your questions about $poly(A)$ dependence in regrets and the difficulty of adaptive adversaries are explained in Q1 and Q3 of the global response. We answer your other questions below.

Q1: What is exactly the “oracle” that is referred to throughout this paper? Is it hidden in the VoX algorithm?

A: Yes, the oracle is hidden in VoX. A call to VoX requires a polynomial number of calls to a min-max optimization Oracle over a class of value functions to learn a good representation; the Oracle is required by the RepLearn subroutine within VoX. We note that this Oracle is by now standard and has been used in many other works such as [Mhammedi et al., 2023; Zhang et al.,2022b].

Q2: In Thm. 4.1, is $\delta$ the failure probability for the regret guarantee? In other words, is Thm. 4.1 stating a high-probability regret bound?

A: Thank you for pointing it out. This is just a typo in the statement of the theorem. The result in Theorem 4.1 is in expectation and $\delta$ should be replaced by $poly(1/T)$.

Q3: Does the difficulty of adaptive adversaries lie in obtaining high-prob regrets against oblivious adversaries? Is it true that with the help of the known loss feature, one can establish high-prob. regret bound, which easily implies regret bounds against adaptive adversaries?

A: The situation is a little more subtle than this. Even with a known feature loss, Algorithm 2 would still fail against an adaptive adversary because the estimation of the average $Q$-functions within an epoch can no longer be reduced to a standard least-squares regression problem with i.i.d.~data; see the answer to Q3 in the general response. Instead, the algorithm in Section 5 aims at estimating the average $Q$-functions, not in a least-squares sense, but in expectation over roll-ins using policies in $\Psi_{`span`}$; the ``in-expectation'' estimation task is in a sense easier. Here, $\Psi_{`span`}$ is a set of policies with good coverage over state-action pairs. More specifically, $\Psi_{`span`}$ is required to be such that $\\{ \mathbb{E}^{\pi}[\phi^{`loss`}(x_h, a_h)] | \pi \in \Psi_{`span`} \\}$ essentially covers all directions in $\mathbb{R}^d$. For this reason, we need $\phi_{`loss`}$ to compute $\Psi_`span`$.

Q4: In line 10 of algorithm 1, Define $\Sigma_h^t = \sum$, anything missing before the $=$ ?

A: $\Sigma_h^t$ is the covariance matrix of time $t$ and step $h$ whose definition is on the right-hand side of ``$=$''. The $\sum$ on the right-hand side is the summation notation.

Q5: In adversarial linear MDPs, [3] performs estimation on-the-fly to get the first rate-optimal regret. I was wondering what would be the difficulty of doing similar things here (and enjoying better regrets). Could the authors point out some other places where the sub-optimality comes from?

A: Indeed, the suboptimal regret of Algorithm 1 is due to the two-stage design. The online occupancy estimation technique in [3] relies crucially on the transition feature being known. It is unclear how to extend this to the low-rank setting with unknown features. Getting the optimal regret is still a challenging open problem.

Q6: If a reference has been accepted to a conference, the authors may want to cite the conference version rather than arXiv, unless there's a significant update.

A: Thank you for the suggestion. For the case of [Mhammedi et al., 2023] in particular, the paper has significant updates on arXiv compared to their camera-ready NeurIPS version (removes the reachability assumption with different analysis). Thus, we cite both versions in our paper. We will change other references to the conference version.

Q7: In Thm. 4.1, the regret scales with the size of the function class. I think it makes some sense but any similar results in the literature?

A: For low-rank MDP, the $\log(|\Phi|)$ in Theorem 4.1 matches the best-known result in the stochastic setting [Mhammedi et al., 2023; Zhang et al., 2022b]. Most papers on low-rank MDP have worse dependence $\log(|\Phi||\Upsilon|)$ under the model-based assumption (e.g. [Agarwal et al., 2020; Uehara et al., 2022]).

Moreover, the logarithmic dependence on the size of the function class is very common in RL with general function approximation. For example, in the general decision estimation coefficient (DEC) framework, such dependence appears in both model-based (Theorem 3.3 in [Foster et al., 2021]) and model-free (Theorem 2.1/Corollary 2.1 in [Foster et al., 2023]) algorithms.

References:

[Mhammedi et al., 2023] Mhammedi, Z., Block, A., Foster, D. J., and Rakhlin, A. (2023). Efficient model-free exploration in low-rank mdps. arXiv preprint arXiv:2307.03997

[Zhang et al., 2022b] Zhang, X., Song, Y., Uehara, M., Wang, M., Agarwal, A., and Sun, W. (2022b). Efficient reinforcement learning in block mdps: A model-free representation learning approach. ICML.

[Agarwal et al., 2020] Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank mdps. NeurIPS.

[Uehara et al., 2022] Uehara, M., Zhang, X., and Sun, W. (2022). Representation learning for online and offline rl in low-rank mdps. ICLR.

[Foster et al., 2021] Foster, D. J., Kakade, S. M., Qian, J., Rakhlin, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487.

[Foster et al., 2023] Foster, D. J., Golowich, N., Qian, J., Rakhlin, A., Sekhari, A. (2023). Model-free reinforcement learning with the decision-estimation coefficient. NIPS.

Thank you for your comments. The statement of Theorem 4.1 should read as follows:

Theorem 4.1. Let $\delta\in(0,\frac{1}{T})$ be given and suppose Assumption 2.1. and Assumption 2.2. hold. Then, for $T =\text{poly}(A,H,d, \log(|\Phi|))$ sufficiently large, Algorithm 2 guarantees $Reg_T \leq \text{poly}(A,H,d, \log(|\Phi|T)) \cdot T^{5/6}$ against an oblivious adversary, where $Reg_T :=E_{\rho^{1:T}}[\sum_{t=1}^T E_{\pi^t\sim \rho^t}[V^{\pi^t}(x_1;\ell^t)] -\sum_{t=1}^T V^{\pi}(x_1;\ell^t) ]$.

Note that $Reg_T$ in this statement is a deterministic quantity; there is no randomness. The $\delta$ in the submission was just a typo.

We now explain why there is no $\delta$ in the statement above even though the analysis of Theorem 4.1 (in particular Lemma G.4 and G.5) have a $\delta$. The current analysis of Algorithm 2 implies that under the setting of Theorem 4.1, we have that for any $\delta\in(0,1)$, there is an event $\mathcal{E}(\delta)$ with probability at least $1-\delta$ under which $\widehat{Reg}\_T \leq \text{poly}(A,H,d, \log(|\Phi|/\delta)) \cdot T^{5/6}$, where $\widehat{Reg}\_{T} := \sum\_{t=1}^T E_{\pi^t \sim \rho^t}[V^{\pi^t}(x\_1;\ell^t)] -\sum\_{t=1}^T V^{\pi}(x\_1;\ell^t);$ Note that the randomness here comes from $\rho^{1:T}$.

Now, since $Reg_T = E_{\rho^{1:T}}[\widehat{Reg}_T]$ and $\widehat{Reg}_T \leq H T$, we have

$Reg\_T =P[\mathcal{E}(1/T) ] E\_{\rho^{1:T}}\left[\widehat{Reg}\_T\mid \mathcal{E}(1/T) \right]+ P[\mathcal{E}(1/T)^c ] E\_{\rho^{1:T}}\left[\widehat{Reg}\_T\mid \mathcal{E}(1/T)^c \right]\leq \text{poly}(A,H,d, \log(|\Phi|/\delta)) \cdot T^{5/6} + H,$ where we used that $P[ \mathcal{E}(1/T)^c]\leq 1/T$ and the bound on $\widehat{Reg}_T$ under $\mathcal{E}(1/T)$.

Note that the high probability bound on $\widehat{Reg}_T$ above is still not good enough for an adaptive adversary; see the answer to Q3.

We hope this clarifies things. Please let us know if you have any more questions.

Thank you for your support and valuable feedback. Your question about $poly(A)$ dependence in regrets is explained in Q1 of the global response. We answer your other questions below.

Q1: The authors should provide more discussions on the computational complexity of the proposed algorithms.

A: The main result in [Mhammedi et al., 2023] guarantees that the number of calls to the optimization Oracle within VoX is polynomial in $d$, $A$, $\log |\Phi|$, and $1/\epsilon$. Due to this, VoX is an Oracle-efficient algorithm. Since our algorithm (Algorithm 2 in this context) makes a single call to VoX, it automatically inherits its Oracle efficiency. All the other steps in Algorithm 2 can be performed computationally efficiently; in fact, the most computationally expensive step is the call to VoX.

Our Algorithm 1 is generally computationally inefficient. The computational complexity scales with $|\Pi|$ because we need to maintain exponential weights over policy class $\Pi$. For the linear policy class defined in Line 235, the computational complexity of Algorithm 1 has order $|\Phi| T^d$.

[Mhammedi et al., 2023] Mhammedi, Z., Block, A., Foster, D. J., and Rakhlin, A. (2023). Efficient model-free exploration in low-rank mdps. arXiv preprint arXiv:2307.03997

Thank you for your support and valuable feedback. Your question about why we use log-barrier is explained in Q2 of the global response. We answer your other questions below.

Q1: The first algorithm is similar to learning adversarial MDPs by reducing to learning adversarial bandits. I would suggest the authors give more comparisons and discussions between the design of the first algorithm and the algorithms in linear MDPs [1,2].

A: Our Algorithm 1 takes a different approach from reducing learning MDPs to linear bandits.

In a linear MDP with a known feature map $\phi$ and a linear loss $\ell_h(x,a) = \phi(x,a)^\top g_h$, we have: $V_1^\pi(x_1, \ell) = \mathbb{E}^\pi\left[\sum_{h=1}^H \ell_h(x_h, a_h)\right] = \mathbb{E}^\pi\left[\phi(x_h, a_h)\right]\sum_{h=1}^H g_h.$

This means that the linear MDP problem can be reduced to a linear bandit instance where the action set is $\\{\mathbb{E}^\pi\left[\phi(x_h, a_h)\right]: \forall \pi \\}$ and $\sum_{h=1}^H g_h$ is the hidden loss vector. This action set can be estimated by estimating occupancy measures; is the approach taken by [1,2]. With this, [1,2] use the standard linear bandit loss estimator with estimated actions.

The reduction to linear bandits in [1,2] relies crucially on the linearity of the loss functions. In contrast, our Algorithm 1 does not require linear losses. Instead, it only relies on the linear structure of the transitions (i.e. the low-rank structure). Moreover, since the feature maps are unknown in our setting, we cannot use the standard linear bandit loss estimator as in [1,2]. To address this, Algorithm 1 learns a representation in an initial phase, which is then used to compute a new loss estimator carefully designed for low-rank MDPs.

Q2: Why Algorithm 2 still need to operate in epochs after the phase of reward-free exploration?

A: The role of the reward-free phase is to learn a policy cover; a set of policies with good coverage over the state space. In the non-adversarial setting, once such a policy set is computed, finding a near-optimal policy is relatively easy. However, in the adversarial setting, the losses change across rounds and the algorithm needs to constantly estimate the $Q$-functions to play good actions. The algorithm uses epoch for this estimation task, where the larger the epoch (the more episodes in an epoch) the more accurate are the estimated $Q$-functions.

Thank you for reviewing our paper and for your valuable feedback. Your questions about the use of the log-barrier and the difficulty of dealing with an adaptive adversary are explained in Q2 and Q3 of the global response. We answer your other questions below.

Q1: In Algorithm 1, most of the complexity introduced by the unknown feature maps is largely addressed by leveraging existing reward-free algorithms, possibly underplaying the novelty or the specific challenges directly tackled by the new algorithm itself.

A: The main novelty of Algorithm 1 lies in the design of the loss estimators; in a low-rank MDP where the feature map is unknown, standard loss estimators used for linear MDPs fail. The challenge here is that the loss estimators have to be carefully designed to account for any errors in the learned representation from Phase 1. This is a non-trivial challenge that existing methods before our paper do not address.

Q2: Could you please clarify how (41) is obtained from Lemma G.5? It feels like some argument on the generalization gap is missing.

A: You are right. Equation (41) follows from Lemma G.4 and Lemma G.5. We will add the reference to Lemma G.4.