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

Summary

This paper studies online learning in low-rank MDPs with adversarial losses (having linear structure), and derives a set of regret guarantees: 1. A model-based and inefficient algorithm ensures $T^{2/3}$ regret, assuming the loss feature vector is unknown. The algorithm has a two-stage design: the first stage is an initial reward-free exploration stage from [1] to ensure low estimation error for the second (exploitation) stage. 2. A model-free and oracle-efficient algorithm ensures $T^{5/6}$ regret, assuming the loss feature vector is unknown. This is thanks to recent advances in exploration for low-rank MDP by [2]. 3. A model-free and oracle-efficient algorithm ensures $T^{5/6}$ regret against adaptive adversaries, assuming the loss feature vector is known, by leveraging a representation learning algorithm from [2].

Strengths

By adopting recent progress in representation learning and low-rank MDP from the literature, the paper provides a set of results for low-rank MDPs with adversarial (linear) losses under bandit feedback. This is the first set of results for the more challenging bandit feedback.

Weaknesses

I overall appreciate the contributions from this work, in which the authors take advantage of SOTA techniques in the literature, but also with some original adaptations, to give a complete picture on regret bounds in a new setup. However, I think the author could do a better job in presentation and delivering insights, which may make readers benefit more from reading this paper. Below are some questions that I think should be made clear(er) in the paper (and I don’t get an answer after reading the paper): 1. Maybe I missed it somewhere, but what is exactly the “oracle” that is referred to throughout this paper? Is it hidden in the VoX algorithm? 2. Even with linear loss struction, the regret still has to be $\Omega(\sqrt{A})$, is this a common result in the low-rank MDP literature, or unique due to the adversarial losses (and bandit feedback)? 3. 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? If so, why is the way of stating a high-prob. bound in Thm. 4.1 different from that in Thm. 5.1? If not, then the use of notation $\delta$ is not consistent in the paper. 4. What’s the difficulty of obtaining regret bounds against adaptive adversaries, without knowing the loss feature map? In section 5, the sentence “Given the difficulty of this setting, we make the additional assumption” fails to yield a smooth transition, as I don’t get the connection between the difficulty (it’s not even clear what it is) and the need for the assumption. 5. Does the difficulty 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? 6. If algorithm 4 is mostly from other papers and there’s no novel modification, the authors may consider moving it to appendix to save some space in the main body for more informative messages. 7. In line 10 of algorithm 1, “Define $\sum_h^t = \sum$”, anything missing before the $=$? 8. Sketched proofs in the main body for deriving regret bounds would be very helpful, but I fully understand it due to the page limit. 9. 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. I will consider increasing my rating to 6 and supporting acceptance if the authors can address these questions so that I can have a clearer understanding of the results.

Questions

Questions here are mainly for curiosity and will not affect my recommendation/rating much. 1. Typically, such two-stage design (initial exploration for warm-up + standard online learning) may not give rate-optimal guarantee. 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? 2. 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? References [1] Cheng, Yuan, Ruiquan Huang, Yingbin Liang, and Jing Yang. "Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs." In The Eleventh International Conference on Learning Representations. 2022. [2] Mhammedi, Zakaria, Adam Block, Dylan J. Foster, and Alexander Rakhlin. "Efficient Model-Free Exploration in Low-Rank MDPs." arXiv preprint arXiv:2307.03997 (2023). [3] Liu, Haolin, Chen-Yu Wei, and Julian Zimmert. "Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback." In The Twelfth International Conference on Learning Representations. 2023.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

In the checklist, it says "The paper discuss the limitations of the work in the discussion section", but I didn't find a section named "discussion". ====== update after author-reviewer discussion ====== During the initial rebuttal and the discussion phase, the authors addressed my clarification question, so as of now I increase my score from 5 to 6

Summary

This paper studies adversarial Low-Rank MDPs with unknown transition and bandit feedback. The authors give three main results, targeting either tighter regret or computational efficiency. The authors show that the linear structure of the reward function is necessary for the case of bandit feedback to achieve regret without dependence on the number of states.

Strengths

1. The paper addresses a novel and challenging problem of adversarial Low-Rank MDPs with unknown transition and bandit feedback. The problem is well-motivated and has practical implications in real-world applications. 2. The theoretical results are strong and the analyses are sound. The authors provide a comprehensive analysis of the proposed algorithms and prove the theoretical guarantees. The authors combine several techniques to handle the unknown transition and bandit feedback, which is non-trivial. 3. The paper provides a lower bound to show we could not gain too much from a low-rank transition structure compared with tabular MDPs. This lower bound is insightful and provides a clear motivation for the linear reward structure in the bandit feedback setting.

Weaknesses

1. The computational cost of the proposed algorithms is huge, even for the oracle efficient algorithms. The authors should provide more discussions on the computational complexity of the proposed algorithms. 2. Though this paper is the first work to study adversarial Low-Rank MDPs with unknown transition and bandit feedback, the $O(T^{5/6})$ regret bound is not very satisfying. Moreover, the results have a linear dependence on the number of actions, which is not ideal.

Questions

1. Is polynomial dependence on the number of actions necessary? Can the authors provide some intuition about the reason or discuss the possibility of improving the dependence on the number of actions?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

