Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies online learning in linear MDPs with bandit feedback and adversarial losses, and a known transition kernel. The regret bound against the best policy is of order $\sqrt{dHT}$. The proposed algorithm is an extension of Q-REPS of Bas-Serrano et al. which previously only works for the standard tabular setting. The authors claim that Q-REPS has computational advantages over O-REPS: despite the fact that the state and action space can be arbitrarily large, solving the optimization problem in each step only requires poly(d) computation. 
main_review: Although the strong assumption on the known transition kernel simplifies the problem a lot, the setting of adversarial bandit linear MDP has not been studied before, and the authors propose an interesting algorithm to tackle it. I like the fact that the authors make the algorithm as transparent as possible by detailing every sub-procedure e.g. Matrix Geometric Resampling and how to solve the convex programming using gradient descent. However, I suspect that there is some mis-presentation in the main result, as I pointed out below. I would like to see authors address it in the rebuttal (either modifying the algorithm, or weakening the claimed bounds). 

As I can see, the regret bound should actually scale with $\sqrt{\frac{T}{\lambda_{\min}}}$, but not the $\sqrt{T}$ given in Theorem 1. The reason is that in Lemma 1, it is required that $\eta$ is smaller than the order of $\frac{1}{\beta M}$ (because the magnitude of $\widehat{\theta}$ can be as large as $\beta M$). A similar condition (i.e., $\eta\leq \frac{2}{(M+2)H}$) is also specified in Theorem 1. Then the $\frac{1}{\eta}D(\mu^*\|\mu_0)$ will scale at least with $\beta M$. Now in order to make the first regret term $2T\sigma RH\exp(-\gamma \beta\lambda_{\min}M)$ sublinear, one must pick $M=\Omega\left(\frac{1}{\gamma\beta\lambda_{\min}}\right)$. So the regret term $\beta M$ is at least $\Omega\left(\frac{1}{\gamma \lambda_{\min}}\right)$. Further considering another regret term $\gamma HT$, the regret will scale at least with $\sqrt{\frac{T}{\lambda_{\min}}}$. 

In practice the learner has no way to know $\lambda_{\min}$ and set $M$ and $\epsilon$ properly.  The authors should discuss how the algorithm works when $\lambda_{\min}$ is unknown. 


========== after the discussion phase ==========

The authors agreed to write their bound in the clearer form of $\sqrt{\frac{T}{\lambda_{\min}}}$, and discuss the difficulties of removing $\lambda_{\min}$ assumption in the MDP setting.  These make the paper more complete, so I slightly raised my score.  

limitations_and_societal_impact: The assumption on $\lambda_{\min}$ and the related statistical or computational issue are not emphasized or discussed in detail. It should be more emphasized in e.g. introduction section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of online learning in a finite horizon MDP with known transition function and adversarially changing rewards at each episode and only bandit feedback from those rewards. In particular, the authors consider the case when the state space is large warranting linear function approximation with the assumption that the MDP is a linear MDP with a known feature map. The proposed method is essentially a follow-the-leader algorithm using estimated rewards, which are found by estimating the parameter of the reward function.
main_review: Overall, I think this is a good paper. It is very well-written and tackles an interesting open problem in the field. The related work and introduction are detailed and comprehensive and do a good job of making the contributions of the paper clear. The assumptions are repeatedly described. The regret bound is interesting and significant in that the authors show that sqrt{dHT} regret is possible in this difficult setting. Although the proposed method combines ideas from several prior works, I do not think that this is necessarily bad and it does not seem to detract from the quality of the result.

As the authors point out, the main limitation is that the results apply only in the case where the transition function is exactly known and it is not clear how this might extend beyond. That being said, I still think this setting is important to understand.

The other limitation is that the regret bound depends on the divergence between the initial and optimal distributions, which I do not think is always needed in tabular cases, so this would be interesting to address in future work. It is pointed out that the bound has no dependence on the minimum eigenvalue, but I actually think this would be preferable to the divergence since the latter is asking for something akin to “good coverage” which is immutable in the problem while the former is asking only for a good model, which could be chosen by a practitioner even without good coverage.

Other questions & suggestions:

