Model-free Posterior Sampling via Learning Rate Randomization

Summary

The paper introduces Randomized Q-learning (RandQL), a novel model-free algorithm for regret minimization in episodic MDPs. Leveraging a new idea of learning rate randomization, two respect algorithms are proposed for tabular and non-tabular metric space settings, achieving near-optimal regret upper bound. Proof-of-concept experiments are conducted.

Strengths

- The concept of learning rate randomization is very interesting, which enables the algorithm to explore without bonuses. - Near-optimal regret upper bounds are obtained, showing the efficiency of proposed algorithms. - Empirical results show that the algorithm outperforms the existing model-free approach (OptQL) and support their theoretical results.

Weaknesses

- The experiments are too simple. Although the theoretical contribution of this paper has outweighed the limited empirical verification and made this paper relatively solid, conducting additional experiments on more complex environments would be advantageous and could further enhance the overall research. - I was unable to find an explicit explanation of the intuition of the value of $J$. It would be helpful to understand the implications if $J$ is too small or too large. I noticed that you set $J$ to be of logarithmic order, but a high-level explanation of this choice would be beneficial. - The policy $Q$ value $\overline{Q}_h(s_h,a_h)$ is computed by taking the maximum of $J$ temporary $Q$-values. Will it incur a large estimation error? Recall that in double Q-learning, one common trick is to take a minimum of two networks in order to reduce the estimation error. Although I am not sure how this issue affects your theoretical analysis, this seems a real problem in practice. - The Net-Staged-RandQL replies on the exact computation of covering, which may be considered a drawback. However, it is worth noting that many existing works also depend on this computation, suggesting that it could be an acceptable requirement.

Questions

While most questions are shown in the "weaknesses" section, there are a few additional smaller questions: - In Line 141, shouldn't $\overline{V}_h^{n+1}$ be computed from $\overline{Q}^{n+1}_h$? Is it a typo? - What is the intuition of setting $r_0=2$ (e.g., in line 210)?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

No negative societal impact was identified.

Summary

This work aims to develop computationally efficient, posterior sampling-style, model-free RL algorithms. They propose a family of algorithms based on the idea of learning rate randomization, which they show are able to provably learn and mimic to some degree the updates of posterior sampling. In the tabular setting, they show that the regret of this approach scales with $O(\sqrt{H^5 SAT})$. They also extend the approach to RL in metric spaces, and show that their algorithm is provably efficient in that setting as well.

Strengths

1. The algorithmic technique (exploration via learning rate randomization) presented here is interesting and to my knowledge novel. A common technique in RL is to add bonuses to the value function estimates to induce exploration via optimism. A related approach inspired from posterior sampling is to randomize the rewards in training, which has been shown to induce exploration and is provably efficient. Rather than adding bonuses or randomizing rewards, this paper instead induces exploration by updating the $Q$-function at each step with a random learning rate with carefully chosen distribution. They show that the resulting $Q$ function has a form very similar to that which would be generated by posterior sampling, and that that the algorithm is provably efficient. 2. To my knowledge there are no existing works which propose provably efficient posterior sampling-inspired algorithms for RL in metric spaces, so the results in this setting are the first of their kind. 3. The technique of learning rate randomization proposed here seems like it could be implemented in a straightforward way in deep RL algorithms, and may therefore have practical implications (though this is not explored in this work---some experiments are given, but these are restricted to gridworld environments). 4. Experimental results demonstrate that on gridworld MDPs the approach proposed here performs better than OptQL (but worse than model-based algorithms).

Weaknesses