This work initiates the study on learning adversarial low-rank MDPs with bandit feedback. The authors propose an inefficient algorithm with $T^{2/3}$ expected regret, and an oracle-efficient algorithm with $T^{5/6}$ expected regret. Further, the authors also show an oracle-efficient algorithm with $T^{5/6}$ high probability regret.

Strengths

1. This work further advances the understanding of learning adversarial MDPs with general function approximation and the algorithmic designs are of interest.

Weaknesses

1. The first algorithm is generally hard to be implemented due to its computational intractability and thus might be less appealing to practitioners in the area. Besides, the algorithmic design of the first algorithm is similar to those of [1,2] in the sense that learning adversarial MDPs is somewhat reduced to learning adversarial bandits by running exponential weights over the policy set of the corresponding MDP. I would suggest the authors give more comparisons and discussions between the design of the first algorithm and the algorithms in [1,2]. [1] Kong et al. Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization. TMLR, 24. [2] Liu et al. Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback. ICLR, 24.

Questions

1. In Eq. (12), log-barrier instead of the common Shannon entropy regularizer is used in FTRL. Is this due to that it is not feasible to bound the stability term in the analysis of FTRL when using Shannon entropy caused by the possibly very large magnitude of the constructed $Q$-function estimates? 2. Intuitively, what is the reason that Algorithm 2 still needs to operate in epochs after the phase of reward-free exploration?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Not applicable.

Summary

The paper explores regret minimization in low-rank MDPs with adversarial bandit loss and unknown transitions. This means that the transition can be expressed as $P(x' \mid x,a ) = \phi^\star (x,a)^T\mu^\star(x')$ for some unknown $\phi^\star$ and $\mu^\star$ and the loss is also linear in $\phi^\star$. They consider three distinct settings: 1. **Model-based setting**: Here, the authors assume access to function classes containing $\mu^\star$ and $\phi^\star$. They use some reward-free algorithm to obtain $\mu$ and $\phi$ that approximates the dynamics well, and then run EXP2-style algorithm on some $\epsilon$-cover of the class of linear policies. This algorithm is computationally inefficient and achieves $T^{2/3}$ regret, with some logarithmic dependencies on the size of the function classes. 2. **Model-free setting**: In this setting, they don't assume access to a class that contains $\mu^\star$. Once again, the algorithm begins with some of-the-shelf exploration phase that aim to find a policy cover. That is, a (small) set of policies that guarantees some sense of minimal reachability to all reachable states. Next, they run an FTRL-style algorithm in each state with log-barrier regularization on blocks of certain size. Within each block, the algorithm plays the policy derived from the FTRL, mixed with a uniform policy from the policy cover. The policy cover's exploration guarantee allows for good least-squares estimation of the Q-function for the policy employed in that block, subsequently used in the FTRL. This achieves $T^{5/6}$ regret against oblivious adversary. 3. **Model-free setting with Adaptive adversary**: Here, the adversary adjusts their strategy based on the learner's actions, and there is additional assumption that the the loss features are known (and the dynamics feature map is still unknown). The algorithm is similar to the algorithm in 2. but adds some representation learning algorithm on top of the reward-free algorithm which suggested to be beneficial against adaptive adversary. The regret bound obtained in this setting is also of order of $T^{5/6}$.

Strengths

- Low-rank MDPs and representation learning are important areas of study in reinforcement learning, particularly due to the relevance of representation learning to deep RL. The paper advances research in this regime by extending previous results from full-information settings to bandit feedback. - The paper introduces three algorithms, each tailored to a distinct setting. These algorithms manage to achieve similar regret guarantees to previous works that dealt with the full-information case (although the settings are not directly comparable). Additionally, the authors provide a compelling justification for why they cannot handle arbitrary (non-linear) loss as in the full-information case by presenting a lower bound that scales with the number of states.

Weaknesses

- The approach taken in Algorithm 1 is somewhat generic, employing an off-the-shelf reward-free exploration phase followed by an inefficient EXP2 algorithm. 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. - Section 5 lacks detailed explanations. The section does not adequately clarify what specifically becomes more challenging in the adaptive adversary setting, nor does it thoroughly explain how the spanner policies effectively address these challenges. The description merely states that these policies are necessary *"because the estimation of the Q-functions becomes much more challenging with an adaptive adversary"*. This lack of detail leaves the reader without a clear understanding of the problem mechanics or the solution’s efficacy in this context.

Questions

Could you please clarify how (41) is obtained from Lemma G.5? (41) bounds the average distance, while, to my understanding, G.5 bounds the distance on the data. It feels like some argument on the generalization gap is missing. - Is there a specific reason to use log-barrier and not negative entropy regularization in algorithm 2?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

As far as I'm concerned, the authors address most of their limitations.

Regarding Q2 and Thm. 4.1

I thank the authors for the response. How Thm 4.1 should be corrected is still unclear to me from the response. Could the authors state the corrected Thm 4.1 in this thread? Also, what is the role of $\\delta$ (confidence parameter) here? What happens if we make it very small (close to 0) or large (close to 1)?

Thank you for your response.

I thank the authors for their response and have no further questions.