Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides the first information-directed sampling (IDS) algorithm with theoretical guarantees for the learning in episodic MDP in the prior free setting. The assumptions are the following: the reward function is deterministic and known to the learner and the transition probabilities in the MDP are unknown and are sampled from a known prior distribution before the first episode begins. Authors considers two types of setups: all presented algorithms works in a tabular setting and some results also extended to work in the linear MDPs. The performance of the learner is measured by a Bayesian regret. 
strengths_and_weaknesses: This works adapts the idea of IDS to the setting of learning in the MDP and the authors present three algorithms to tackle this problem. For the first algorithm proposed, Vanilla IDS, the idea is to introduce a notion of the “environment”, which hides in it all the randomness of the unknown parameters of MDP’s transitions and define the information ratio for a policy \pi as the ratio between the square of expected difference of the value function of optimal policy and the value function of policy \pi, divided by the information gain of the “environment” variable and a the history of episode ℓ up to layer h produced by a policy \pi, all conditioned on the history. To find a \pi, that achieves the minimum information ratio, the learned has to optimize over the full policy space, which is a computationally costly. The analysis is simple and borrows the tricks from the literature, as the decomposition of regret based on the marginal posterior distribution of  “environment” (line 145) and a trick with the ratio of occupancy measures (Lemma D.3), but all together it gives the first regret bound of this kind.    
Next, authors propose Regularized-IDS algorithm, where instead of computing the ratio, authors propose to compute the sum of the arguments of Vanilla IDS. The result of this chapter is that the 
 Regularized-IDS can be efficiently computed using the samples from the posterior which gives the augmented MDP and has the same regret bound as Vanilla IDS. 
Finally, the author improve the regret bound of Regularized-IDS  and Vanilla IDS, which they show can be achievable by Surrogate-IDS algorithm. The idea of this algorithm is to construct a surrogate environment, which would be an \epsilon approximation of the true “environment” variable and then compute the information ratio which would be computed over this approximated environment. This algorithm is not computationally efficient, but it improves the dependence of the regret bound on S. Also, the discretisation approach allows to extend the results obtained for episodic MDP to linear MDP, as the number of the set in the partition of the environment space does grow as the covering number of the bounded set in R^d. 


I find it especially interesting how similar techniques works in the analysis of this paper and [Foster et.al 2021],  since it give another evidence that the decision-estimated coefficient is related to the information ratio. 

questions: In some places the definition of variables are omitted, please check it. 
- Definition of \bar{\Epsilon}_l is recursive
-  zeta in the proof of B.1 is undefined
-  the way of defining \pi_{TS}^l is confusing as this policy is only used in the proof and no presented algorithms use it to compute the actual policy. 

Minor remarks

- for the clarity, it has to be mentioned in the preliminaries that the prior is assumed to be known to the learner
- Partition should depend on \epsilon
- In equation (3.3), \pi is missing from I_{\ell}

limitations: The main limitation of the proposed algorithms is that they are not computationally efficient.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies information-directed sampling (IDS) for Markov decision processes. In particular, the authors prove the Bayesian regret bound of IDS for finite horizon tabular MDPs and linear MDPs. 

strengths_and_weaknesses: The writing of the paper is clear and the proofs seem to be sound. While I appreciate the comparison of the regret bound with other methods in the literature, I do not think it is proper to compare the Bayesian regret bound derived in this paper with the frequentist regret bound in other papers. Special comments should be carefully made around any of these remarks.

questions: Since $\mathcal{S}, \mathcal{A}$ and $r_h$ are assumed to be known and deterministic, the expectation over the environment $\mathcal{E}$ is just the expectation over the prior of the transition probabilities?

limitations: Line 51: it would be more convincing to include some cases where the best UCB-type algorithms are sub-optimal.

One potential drawback of the paper is its lack of a specific example for calculating the information ratio and the sample complexity for estimating it, which makes it hard to understand the advantage of using IDS policy in practice. 

