Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback

Thank you for the support and the valuable feedback. Please see our response below.

Q1: Why the adversary is assumed to be oblivious?

Reply: This is mostly for simplicity. Our analysis can directly obtain a pseudo regret bound for adaptive adversary, where pseudo regret is defined as $\mathbb{E}\left[\sum_{k=1}^K V^{\pi_k}\left(s_1, \ell_k\right)\right] - \min_{\pi} \mathbb{E}\left[\sum_{k=1}^K V^{\pi}(s_1; \ell_k)\right].$ If we would like to obtain the stronger expected regret: $\mathbb{E}\left[\sum_{k=1}^K V^{\pi_k}\left(s_1, \ell_k\right)\right] - \mathbb{E}\left[\min_{\pi} \sum_{k=1}^K V^{\pi}(s_1; \ell_k)\right]$ for adaptive adversary, then the standard technique is to first obtain a high probability bound for the algorithm, and then take expectations [1]. Overall, to obtain an expected regret bound for adaptive adversary, it suffices to prove a high-probability bound for the algorithm.

The standard technique to obtain a high-probability bound is to add a bonus in the update to compensate the deviation in the concentration bound. This is based on the same idea of our current algorithm (which already incorporates some bonus term to compensate the bias), but may require extra bonus terms. We do not pursue in this direction to focus the exposition more on our key contributions. We point out that the regret notion in our work is the same as those in previous work (Luo et al. 2021, Dai et al. 2023, Sherman et al. 2023b, Kong et al. 2023), and the cases the algorithms can be applied to are also the same.

[1] Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory, pages 3285–3312. PMLR, 2022

Thank you for the support and the valuable feedback. We have added a table to compare the regret bounds. Please see Appendix A. Other questions are addressed below.

Q1: Can the authors give a brief discussion about the possibility or the main barriers to achieving the rate-optimal result for PO-based methods?

Reply: We believe that it is possible to achieve optimal rate with PO-based methods. Currently, the main challenge lies in how to efficiently reuse previous data to create an covariance matrix estimator $\hat{\Sigma}_k$, and bound the bias of the loss estimator due to the error in $\hat{\Sigma}_k$. Below we give a high-level explanation on why our inefficient exponential weight algorithm is able to achieve an optimal rate, while the PO approach still faces difficulties.

Notice that the main difference between the inefficient exponential weight algorithm and the PO algorithm is that, the former runs a "global" linear bandit algorithm over all policies, while the latter runs a "local" linear bandit algorithm on every state. This difference leads to a difference in their loss estimator construction. The loss estimator in the exponential weight case is

$M_k^{-1}\hat{\phi} _k^{\pi_k}L _k$

where

$M_k = \mathbb{E}_{\pi\sim q_k}[\hat{\phi}_k^\pi\hat{\phi}_k^{\pi\top}],$

while the loss estimator for the PO case is

$\hat{\Sigma}\_{k,h}^{-1} \phi (s\_{k,h}, a\_{k,h}) L\_{k,h}$

where

$\hat{\Sigma}\_{k,h} = \lambda I + \hat{\mathbb{E}}\_{s\_h\sim \pi\_k}\left[\sum\_a \pi\_k(a|s\_h)\phi(s\_h,a)\phi(s\_h,a)^\top \right]$

and $\hat{\mathbb{E}}\_{s\_h\sim \pi\_k}$ means that we have to use empirical data to estimate the state distribution of $s_h$ under $\pi_k$. For exponential weights, the bias comes from the error of $\hat{\phi}^\pi_k$, while its covariance matrix $M_k$ can be computed exactly (since $q_k$ is known to the learner). For PO, on the other hand, the bias mainly comes from the error in the covariance matrix $\hat{\Sigma}\_{k,h}$. In exponential weights, bounding the error $\hat{\phi}^\pi\_k - \phi^\pi\_k$ is relative easier, while in PO, bounding the error $\hat{\Sigma}\_{k,h}^{-1} - \Sigma\_{k,h}^{-1}$ is more challenging because concentration inequalities for inverse matrices are more difficult to establish. Currently, we use fresh on-policy samples to estimate $\hat{\Sigma}\_{k,h}$ in epoch $k$, which is expensive. A more sample efficient option would be to reuse previously collected data to estimate $\hat{\Sigma}\_{k,h}$ in an off-policy manner. However, currently we do not know how to bound the estimation error $\hat{\Sigma}\_{k,h}^{-1} - \Sigma\_{k,h}^{-1}$ tightly if adopt this approach.

Thank you for the support and the valuable feedback. Please see our response below.

Q1: The pseudo-code of algorithm 1 lacks explanations.

Reply: The explanation of Algorithm 1 is provided in Page 5 between Eq.(6) and Lemma 5. Please feel free to let us know if the exposition there requires further improvement.

Q2: What is the practical motivation of this problem?

