Regret Bounds for Information-Directed Reinforcement Learning
Authors: Botao Hao
Tor Lattimore
Venue: NeurIPS 2022 Accept (2022)
Keywords: information-directed sampling
regret bound

Abstract: Information-directed sampling (IDS) has revealed its potential as a data-efficient algorithm for reinforcement learning (RL). However, theoretical understanding of IDS for Markov Decision Processes (MDPs) is still limited. We develop novel information-theoretic tools to bound the information ratio and cumulative information gain about the learning target. Our theoretical results shed light on the importance of choosing the learning target such that the practitioners can balance the computation and regret bounds. As a consequence, we derive prior-free Bayesian regret bounds for vanilla-IDS which learns the whole environment under tabular finite-horizon MDPs. In addition, we propose a computationally-efficient regularized-IDS that maximizes an additive form rather than the ratio form and show that it enjoys the same regret bound as vanilla-IDS. With the aid of rate-distortion theory, we improve the regret bound by learning a surrogate, less informative environment. Furthermore, we extend our analysis to linear MDPs and prove similar regret bounds for Thompson sampling as a by-product.

Regret Bounds for Information-Direeted Reinforcement Learning
Botao Hao
Tor Lattimore Deepmind
Deepmind haobotao000@gmail.ccom
lattimore@@oogle..com
Abstract
coomaation-dirccted sampling (IDS) has revealed its potential as a data-efficient algorithm [Lu et al., 2021] for reinforcement learning (RL). However, theoretical understanding of IDS for Markov Decision Processes (MDPs) is still limited. We develop novel information-theoreti tools bound the information ratio and cumulative information gain about the learning target. Our theoretical results shed light the importance of choosing the learning target such that the practitioners can balance the computation and regret bounds. As a consequence, we derive prior- free Bayesian regret bounds for vanilla- which learns the whole environment under tabular finite-horizon MDPs. addition, we propose a computationally- that maximizes an additive form rather than the ratio
efficient regularized- form and show that it enjoys the same regret bound as vanilla-IDS. With the aid of rate-distortion theory, improve the regret bound by learning surrogate, less informative environment. Furthermore, extend our analysis linear MDPs and prove similar regret bounds for Thompson sampling as by-product.
Introduction
Information-dires direcced sampling (IDS) a design principle proposed by [Russo and Van Roy, 2014, 2018] that optimizes the trade-off between information and regret. Comparing with other design principles such UCB and Thompson sampling (TS), IDS automatically adapt to different information-rege structures. As a result, IDS demonstrates impressive empirical performance [Russo and Van Roy, 2018) and outperforms UCB and TS in terms of asymptotic optimality [Kirschner et al., 2021] and minimax optimality in heteroscedastic bandits [Kirschner and Krause, 2018] and sparse linear bandits [Hao et al., 2021].
In the context of full RL, mutiple works have examined the empirical performance of IDS [Nikolov al., 2018, Lu al., 2021]. However, formal regret guarantee for IDS is still lacking. IDS minimizes notion of information ratio that is the ratio of per-episode regret and information gain about the learning target. While different choices of the learning target could lead to different regret bounds and computational methods, the most natural choice is the whole environment and we name the corresponding IDS as vanilla-IDS.
In this work, we prove the first prior- where S is the size of state space, A is the size of action space, H is the length of episodes and is the number of episodes. Computationally, vanilla-In IDS needs optimize over the full policy space, which is not efficient in general. To facilitate the computation, we consider its regularized form, named regulari regularized-ID. IDS, that can be solved by any dynamic programming solver. By carefully
Bayesian regret bound for vanilla-IDS.
36th Conference Neural Information Processing Systems (NeurIPS 2022).

---