Line 177: conditionar => conditional
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents general guarantees for information directed sampling in MDPs. As it stood, prior work had only understood Thompson-Sampling inspired approaches in frequentist settings, or provided bounds for specific priors, but this is the first work to analyze proper IDS for MDPs with no restrictions on the prior.
strengths_and_weaknesses: Strengths: the bounds in this paper apply to general priors, some of the information bounds based on the method of mixtures may be of independent interest, a regularized variant of IDS can be implemented efficiently given access to a natural sampling oracle. In addition, the paper is generally well written and well explained, despite a couple of minor grammatical issues. Authors do a great job explaining what the essential ingredients are of their proofs.

The refinements due to rate distortion theory were also a nice addition.

Weaknesses: I should preface this by saying that I am not an expert on Bayesian regret bounds; hence it is hard for me to gauge the technical contribution of this paper. However, it does seem that the techniques and arguments are rather standard, and I think it would be useful for the authors do explain not just the *results* derived in prior works, but to give a sense of how common (or unique) their techniques are in comparison to the rest of the Bayesian regret community. 

In addition, it seems that the bounds here do not match what is attainable in the (harder) frequentist setting. This makes me wonder - either is (a) the analysis loose, or (b) can one derive lower bounds to show that IDS (without modification) necessarily suffers this worse sampling complexity? Even some numerical experiments demonstrating scaling with S would be illustrative here. 

Another weakness is that the sharper guarantees required computing an explicit cover, which is computationally prohibitive. I would have been more excited if the refined regret were attainable with computationally efficient algorithms.
questions: Do the authors conjecture that the suboptimality of their regret is a limitation of the analysis, or the algorithm? To they have any analysis or experimental evidence to shed light on this? Moreover, have the authors thought about what a more computationally efficient algorithm which uses the MDP cover would look like?
limitations: As noted, regret bounds are suboptimal, refined bounds are not computationally efficient.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors studied the provable efficient Information-Directed Sampling (IDS) methods in MDP setting. They first proposed vanilla-IDS and then derived a prior-free Bayesian regret bound for it. After that, for the sake of computational efficiency, they proposed another variant called regularized-IDS. Besides, they improved the regret bound by learning a surrogate environment. Beyond the tabular setting, they also extended their results to linear MDP.
strengths_and_weaknesses: ### Strengths

This paper has an important contribution to understanding IDS methods in the MDP setting. The algorithm and analysis look novel and interesting. The paper writing looks good to me.


### Weakness

I only have a small issue about the rigorousness in the discussion related to $\Gamma^*$ in Sec. 3.1 and related proof.

It seems to me that $\Gamma_l(\pi^l_{IDS})$ is not a constant across $l=1,2,...,L$, while $\Gamma^*$ is defined to be the worst-case information ratio and upper bounds $\Gamma_l(\pi^l_{IDS})$ for all $l\in[L]$. As a result, there might exists some $\bar{l},\tilde{l} \in [L]$, such that $\Gamma^*$ is attained at $\bar{l}$, but at $\tilde{l}$, we have $\Gamma_{\tilde{l}}(\pi^\tilde{l}_{IDS}) < \Gamma^*$.

Therefore, although we always have $\Gamma_l(\pi^l_{IDS}) \leq \Gamma_l(\pi^l_{TS})$, it is possible that $\Gamma_l(\pi^l_{IDS}) \leq \Gamma_l(\pi^l_{TS}) < \Gamma^*$ when $l=\tilde{l}$. As a result, I think the argument $\Gamma^* \leq \Gamma_l(\pi^l_{TS})$ (Line 482 in the proof of Lem. 3.2) is not correct (but I guess one can recover the same regret upper bound without introducing $\Gamma^*$ and therefore there will be no such issue).

If the authors can fix the issue I mentioned above, I would like to increase my score correspondingly.
questions: Please check the **Weakness** section above.
limitations: N.A.
review_title: null

Meta-review: metareview: This paper has been well-received by the reviewers already in the initial round, and the reviewers were all happy with the authors' responses. The updates already made to the manuscript clearly showed the commitment of the authors to take all the reviewers' comments into account for the final version. After some discussion, all reviewers agreed that the paper should be accepted for publication at NeurIPS 2022. I encourage the authors to finalize the promised changes for the camera-ready version, and in particular complete the preliminary experimental section provided in the revision.
confidence: Certain
Decision: Accept