Reply: Our work follows the line of research by (Luo et al. 2021, Dai et al. 2023, Sherman et al. 2023b, Kong et al. 2023) that investigate the intersection of function approximation, non-stationary reward, and the design of exploration bonus on top of them. The main goal of this line of research is to improve the weak part of traditional policy-based algorithms --- having low sample efficiency, only performing local policy search --- through the use of exploration bonus, while keeping its strength of being robust to non-stationarity. Indeed, simultaneously ensuring sample efficiency and robustness in changing environments is crucial for fields such as robotics. We agree that currently this line of research is theory-oriented, but some techniques that have been developed (e.g., the use of the initial exploration phase to reduce the required exploration bonus, and the recursive construction of the exploration bonus) could provide insights for future empirical study.

Q3: With the help of simulators, $K^{2/3}$ regret can be obtained, what is changed when the simulator of the environment is available?

Reply: We point out that the state-of-the-art regret bound with a simulator is $\sqrt{K}$ by Algorithm 1 in [1].

With the help of a simulator, the learner can learn the transition directly from the simulator without interacting with the environments (assuming the simulator is unbiased). This saves the number of interactions with the environments. Specifically, for our Algorithm 2, if there is a simulator, the estimation of the covariance matrix can be free and with low error. This also eliminates the need for the initial exploration phase because the original goal of the initial phase is to reduce the bias caused by the covariance matrix estimation error. Overall, if there is a simulator, our policy optimization algorithm can actually achieve a $\sqrt{K}$ regret, like in [1].

[1] Yan Dai, Haipeng Luo, Chen-Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. In International Conference on Machine Learning, 2023.

Thank you for the support and the valuable feedback. Please see our response below.

Q1: Can the authors discuss the possibility of designing an algorithm with a minimax-optimal regret guarantee? Such a result has already been established in [1,2] for linear mixture MDPs with/without adversarial losses, with the full information feedback. [2] also established a lower bound of regret which depends on $\log{|\mathcal{S}|}$ and $\log{|\mathcal{A}|}$. Does the same lower bound also hold for the bandit feedback setting?

Reply: The main differences between our setting and those of [1, 2] are the following:

(1) They study full-information loss feedback, while we study bandit loss feedback;

(2) Their linear mixture MDP only assumes linear structure on the transition ($\mathbb{P}(s'|s,a) = \phi(s'|s,a)^\top \psi$), while our linear MDP assumes linear structures both on the transition ($\mathbb{P}(s'|s,a) = \phi(s,a)^\top \psi(s')$) and the loss ($\ell_k(s,a) = \phi(s,a)^\top \theta_k$). Notice that the assumptions on the transition are different -- in linear mixture MDP, it's possible to use a model-based algorithm to estimate the the transition, while in linear MDP this is not allowed.

The algorithmic techniques required for linear mixture MDPs and linear MDPs are quite different due to the different assumptions. Therefore, the bounds obtained in one setting cannot be translated or compared to the other setting in general. We note that a concurrent work [2] studied a more comparable setting of adversarial linear MDPs with full-information loss feedback. They obtained a regret of $\sqrt{d^4H^6 K}$ (also the first rate-optimal result), while ours in the bandit setting is $\sqrt{d^7H^7 K}$. Clearly, in both works, there is still a significant gap between the upper bounds and the currently best lower bound $dH\sqrt{K}$. We believe that the lower bound is tight. Potential ways to improve our upper bound include:

• In Algorithm 1, try NOT to control the estimation error for all functions in the function set $\mathcal{F}_\pi$ (which requires an union bound over an exponentially large function set); instead, just control the error for those $f$ that are relevant to the estimation of $\phi^\pi$.

• Improve the upper bound for the bias term in Lemma 10 -- we believe that a more refined and complicated analysis could improve the $d$ dependence there.

To implement these ideas, significant changes in the analysis and the algorithm may be required, so we leave it as future work.

Next, we remark on the $\log|\mathcal{S}|$ and $\log|\mathcal{A}|$ lower bound established in [2]. The key reason that they have explicit $|\mathcal{S}|$ and $|\mathcal{A}|$ dependencies is that in their linear mixture MDP model, there is NO structural assumption on the loss function $\ell_k(s,a)$ (see (2) above). Therefore, their $\ell_k(s,a), \ell_k(s',a')$ can be arbitrarily different even if $\phi(s,a)=\phi(s',a')$. This makes the intrinsic dimension of their $\ell_k(s,a)$ scales with $|\mathcal{S}||\mathcal{A}|$ (though the full-information assumption make their regret dependency only logarithmic). On the other hand, in our linear MDP model, $\ell_k(s,a)$ can be represented as a $d$ dimensional linear function. Therefore, our bound can only depend on $d$ but not on $|\mathcal{S}|$ or $|\mathcal{A}|$.

[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. Conference on Learning Theory. PMLR, 2021.

[2] Ji, Kaixuan, et al. Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs. arXiv preprint arXiv:2305.08359 (2023).

[3] Uri Sherman, Alon Cohen, Tomer Koren, Yishay Mansour. Rate-Optimal Policy Optimization for Linear Markov Decision Processes. arXiv preprint arXiv:2308.14642 (2023).