1. This work is motivated by noting that “a provably tractable model-free posterior sampling algorithm has remained a challenge”. However, I’m not entirely sure this is correct. The RLSVI algorithm of (Russo, 2019) is inspired by posterior sampling, is computationally efficient, and is model free (in that it never requires computing or storing an estimate of the transition dynamics). While I do think the algorithmic techniques are interesting and the extension to the metric RL setting is novel, it’s not clear to me what the contributions of this paper are beyond that. 2. The guarantee obtained in the metric RL setting does not scale with the zooming dimension, but instead scales with the ambient dimension. While this is optimal in the worst-case, in general one would hope to see a scaling in the zooming dimension for learning in metric spaces (as is shown, for example, in (Sinclair et al., 2022)). 3. Furthermore, in the metric RL setting the proposed approach is not in general computationally efficient (as the computational complexity scales with $N_\epsilon$, which in general could be exponentially large in the dimension). In contrast, the metric RL algorithm of (Sinclair et al., 2022) is computationally efficient. Both this and the previous issue arise because the algorithm applies a fixed rather than adaptive discretization technique. 4. The assumptions required in the metric RL setting (in particular Assumptions 2 and 3) are somewhat stronger than what has been required in previous work on metric RL (Sinclair et al., 2022). I do not believe the extra assumptions are that restrictive, but some more discussion on them would be helpful. 5. It would greatly strengthen this paper if experiments could be provided using learning rate randomization on deep RL benchmarks, and illustrating that this approach is able to effectively induce exploration in such settings. 6. It would also be helpful to include the algorithm of (Russo, 2019) in the experimental evaluation of Section 5.

Questions

Please clarify the contributions of this paper and why the algorithm of (Russo, 2019) does not satisfy the desiderate (in the tabular setting).

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

Yes.

Summary

The paper introduces a novel algorithm for regret minimization in episodic Markov Decision Processes. The proposed algorithm, RandQL, achieves optimistic exploration without using bonuses, relying on learning rate randomization. The authors provide theoretical analysis of the algorithm's regret bound and demonstrate its effectiveness in experiments.

Strengths

1. The paper presents a novel algorithm that achieves optimistic exploration with learning rate randomization. 2. Both theoretical analysis of the algorithm and experimental results are provided with discussions to compare with baseline methods.

Weaknesses

1. Lack of baseline comparison: using ensembles of Q values is not new, for example, bootstrapped DQN [1]. It would be an essential baseline method to show the potential difference in learning rate randomization compared with other ensemble methods. 2. The experimental section would benefit from a more complex setting other than the grid world, for example, the chain environment in [1] which requires some “deep” exploration. [1] Deep Exploration via Bootstrapped DQN. Ian Osband, Charles Blundell, Alexander Pritzel, Benjamin Van Roy

Questions

1. If the learning rate randomization is to approximate the posterior distribution, how is it different from other ensemble methods like bootstrapped DQN[1], which also uses multiple Q values to estimate the posterior distribution? 2. The proposed method does not necessarily need to be restricted in the tabular case, is it possible to extend it to more practical scenarios since its advantage also comes from computation?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

The paper titled Model-free Posterior Sampling via Learning Rate Randomization proposes a novel model-free algorithm called Randomized Q-learning (RandQL) for regret minimization in episodic Markov Decision Processes (MDPs). The algorithm introduces the concept of learning rate randomization to achieve optimistic exploration without using bonuses. The performance of RandQL is analyzed in both tabular and non-tabular metric space settings, and it outperforms existing approaches in baseline exploration environments. The authors address the challenge of sample complexity in model-free algorithms where the agent has no access to a simulator. They propose RandQL, a tractable model-free algorithm that achieves exploration without using bonuses. RandQL updates an ensemble of Q-values using Q-learning with Beta distributed step-sizes, introducing noise similar to the posterior sampling approach. The ensemble of Q-values can be seen as posterior samples, and RandQL chooses among these samples in an optimistic fashion. The authors analyze the regret bounds of RandQL in both tabular and metric state-action spaces. The paper highlights that Bayesian-based exploration techniques have shown superior empirical performance compared to bonus-based exploration, but most theoretical studies have focused on model-based algorithms. The authors aim to extend the posterior sampling approach to a provably efficient model-free algorithm that matches the empirical performance of its model-based counterparts. Previous attempts at model-free posterior sampling algorithms have not been computationally tractable, making this a challenge to overcome.

Strengths

1. The idea of relating learning rate randomization to PSRL Dirichlet sampling is interesting. 2. The first computationally tractable model-free (optimistic) posterior sampling algorithm with regret guarantees in tabular setting and metric RL setting. 3. Experiments in finite and continuous MDPs that show that RandQL is competitive with model-based and model-free baselines while keeping a low time-complexity.

Weaknesses

Although the author claims the algorithm do not require bonus, the learning rate randomization still needs (s, a) counting. Counting is not easy to generalise to practical RL with function approximation.

Questions

1. RLSVI related algorithm also do not require bonus but can be can be easily compatible with complex function approximation. Also it utilise all history data in previous theoretical analysis (which can be thought as a definition of model-based), it still only track the optimal value function. Could you give more detailed comparison to this line of work in both computation and sample complexity consideration. 2. See weakness. I could consider increasing score if the questions are properly answered.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

This paper introduces a new model-free Q-learning algorithm that utilizes a randomized learning rate. The effectiveness of this algorithm is theoretically validated by demonstrating a promising regret bound of $\widetilde{O}(\sqrt{H^{5} SA T})$ under the tabular setting. Furthermore, a theoretical bound is established for the metric state-action space in this paper.

Strengths

- Introduces a new model-free algorithm with random exploration. - Provides provable guarantees under both tabular and non-tabular settings.

Weaknesses

The research significance is not well addressed. What are the benefits of eliminating the exploration bonus? What are the promising parts (for future work to develop new methods and apply to practical tasks) compared with alternative methods (e.g., RLSVI, UCB)?

Questions

1. The idea of using multiple ensembles and maximizing to incentivize exploration has been mentioned in previous works. See e.g., [R1, R2] (the reference of [R1] is missing). The reviewer wants to know the difference and whether this is a general technique that theorists and practitioners should follow in the future. 2. Why is RLSVI viewed as a model-based algorithm in the introduction? What are the computational benefits compared with RLSVI? [R1] Ishfaq, Haque, et al. "Randomized exploration in reinforcement learning with general value function approximation." *International Conference on Machine Learning*. PMLR, 2021. [R2] Xiong, Zhihan, et al. "Near-Optimal Randomized Exploration for Tabular Markov Decision Processes." *Advances in Neural Information Processing Systems* 35 (2022): 6358-6371.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Limitations: - The claim in the introduction that "Although empirical evidence suggests that model-based algorithms are more sample efficient than model-free algorithms..." is somewhat misleading. In the field of deep RL, there is no definitive conclusion yet. Please consider revising this argument. - The vanilla Q-learning algorithm is rarely used in practice. Practitioners typically utilize the target Q-learning algorithm. Please refer to [R3] for further discussion. It is encouraged to investigate this algorithm with a randomized learning rate. [R3] Zanette, Andrea, and Martin Wainwright. "Stabilizing Q-learning with Linear Architectures for Provable Efficient Learning." *International Conference on Machine Learning*. PMLR, 2022.

Summary

The paper proposes a new algorithm, Randomized Q-learning (RandQL), for regret minimization in episodic Markov Decision Processes (MDPs). RandQL is the first manageable model-free posterior sampling-based algorithm. The authors study RandQL's performance in both tabular and non-tabular metric space settings. In tabular MDPs, RandQL gives a regret bound of $O(\sqrt{H^5SAT})$, where $H$ is the planning horizon, $S$ the number of states, $A$ the number of actions, and $T$ the number of episodes. RandQL has a regret bound of order $O(\sqrt{H^5T^{(d_c+1)/(d_c+2)}})$, where $d_c$ is the covering dimension, in a metric state-action space. Interestingly, RandQL achieves optimistic exploration without bonuses and uses a new idea of learning rate randomization. The authors also show that RandQL does better than current methods on baseline exploration environments in their empirical study.

Strengths

1. The introduction of learning rate randomization is novel and interesting, that lets RandQL achieve optimistic exploration without bonuses. This indeed reduce the memory cost. 2. RandQL does well in both tabular and non-tabular metric space settings. In both cases, the authors show that it gives good regret bounds. That's a pretty solid result.

Weaknesses

In the experiments, the performance gap between model-free algorithms and model-based algorithms seems too large. It would be better to provide stronger evidence in experiments of the benefits of RandQL such as lower computation cost, lower memory cost, or possibly has a closer performance in a more complex environment compared to model-based methods.

Questions

Can authors discuss why the randomized learning rate can work in a high-level idea? For example, is it possible that this randomization brings some optimistic?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Reply to the rebuttals

Thank you for the response. I would keep my score.

Reply to rebuttal

I would like to thank the authors for their detailed response to my questions. I believe the majority of my concerns have been addressed and will raise my score accordingly. In particular, I agree with the author's assessment of RLSVI, and that it is not truly model-free in the sense considered in this work. Furthermore, I had previously missed the bounds scaling with the zooming dimension given in Appendix F. I would encourage the authors to include these bounds in the main body for the final version, as space permits (and provide a full proof of the results).