While it is not strictly necessary, I think that the result of Theorem 1 would feel more complete if one could see exactly the effect of the optimization error of solving G, for example, in terms of samples as described in Appendix C. Right now there is an epsilon that represents this in the main theorem. However, since a great deal of the motivation is tractability, perhaps a corollary would be helpful even though this would just be a simple calculation.

In Lemma 8 in the appendix, doesn’t one need a uniform convergence guarantee since the goal is to minimize over \hat{G}? The statement looks like it holds only for a single Z, but the proof seems to handle it more generally. Also, when can one expect that Delta is bounded? 

Is there anything wrong with simply plugging the optimization problem (5) into an off-the-shelf solver if one were to implement this practically instead of solving the unconstrained optimization problem? It is my understanding that many solves can handle relative entropy objectives and the constraints seem tame enough. There is some discussion already about it potentially being intractable, but in what way is this the case? Too many states/actions? or something inherent about objective/constraints?

limitations_and_societal_impact: See main review for limitations and suggestions.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a theoretical approach for online learning in Markov decision processes (MDPs) with time-varying adversarial rewards and infinite, and possibly continuous, state spaces. The proposed approach is based on linear assumptions on the structure of the MDP and approximate solutions of a linear programming problem. Theoretical regret bounds and discussions on the implementation of a tractable algorithmic solution are provided.
main_review: The paper is mostly well written and presents the solution to a problem relatively unexplored in the literature: online learning in MDPs with adversarial rewards over infinite/continuous state spaces. The presentation of the method is mostly rigorous in its mathematical formulations with clear theoretical justifications. However, the paper still has a few remaining clarity issues, which I elaborate below.

Issues:
- The first half of the introduction lacks citations/references to back up some of the claims (e.g., lines 21 and 24).
- The second half of the introduction (line 41 onwards) could be labelled as a "related work" section to better structure the paper.
- $K$ is introduced without prior definition in line 52.
- The notation $\tilde{O}$ is not defined, though it's commonly applied to indicate suppression of log-factors in the big-$O$ notation.
- In the preliminaries section, the reward function is first introduced as if it was stationary (see line 97), but it is later on considered to be varying across time step and episode.
- It is not totally clear whether the algorithm can achieve a vanishing regret as $T \to \infty$, since this would imply that both $\eta \to 0$ and $\alpha\to 0$, i.e., the optimisation problem in Theorem 1 would have to be solved up to arbitrary precision. Could the authors comment on that?
limitations_and_societal_impact: Limitations are discussed in Sec. 5. Societal impact is not directly applicable, as this is a purely theoretical work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study the adversarial linear bandit problem under bandit feedback. When the dynamics is known, the authors propose a computationally efficient algorithm to achieve low regret.
main_review: I have read an earlier version of this paper, where the authors assume access to a simulator to conduct matrix geometric resampling without assuming known dynamics. Although assuming knowing the dynamics sounds weaker, I actually like the new version since the assumption is clear and more reasonable -- Actually, I think assuming a simulator in an online problem with adversarial reward sounds super wired. Also I think authors may want to add more discussion to highlight the improvement in the new version, which would be very helpful for reviewers like me.

I have some other comments:
 
1. When assuming the known dynamics, in principle we can compute the "covariance matrix" explicitly. The authors claim this is hard. They may want to add some explanation to at least convince the reader this is hard, which is not clear to me at first glance. This will also highlight the significance of the resampling procedure.

2. When finding Z_t, a minimization problem (6) needs to be solved. It would be great if the authors can add some intuition in the main text why this can be done in a computationally efficient manner. In particular, since it contains a summation of S terms and S could be very large, why the overall complexity only depends on d?

3. The decision variable used is a pair (mu,u). Why using this pair is superior to only using mu? Since both of them are constrained by some linear constraints, I can't see intuitively this is the case.
limitations_and_societal_impact: The authors have adequately addressed them.
review_title: null

Meta-review: Several reviewers increased their scores after the discussion phase.
Overall, we agree that this paper makes solid contribution to the direction of online learning MDPs.
Please do implement the promised revisions, especially those related to the discussion with Reviewer hYYK. 

Decision: Accept (Poster)