choosing the tunable parameter, we prove that regularized- enjoys the same regret bound as vanilla-IDD
Although learning the whole environment offers certain computational advantages, the agent could take too much information to learn the whole environment exactly. A key observation is that different states may correspond to the same value function which eventually determines the behavior of the optimal policy. Through the rate-distortion theory, we construct surrogate environment that is less informative to learn but enough to identify the optimal policy. As a result, we propose surrogate-ID IDD that takes the surrogate environment as the learning target and prove a sharper AL bound for tabular MDPs.
In the end, we extend our analysis to linear MDPs where we must learn a surrogate environment due potentially infinitely many states and derive OdH?2 Bayesian regret bound that matches the existing minimax lower bound up factor of H. As by-product of our analysis, we also prove prior-free Bayesian regret bounds for TS under tabular and linear MDPs.
2
Related work
In general, there are two ways to prove Bayesian regret bounds. The first is to introduce confidence sets such that the Bayesian regret bounds of TS can match the best possible frequentist regret bounds by UCB [Russo and Van Roy, 2014] and has been extended to RL by Osband et al. [2013], Osband and Van Roy [2014], Osband et al. [2019]. However, when the best possible bound for UCB is sub-optimal (for instance, sparse linear bandits [Hao al., 2021]), this technique yields a sub-optimal Bayesian regret bound. In addition, this technique can only be used to analyze TS but not IDS.
The second is to decompose the Bayesian regret into an information ratio term and cumulative information gain term and bound them by tools from information theory [Russo and Van Roy, 20.6]. This technique can be used to analyze both TS [Dong and Van Roy, 2018, Bubeck and Sellke, 2020] and IDS in bandits setting [Russo and Van Roy, 2014, Liu et al., 2018, Kirschner et al., 2020b, Hao al., 2021, 2022], partial monitoring [Lattimore and Szepesvári, 2019, Kirschner et al., 2020a, Lattimore and Gyorgy, 2021] but not RL as far as we know. One exception is Lu and Van Roy [2019], Lu [2020] who bounded the information ratio for specific Dirichlet prior with additional assumptions.
Frequentist regret bounds in episodic RL have received considerable attention recently. For tabular MDPs, several representative works include UCBVI [Azar et al., 2017], optimistic Q-learning [Jin et al., 2018], RLSVI [Russo, 2019], UCB-Advantage [Zhang et al., 2020], UCB-MQ [Ménard et al., 2021]. While our regret bounds are not state of the art, the primary goal of this paper is to broaden the set of efficient RL design principles known to satisfy VT regret bounds.
For linear or linear mixture MDPs, several representative works include LSVI-UCB [Jin et al., 2020], OPPO [Cai et al., 2020), UCRL-VTR [Ayoub et al., 2020, Zhou et al., 2021], RLSVI [Zanette et al., 2020J. Notably, Zhang [2021]. Dann et al. [2021] derived minimax regret bounds for a variant of TS. Beyond linear cases, several works consider general function approximation based on Bellman rank [Jiang et al., 2017], cluder dimension [Wang et al., 2020], Bellman-eluder dimension [Jin et al., 2021] and bilinear class [Du et al., 2021].
It is worth mentioning the recent impressive work by Foster et al. [2021] who proposed a general Estimation-to-DD
(E2D) design principle. Although motivated by different design principles, E2D shares the similar form as regularized-IDS On one hand, Foster et al. [2021] mainly focuses on statistical complexity in a minimax sense, while we offer a specific computationally- efficient algorithm thanks to the chain rule of mutual information and independent priors and derive corresponding Bayesian regret bounds. On the other hand, while E2D tends learn the whole environment, our theory in Section 5 suggests learning surrogate environment could yield better regret bounds.

---

3 Preliminary
Finite-horizon MDPs The environment characterized by a finite-horizon time-inhomogeneous MDP, which is a tuple (S, A, H, (Pr ) frh h where S the countable state space with |8| = S. A is the finite action space with |A] A, H is the episode length, PA S x A As is the transition probability kemel and rı 8 A [0, 1] is the reward function. For finite set S, let As be the set of probability distributions over S. We assume S, A, Th are known and deterministic while the transition probability kernel is unknown and random. Throughout the paper, we may write Ph. and гı explicitly depend on when necessary.
Let O = [0. 11$xAxx be the parameter space of PA and θ 01 x.. Oh be the full parameter space. We assume Ps. is the prior probability measure for Ps. On, with Borel o-algebra and P P1 .... @ PH the product prior probability measure for the whole environment on θ with Borel o-algebra. This ensures the priors over different layers are independent and the prior is assumed to be known to the learner.
Interaction protocol An agent interacts with a finite-horizon MDP follows. The initial state oi is assumed be fixed over episodes. In each episode E [Z] and each layer E [H], the agent observes a state sf,, takes action af and receives reward rf. Then, the environment evolves to random next state + according to distribution (- ).). The episode terminates when 8141 is reached and is reset to the initial state.
Denote He, n as the history of episode up to layer h, e.g., He, = (sf, the set of such possible history is S4 = I (S x A [0, IJ) Let Dj (H1.H..... H4-1,11 as the entire history up to episode with D1 6. A policy π is collection of (possibly randomised) mappings ( TH) where each TTi maps an element from f2211 x S to A(A) and 11 is the whole policy class. A stationary policy chooses actions based on only the current state and current layer. The set of such policies is denoted by IIs where we denote Ty, (a(s) as the probability that the agent chooses action a at state s and layer h.
5 of rf,) and
Value function the expected value of cumulative rewards received under policy when starting from an arbitrary state at /ith layer; that is,
For each h E [H] and a policy æ, the value function V S - R is defined as
H Σ
E n, (s) = E Lh'=h
TM (sw ax)
8h =
where E denotes the expectation over the sample path generated under policy н and environment
We adapt the convention that v.. 0. There always exists an optimal policy x² which gives the optimal value V (s) max=em, Vr,, (s) for all E S and h E [H]. Note that in the Bayesian setting, n is function of & so it is also a random variable. In addition, we define the action-value function as follows:
H
of = = E
(sw axd) s, s,a, =
which satisfies the Bellman equation: (s, (n, a) + E Vitt Further-
more, we denote the state-action occupancy measure as
( T (sh 8, OA =a);
where we denote p as the law of the sample path generated under policy æ and environment E.
Bayesian regret The agent interacts with the environment for episodes and the total number of steps is T LH. The expected cumulative regret of an algorithm { H/ with respect to an environment is defined
Ry RE, T) E
Σ
(5f-(sf) VL (s))
3

---

where the expectation is taken with respect to the randomness of n². The Bayesian regret then is defined as
2 (T) (E, x)),
where the expectation is taken with respect to the prior distribution of &. At each episode, TS finds
argmax Vi.: 1,, (s1)
TS
sell
where & is sample from the posterior distribution of &, e.g., & IP(E (Dz).
Notations Let (2, F.)
measurable space. A random variable X is measureable function X Ω + E from a set of possible outcomes Ω to a measurable space E. Now P(X E -) is
a probability measure that maps from F to [0, 1]. D, is another random variable from 1 to
measurable space Y. Then P(X E -(Dz) is a probability kernel that maps from Ω x F + [0. 1].
We write Pe(.) PP())P)), [e[l] E| [Da) and also define the conditional mutual information (x;)) (KL(X( (D:) PXX ((De) P(Y -(De)). For random variable x define:
(x: He,n) DKL (l,,,=((, HeN) E 1), E @ Pr,,(He,n E )),
where Pe,x is the law of x and the history induced by policy interacting with sample from the posterior distribution of & given Dz. We define & as the mean MDP where for each state-action pair (s, a). pf (-1s,a) a) E.IA (-Is, a)] the mean of posterior measure.
Learning the whole environment
The core design of IDS for RL relies on a notion of information ratio. The information ratio for policy π at episode is defined as
[Ee.V
1.x (54) VI, (si)))
Te(
(4.1)
17 (xi He,H)
where x is the learning target to prioritize information sought by the agent. The choice of plays crucial role in designing the IDS and could lead to different regret bounds and computational methods. We first consider the most natural choice of x which is the whole environment &
4.1 Vanilla IDS
Vanilla- IDS takes the whole environment & as the learning target and at the beginning of each episode, the agent computes a stochastic policy:
Te(T) = (EeVVE 1, (sf) V.E. (sf)1)2
TiDS = argmin
(4.2)
(E;
TEll
Define the worst-case information ratio 1* such that (2( < 1 for any é E [L] almost surely. The next theorem derives generic regret bound for vanilla- IDS in terms of I and the mutual information between È and the history.
Theorem 4.1. A generic regret bound for vanilla-IDs is
BBy & [E;
The proof is deferred to Appendix A. and follows standard iiformation-thhoreefii regret decompo- sition and the chain rule of mutual information that originally was exploited by Russo and Van Roy [2014]. For tabular MDPs, remains to bound the E[["] and II (E; DL+1) separately.
Lemma 4.2. The worst-case information ratio for tabular MDPs is upper bounded by
ETT < 2SAH

---

We sketch the main steps of the proof and defer the full proof to Appendix A.2.
Proof sketch. Since vanilla- minimizes the information ratio over all the policies, we can bound the information ratio of vanilla-IDS by the information ratio TS.
Step one. Our regret decomposition uses the value function based on & as a bridge:
Eg Vf. Vf (5f) - Vr. 1,74fs (sf) = Eg Vf..r (s1)
1,mf. (of)
E
V 1,7
(sf)
V
(0f)
1,
Note that conditional on Dr, the law of rís is the same as the law of x² and both x² and xfs are independent of Eg. This implies Ee[V &e (sf) EV (sf)].
1,
Step two. Denote (s, a) = E (l),a)) Vi 1, (5)) B p (-Is,a) ( (0 (8') as the value function difference. Inspired by Foster et al. [2021], with the use of state-action occupancy measure and Lemma D.3, we can derive
Lle b. (s,a)
11
Ee
[B (s, (Beld (s, (s.a)))
(2.0)
Applying the Cauchy-Schwarz Schwarz inequality and Pinsker's inequality (see Eqs. (A.2)-(A.4) in the appendix for details), we can obtain
1/2
of (-1ss ob) (l)
IS VSAH3
Σ
E
E
DKL (Ph
where we interchange wÎs and nh again and B& taken with respect to æ/s and E.
is taken with respect to s of and E, is *Is
Step three. It remains to establish the following equivalence of above KL-divergence and the information gain (Lemma A.1):
H
E
R
DKL. (Pf (-1ss, I (-1sh, an) ]]] = Th (E; He,H)
A crucial step is to use the linearity of the expectation and the independence of priors different layers (from the product prior assumed in Section 3) show
P P (sh-1 Qh-1 a)
IF& (sh-1 0h-1 a).
Combining Steps 1-3, can reach the conclusion and the bound for is similar.
The next lemma directly bounds the mutual information for tabular MDPs. Lemma 4.3. The mutual information can be bounded by
I(E; (++1) < 2S² AH log (SLH).
The proof relies on the construction of Bayes mixture density and covering set for KL-divergence and is deferred to Appendix A.3. Combining Theorem 4.1, Lemmas 4.2 and 4.3 yields the following:
Theorem 4.4 (Regret bound for tabular MDPs). Suppose Tws (/ is the vanilla IDS policy. The following Bayesian regret bound holds for tabular MDPs
BRy (TIs) S
Although this regret bound is sub-optimal, this is the first sub-linear free Bayesian regret bound for vanill. I
5

---

Remark 4.5. It is worth mentioning that Lu and Van Roy [2019], Lu [2020] also derived Bayesian regret bound using cnarmatiion-hhoreiiien tools but only hold for specific Dirichlet prior as well other distribution-speciij assumptions. Their proof heavily exploits the property of Dirichlet distribation and can not easily be extended to prior-free regret bounds.
In the context of finite-horizon MDPs, Lu et al. [2021] considered a condi tinaa-IDS such that at each time step, conditional on s/ conditional oooooonnnDDDS IDS takes the action according to
ve (6 Ph (6/1- An)))
Egg
TA (-1))) argmin MEAA
Tee (xs (An, - An))
where A, is sampled from v. Conditional-IDS defined the information ratio per-step rather than per-episode such that it only needs to optimize over action space rather than the policy space. This offers great computational benefits but there is no regret guarantee for conditional- IDD. Recently, Hao et al. [2022] has demonstrated the theoretical limitation of conditional-ID. IDS contextual bandits.
4.2 Regularized IDS
Computing an IDS policy practically usually involves two steps: approximating the information ratio; 2. optimizing the information ratio. In bandits where the optimal policy is only function of action space, optimizing Eq. (4.2) is convex optimization problem and has an optimal solution with at most two non-zero components (Russo and Van Roy [2018, Proposition 6)). However in MDPs where the optimal policy is a mapping from the state space to the action space, vanilla- IDS needs to traverse two non-zero components over the full policy space which suggests the computational time might grow exponentially in and H.
To overcome this obstacle, propose regular aellaarizeedii IDS that be efficiently computed by any dynamic programming solver and enjoy the same regret bound as vanilla-IDS. At each episode f, regularized- IDS finds the policy:
THIS = argmax [V,, (51)] + Alle (8:H),H)
(4.3)
xell
where À > O is a tunable parameter.
To approximate the objective function in Eq. (4.3), we assume the access to a posterior sampling oracle.
Definition 4.6 (Posterior sampling oracle). Given a prior over & and history Dr. the posterior sampling oracle, SAMP, is a subroutine which returns a sample from the posterior distribution Pe(E). Multiple calls to the procedure result in independent samples.
Remark 4.7. SAMP can be exactly obtained when the conjugate prior such as Dirichlet distribution is put the transition kernel. When approximated by epistemic neural networks [Osband et al., 2021a], general framework to quantify uncertainty for neural nets. The effectiveness of different epistemic neural networks such as deep ensemble, dropout and stochastic gradient MCMC has been examined empirically by Osband et al. [202 lb].
neural nets estimate the model, SAMP can be
We compute TAADS in two steps:
Firstly, we prove an equivalent form of the objective function in Eq. (4.3) using the chain rule of mutual information. Define r/ (8, a) as an augmented reward function:
(s) an(s,a) + > f DKL (PÉ a) ( ( dp, (E)
Proposition 4.8. The following equivalence holds
Σ r (s an)
EV (sf)) + AIZ (E: He,H) =

---

The proof is deferred to Appendix A.4.
Given SAMP, the augmented reward r/ and the MDP & can be well approximated by Monte Carlo sampling. Therefore, at each episode E, finding T-IDS is equivalent to find an optimal policy based computable and augmented MDP {PA r M= This be solved efficiently by any dynamic programming solver such as value iteration policy iteration.
In the end, we show that " enjoys the same regret bound as vanilla- when the tunable parameter is carefully chosen.
Theorem 4.9. By choosing À = LETTI//I(E2 DL+1), we have
3 [ETTTT((E
B (T 1DS)
The proof is deferred to Appendix A.5. Let M1, M2 be upper bounds of [R[[")] and T[E; D L+1) respectively. In practice, we could conservatively choose X = v LLMM/M such that (xx I
/3/2M, M2 From Lemmas 4.2 and 4.3 for tabular MDPs, we could choose M1 25 AH and M2 = 2S2 AH log(SLH).
Remark 4.10. Russo and Van Roy [2018, Section 9.3] also considered a tunable version of IDS (for bandits) but took a square form of Ee (E.,,((((()) While this makes no difference in bandits setting, this prevented us use dynamic programming solver in RL setting. We are also inspired by Foster et al. [2021, Section 9.3] who studied the relationship between information ratio and Decision-Estimalee Coefficient.
5 Learning a surrogate environment
When the state space is large, the agent could take too much information to learn exactly the whole environment & which is reflected through ((E;Dr+1). A key observation is that different states may correspond to the same value function who eventually determines the behavior of the optimal policy. Based on the rate-distortion theory developed Dong and Van Roy [2018], we reduce this redundancy and construct a surrogate environment that needs less information to learn.
5.1 A rate distortion approach
The rate-distortion theory [Cover and Thomas, 1991] addresses the problem of determining the minimal number of bits per symbol that should be communicated (input signal) can be approximately reconstructed at the receiver (output signal) without exceeding an expected distortion. It was recently introduced to bandits community to develop sharper bounds for linear bandits [Dong and Van Roy, 2018] and time-sensitive bandits [Russo and Van Roy, 2022]. We take a similar approach to construct a surrogate environment.
channel, that the source
Surrogate environment Suppose there exists partition { over O such that for any E, 8' O and any & E [K], we have
Vg..ng (s1) - Vi..ng (s1) Se,
(5.1)
where e > 0 is the distortion tolerance and we write the optimal policy explicitly depending on the environment. Let be a discrete random variable taking values {1...., K} that indicates the region& & lies such that Ç = & if and only if E Og. Therefore, Ç can viewed as a statistic of & and less informative than E if K small.
The next lemma shows the existence of the surrogate environment based on the partition. Lemma 5.1. For any partition {Ox K k= and any E [L]. we can construct a surrogate environment Er E θ which is random MDP such that the law of E; only depends on Ç and
Eg V (5f) Vi.ngg (01)
E2 V2.V [Vf
V.Ei V.,0g (sf) Se.
(5.2)
The concrete form of Eg is deferred to Eq. (B.1) in the appendix.
7

---

Surrogate IDS
We refer the IDS based on the surrogate environment E as surrogate - that
minimizes
(Ee[Vi.r
1, (sf) V(,+ =)
argmin Tell
(5.3)
(E He,H)
for parameters
0 the will be chosen later. Denote the surrogate information ratio of TS as
V 1,
($f) v 1, (e)))
Eg
max LE[L]
i (E7 H(,H)
We first derive generic regret bound for surrogate IDS in the following theorem. Theorem 5.2. A generic regret bound for surrogate IDS is
BR 2
E[T] D Le.
We defer the proof to Appendix B.2. Given Ç. we have Eg and He are independent under the law of P. f By the data processing inequality, the proof uses the fact that
ins (&;; He,r)
IiA (4; He,
Comparing with regret bound of vani vanilla-IDS in Lemma 4.1, the regret bound of surrogate- IDS depends on the information gain about Ç rather than the whole environment E. If there exists a partition with small covering number K, the agent could pay less information to learn. The second term Le the price of distortions.
In the following, will bound the ET] and I for tabular and linear MDPs separately.
5.2 Tabular MDPs
We first show the existence of the partition required in Lemma 5.1 for tabular MDPs and an upper bound of the covering number K. Lemma 5.3. There exists a partition {0t) over such that for any & E [K] and & & E Of
V
(81) V1,2g (81) 8
and the log covering number satisfies log( K) S SAH (og(4HH²/s)
The proof is deferred to Lemma B.3. For tabular MDPs, the mutual information between Ç and the history can be bounded by
DL+1) H(()) < log(K)= s SAH log(4HH
where H[(-) is the Shannon entropy. Comparing with Lemma 4.3 when learning the whole environment, learning the surrogate environment saves a factor of S throuuh the bound mutual information. Lemma 5.4. The surrogate information ratio for labular MDPs is upper bounded by
E[T] 2SAH3
The proof is the same as Lemma 4.2 and thus omitted. Putting Lemmas 5.3-5.4 yields an improved bound for tabular MDPs using surrogate- -DD. Theorem 5.5 (Improved regret bound for tabular MDPs). By choosing 1/L, the regret bound of surrogate- IDS for tabular MDPs satisfies
BH, (T & A2
For tabular MDPs, surrogate- IDS improves the regret bound of vanilla-IDS by factor of S. However, it is still away from the minimax lower bound by a factor of vSAHI. We conjecture surrogate- -n IDS can achieve the optimal bound with a price lower order term but leave as a future work.
Remark 5.6. Although the existence of & is established using constructive argument, finding E needs grid search and is not computationally efficient.

---

5.3 Linear MDPs
We extend our analysis to linear MDPs that is fundamental model to study the theoretical properties of linear function approximations in RL. All the proofs are deferred to Appendix B.4-B.5.
Definition 5.7 (Linear MDPs [Yang and Wang, 2019, Jin et al., 2020)), Let Φ 8 A R be feature map which assigns to each state-action pair d-dimensional feature vector and assume [lo(s, a)ll S. 1. An MDP is called linear MDP for any h E [H], there exist d unknown (signed) measures ....., Vh over S, such that for any (s,a) E ES x A, we have
Pa(-|s, 0) (o(s, a), ()),
where un = (th....,,
v1). Let us denote @ be the parameter space of linear MDPs and assume |E (n()))122 S Cv.
Note that the degree of freedom linear MDPs still depends on S which implies that I(E; DL+11) may still scale with S. Therefore, we must learn surrogate environment rather than the whole environment for linear MDPs based on the current regret decomposition in Theorem 4.4. We first show the existence of partition over linear MDPs with the log covering number only depending on the feature dimension d.
Lemma 5.8. There exists a partition
{0)) over Qlin such that for any [K] and & &2 E Os.
V 1, (81) V1 (s1) S,,
and the log covering number satisfies log( K) < Hd C2
For linear MDPs, the mutual information can be bounded by
T(;;De4)) S H()) S log(K)= S Hdlogg H Co 1).
Lemma 5.9. The surrogate information ratio of linear MDPs is upper bounded by E(T) S 4H
Theorem 5.10 (Regret bound for linear MDPs). By choosing 1/L, the regret bound of surrogate IDS for linear MDPs satisfies
(T.DD) S AAHL +1.
This Bayesian bound improves the 22 frequentist regret of LSVI-UCB [Jin et al., 2020] by a factor of vd and matches the existing minimax lower bound O / Ld [Zhou et al., 2021] up to H factor. However, we would like to emphasize that this is not an apples-to-appee to-apples comparison, since in general frequentist regret bound is stronger than Bayesian regret bound.
5.4 Regret bounds for TS
As direct application of our rate-distortion analysis, we provide Bayesian regret bounds for Thomp- sampling.
Theorem 5.11. generic regret bound for TS is
BR (TIS) S DfTT(CDDL-IL + Le.
This implies for tabular and linear MDPs, TS has the same regret bound as MDrrogate-IDS. Note that the computation of TS does not need to involve the surrogate environment & so once posterior sampling oracle is available, computing the policy efficient. Howevern when the worst- case information ratio cannot be optimally bounded by the information ratio of TS, IDS demonstrates better regret bounds than TS, such as bandits with graph feedback [Hao al., 2022] and sparse linear bandits [Hao et al., 2021].

---

Conclusion
In this paper, we derive the first prior-free Bayesian regret bounds for information-directe RL. under tabular and linear MDPs. Theoretically, it will be of great interest to see any version IDS can achieve the O(VSAH3L) minimax lower bounds for tabular MDPs.
Acknowledgements
We would like to thank Johannes Kirschner for helpful initial discussions.
References
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pages 463-474, PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
Sébastien Bubeck and Mark Sellke. First-order bayesian regret analysis of thompson sampling, In Algorithmic Learning Theory, pages 193-233. PMLR, 2020.
Qi Cai, Zhuoran Yang. Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294, PMLR, 2020.
T.M. Cover and J.A. Thomas. Elements of Information Theory. Wiley Series in Telecommunications and google. www bookkdoo
Signal Processing. Wiley, 1991. ISBN 9780471062592. URL CX9QAAAAMAAJ.
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances Neural Information Processing Systems. 34, 2021.
Shi Dong and Benjamin Van Roy. An information-theorrtie analysis for thompson sampling with many actions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4161-4 1166, 2018.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruasong Wang. Bilinear classes: structural framework provable generalization In International Conference on Machine Learning, pages
PMLR, 2021.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:21 13487, 2021.
Botao Hao, Tor Lattimore, Wei Deng. Information directed sampling for sparse linear bandits. Advances in Neural Information Processing Systems, 34, 2021.
Botao Hao, Tor Lattimore, and Chao Qin. Contextual information-directed sampling. In Kamalika Chaudhuri, Stefanie Jegelka, Song, Csaba Szepesvari, Gang Niu, Sivan Sabato, editors, Proceedings of 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 0446-864.. PMLR, 17-23 Jul 2022. URL https://proceeding mlr wwt.sp/esss// hao22b. html.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. Contextual decision processes with low bellman rank are pac-lcarnable. In International Conference on Machine Learning, pages 1704-1713, PMLR, 2017.
Chi Jin, Zeyuan Allen Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137-2143, PMLR, 2020.
10

---

Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34, 2021.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference Learning Theary, pages 358-384. PMLR, 2018.
Johannes Kirschner, Tor Lattimore, and Andreas Krause, Information directed sampling for linear partial monitoring. Conference on Learning Theory, pages 2328-2369. PMLR, 2020a.
Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. Asympiotically optimal information- directed sampling. arXiv preprint (XXiv:00110059// 2020b.
Johannes Kinschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. Asymptotically optimal information- directed sampling. In Conference Learning Theory, pages 2777-2821, PMLR, 2021.
Tor Lattimore and Andras Gyorgy. Mirror descent and the information ratio. In Conference on Learning Theory, pages 2965-2992. PMLR, 2021.
Tor Lattimore and Csaba Szepesvári. An information-thhorrticc approach to minimax regret in partial monitoring. In Conference on Learning Theory, pages 211 1-119.. PMLR, 2019.
Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic bandits with graph feedback. In Proceedings the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Xiuyuan Lu. information-Directedd Directed Sampling for Reinforcement Learning. Stanford University, 2020.
Xiuyuan Lu and Benjamin Van Roy. Information-theoretic confidence bounds for reinforcement learning, arXiv preprint arXiv:1911.09722 2019.
Xiuyuan Lu, Benjamin Van Roy. Vikranth Dwaracherla, Morteza Ibrahimi, lan Osband, and Zheng Wen. Reinforcement learning, bit by bit. arXiv preprint arXiv:2/03.00004, 2021.
Pierre Ménard, Omar Darwiche Domingues. Xuedong Shang, and Michal Valko. Ueb momentum q gearnning:: Correcting bias without forgetting. In International Conference on Machine Learning, pages 7609-6613
PMLR, 2021.
Nikolay Nikolov, Johannes Kirschner, Felix Berkenkamp, Andreas Krause. dnffommation-direade exploration for deep reinforcement learning. In Intermational Conference on Learning Representations, 2018.
Ian Osband and Benjamin Van Roy. Model-basee reinforcement learning and the eluder dimension. Advances Neural Information Processing Systems, 27, 2014.
Tan Oshand, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Ian Oshand, Benjamin Van Roy, Daniel J Russo, Zheng Wen, al. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20 (24): 2019.
Ian Osband, Zheng Wen, Mohammad Asghari. Morteza Ibrahimi, Xiyuan Lu, and Benjamin Van Roy. Epistemic neural networks. arXiv preprint 2rXiv:2107.08924 2021a
Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Botao Hao, Morteza Ibrahimi. Dieterich Lawson, Xiuyuan Lu, Brendan O' Donoghue, and Benjamin Van Roy. The neural testbed: Evaluating predictive distributions. arXiv preprint arXiv:21 10.0066, 2021b.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Advances Neural Information Processing Systems, 32, 2019.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direette sampling. Advances in Neural Information Processing Systems, 27, 2014.
Daniel Russo and Benjamin Van Roy. information tatoootttttttttcccooooo analysis thompson sampling. The Journal of Machine Learning Research, 17(1):2442 2471, 2016.

---

Daniel Russo and Benjamin Van Roy. Learning to optimize via information--ireeted sampling. Operations Research, 66(1):230-252, 2018.
Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. Mathematics of Operutions Research, 2022.
Jennifer Tang and Yury Polyanskiy. Capacity noisy permutation channels. arXiv preprint arXi:22111.0055, 2021.
Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded cluder dimension. Advances in Neural Information Processing Systems, 33:6123-6135, 2020.
Lin Yang and Mengdi Wang. hample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequen- tist regret bounds for randomized least-squares value iteration. In International Conference Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020.
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. arXiv preprint arXiv:21 10.0087), 2021.
Zihan Zhang, Yuan 7hou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference- advantage decomposition. Advances in Neural Information Processing Systems, 33:15198 15207, 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576, PMLR, 2021.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], [ or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [N/A]
Did you include the license to the code and datasets? [N/A]
Did you include the license to the code and datasets? [N/]]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
12

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "vZf8g-tCFoW", "reviewer": "Reviewer_uxAT", "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. ", "questions": "In some places the definition of variables are omitted, please check it. \n- Definition of \\bar{\\Epsilon}_l is recursive\n-  zeta in the proof of B.1 is undefined\n-  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. \n\nMinor remarks\n\n- for the clarity, it has to be mentioned in the preliminaries that the prior is assumed to be known to the learner\n- Partition should depend on \\epsilon\n- In equation (3.3), \\pi is missing from I_{\\ell}\n", "limitations": "The main limitation of the proposed algorithms is that they are not computationally efficient. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.    \nNext, 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 \n 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. \nFinally, 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. \n\n\nI 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. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pOBAWa5g96L", "reviewer": "Reviewer_hin3", "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.", "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. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe refinements due to rate distortion theory were also a nice addition.\n\nWeaknesses: 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. \n\nIn 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. \n\nAnother 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jg0D8CTuM6F", "reviewer": "Reviewer_Dwor", "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. \n", "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?\n", "limitations": "Line 51: it would be more convincing to include some cases where the best UCB-type algorithms are sub-optimal.\n\nOne 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. \n\nLine 177: conditionar => conditional\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Tpn0-rrxq6w", "reviewer": "Reviewer_dRgt", "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.", "questions": "Please check the **Weakness** section above.", "limitations": "N.A.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThis 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.\n\n\n### Weakness\n\nI only have a small issue about the rigorousness in the discussion related to $\\Gamma^*$ in Sec. 3.1 and related proof.\n\nIt 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^*$.\n\nTherefore, 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).\n\nIf the authors can fix the issue I mentioned above, I would like to increase my score correspondingly.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept