Asymptotic Instance-Optimal Algorithms for Interactive Decision Making
Authors: Kefan Dong
Tengyu Ma
Venue: ICLR 2023 poster (2023)
Keywords: reinforcement learning theory
instance optimality

Abstract: Past research on interactive decision making problems (bandits, reinforcement learning, etc.) mostly focuses on the minimax regret that measures the algorithm's performance on the hardest instance. However, an ideal algorithm should adapt to the complexity of a particular problem instance and incur smaller regrets on easy instances than worst-case instances. In this paper, we design the first asymptotic instance-optimal algorithm for general interactive decision making problems with finite number of decisions under mild conditions. On every instance $f$, our algorithm outperforms all consistent algorithms (those achieving non-trivial regrets on all instances), and has asymptotic regret $\mathcal{C}(f) \ln n$, where $\mathcal{C}(f)$ is an exact characterization of the complexity of $f$. The key step of the algorithm involves hypothesis testing with active data collection. It computes the most economical decisions with which the algorithm collects observations to test whether an estimated instance is indeed correct; thus, the complexity $\mathcal{C}(f)$ is the minimum cost to test the instance $f$ against other instances.  Our results, instantiated on concrete problems, recover the classical gap-dependent bounds for multi-armed bandits and prior works on linear bandits, and improve upon the previous best instance-dependent upper bound for reinforcement learning. 

Published as a conference paper at ICLR 2023
ASYMPTOTIC INSTANCE-OPTIMAL ALGORITHMS FOR INTERACTIVE DECISION MAKING
Kefan Dong
Tengyu Ma
Stanford University
Stanford University
ke ee
tengyuma aat.aaorddddddadoiie.........
ABSTRACT
Past research on interactive decision making problems (bandits, reinforcement learning, etc.) mostly focuses on the minimax regret that measures the algorithm's s performance on the hardest instance. However, an ideal algorithm should adapt to the complexity of particular problem instance and incur smaller regrets easy instances than worst-case instances. In this paper, we design the first asymptotic instance-optimal algorithm for general interactive decision making problems with finite number of decisions under mild conditions. On every instance f. our algo- rithm outperforms all consistent algorithms (those achieving non-trivial regrets all instances), and has asymptotic regret C(J) In., where C(J) is an exact charac- terization of the complexity of f. The key step of the algorithm involves hypothe- sis testing with active data collection. It computes the most economical decisions with which the algorithm collects observations to test whether an estimated in- stance is indeed correct; thus, the complexity C(f) is the minimum cost to test the instance ff against other instances. Our results, instantiated on concrete problems, recover the classical gap-dependent bounds for multi-armed bandits (Lai al., 1985) and prior works on linear bandits (Lattimore & Szepesvari] 2017), and im- prove upon the previous best instance-dependent upper bound (Xu et al. 2021 for reinforcement learning.
INTRODUCTION
Bandit and reinforcement learning (RL) algorithms demonstrated wide range of successful real- life applications (Silver et al., 2016 2017 Mnih et al.] 2013; Berner et al.] 2019 Vinyals et al.)
2019 Mnih et al., 2015 Degrave et al. 2022). Past works have theoretically studied the regret or sample complexity of various interactive decision making problems, such as contextual bandits, reinforcement learning (RL), partially observable Markov decision process (see) Azar et al. (2017);
Jin et al. (2018) Dong et (2021) Li al. (2019); AAgawal al. (014);
& Rakhlin (020
Jin et al. 2020), and references therein). Recently, Foster et al. (2021) present a unified algorithmic
principle for achieving the minimax regret-the optimal regret for the worst-case problem instances.
However, minimax regret bounds do not necessarily always present a full picture of the statistical complexity of the problem. They characterize the complexity of the most difficult instances, but potentially many other instances are much easier. An ideal algorithm should adapt to the complexity of a particular instance and incur smaller regrets on easy instances than the worst-case instances. Thus, an ideal regret bound should be eestance-dependentt that is, depending on some properties of each instance. Prior works designed algorithms with instance-dependent regret bounds that are stronger than minimax regret bounds, but they are often not directly comparable because they depend on different properties of the instances, such as the gap conditions and the variance of the value function (Zanette & Brunskill 2019 Xu et al. 2021 Foster et al. 2020 Tirinzoni et al. 2021).
A more ambitious and challenging goal is to design instance-optimal algorithms that outperform, on every instance, all consistent algorithms (those achieving non-trivial regrets all instances). Past works designed instance-optimal algorithms for multi-armed bandit (Lai et al. 1985). linear bandits Kirschner al.; 2021 Hao et al.) 2020), Lipschitz bandits (Magureanu et al. 20044), and ergodic MDPs (Ok et al. 2018). However, instance-optimal regret bounds for tabular reinforcement learning
remain open question, despite recent progress (Tirinzoni et al. 2021 2022). The challenge partly

---

Published as a conference paper at ICLR 2023
stems from the fact that the existence of such an instance-optimal algorithm is even priori unclear for general interactive decision making problems. Conceivably, each algorithm can have its own specialty on subset of instances, and no algorithm can dominate all others on all instances.
Somewhat surprisingly, we prove that there exists a simple algorithm (T2C, stated in Alg. D that is asymptotic instance-optimal for general interactive decision making problems with finite number of decisions. We determine the exact leading term of the optimal asymptotic regret for instance f to be C()) n.. Here, is the number of interactions and C(f) is a complexity measure for the instance I that intuitively captures the difficulty of distinguishing ʃ from other instances (that have different optimal decisions) using observations. Concretely, under mild conditions on the interactive decision problem, our algorithm achieves an asymptotic regret C(f) In n (Theorem 5.2) for every instance f, while every consistent algorithm must have an asymptotic regret at least C(T)ln Inn (Theorem 3.2).
Our algorithm consists of three simple steps. First, it explores uniformly for o(1) )-frccion of the steps and computes the MLE estimate of the instance with relatively low confidence. Then, it tests whether the estimate instance (or, precisely, its associated optimal decision) is indeed correct using the most economical set of queries/decisions. Concretely, it computes a set of decisions with mini- mal regret, such that, using log-likelihood ratio test, it can either distinguish the estimated instance from all other instances (with different optimal decisions) with high confidence, or determine that estimation
incorrect. Finally, with the high-confidence estimate, it commits to the optimal decision of the estimated instance in the rest of the steps. The algorithmic framework essentially reduces the problem to the key second
optimal hypothesis testing with active data collection.
Our results recover the classical gap-dependent regret bounds for multi-armed bandits (Lai et al.
[985) and prior works on linear bandits (Lattimore & Szepesvari 2017 HHo al. 2020). As an
instantiation of the general algorithm, we present the first asymptotic instance-optimal algorithm for tabular RL, improving upon prior instance-dependent algorithms (Xu et al. 2021; Simchowitz &
Jamieson 2019
Tirinzoni et al. 2021 2022).
1.1 ADDITIONAL RELATED WORKS
Some algorithms are proved instance-optimal for specific interactive decision making problems. Variants of UCB algorithms are instance-ppiimll for bandits with various assumptions (Lattimore)
& Szepesvári 2020 Gupta et al. 2021: Tirinzoni et al. 2020 Degenne et al.] 20200] Magureanu
jet al., 2014), but are suboptimal for linear bandits (Lattimore & Szepesvari, 2017). These algo-
rithms rely on the
principle to deal with expl explooaatioeexxloiaaaioo
tradcoff, whereas our algorithm explicitly computes the best tradeoff. Kirschner et al. (2021): Lat-
timore & Szepesvari y Hao et al. (2020) design non-optimistic instance-optimal algorithms for linear bandits. There are also cestance-optime
algorithms for ergodic MDPs where the regret is less sensitive to the exploration policy (Ok et al., 2018 Burnetas & Katehakis 1997| Graves & Lai
1997], interactive decision making with finite hypothesis class, finite state-action space, and known rewards (Rajeev al. 1989), and interactive decision making with finite observations (Komiyama cet al. 2015).
The most related problem setup is structured bandits (Combes et al. 2017 Van Parys & Golrezaei 2020 Jun & Zhang 2020), where the instances also belong to an abstract and arbitrary family F. The structured bandits problem is a very special case of general decision making problems and does not contain RL because the observation is scalar. In contrast, the observation in general decision making problems could be digeenimnsiional (e.g., a trajectory with multiple states, actions, and rewards for episodic RL), which makes our results technically challenging.
Many algorithms' regret bounds depend on some properties of instances such as the gap condition. Foster et al. (2020) prove gap-dependent regret bound for contextual bandits. For reinforcement
learning, the regret bound may depend on the variance of the optimal value function (Zanette &
Brunskill 2019) or the gap of the Q-function (Xu et al. 1 Simchowitz & Jamieson 2019 Yang et al. 2021). Xu et al. (2021): Foster et al. (2020) also prove that the gap-dependent bounds cannot be improve some instances. To some extent, these instance- -eeeendedd lower bounds can be viewed as minimax bounds for a fine-grained instance family (e.g., all instances with the same Q-function gap), and therefore are different from ours.
2

---

Published as a conference paper at ICLR 2023
2 SETUP AND NOTATIONS
Interactive decision making problems. We focus on interactive decision making problem with structured observations (Foster et al. 2021). which includes bandits and reinforcement learning as special cases. An interactive decision making problem is defined by a space of decisions II. observations O, a reward function R : O + I., and a function I (also called an instance) that maps a decision π II to a distribution over observations f[T]. We use [.)]()) : O + RR to denote the density function of the distribution f[z]. We assume that the reward R is deterministic and known.
An environment picks an ground-truth instance f from a instance family F, and then an agent (which knows the instance family F but not the ground-truth f*) interacts with the environment for n total rounds. In round S n,
(a) the learner selects decision Te from the decision class II. and (b) the environment generates an observation following the ground-truth distribution f (mTe) and reveals the observation. Then the agent receives a reward R(oo).
For example, multi-armed bandits, linear bandits, and episodic reinforcement learning all belong to interactive decision making problems. For bandits, a decision т corresponds to an action and an observation corresponds to reward. For reinforcement learning, decision и is a deterministic policy that maps from states to actions, and an observation o is a trajectory (including the reward at each step). In other words, one round of interactions in the interactive decision making problem corresponds to one episode of the RL problem. We will formally discuss the RL setup in Section 5
Let (T) = Eo- [R()]]
[[[ be the expected reward for decision π under instance f. and π (f) &
argmax, (x) the optimal decision of instance f. The expected regret measures how much worse the agent's s decision is than the optimal decision:
(1) We consider the case where the decision family IT is finite, and every instance E F has a unique optimal decision, denoted by x (J). We also assume that for every J E F and π E IT, 0 S R(o) S
Reg = E, [Σi=1 mmax (T) R2 (m))]
Rmax almost surely when o is drawn from the distribution f[r], and sup, f(=((o) < sc.
Consistent algorithms and asymptotic instance-optimalliy. We first note that it's unreasonable to ask for an algorithm that can outperform match any arbilrary algorithm on every instance. This because, for any instance ʃ E F, a bespoke algorithm that always outputs (J") can achieve zero regret instance ff (though it has terrible regrets for other instances). Therefore, if an algorithm can outperform or match any algorithm on any instance, it must have zero regret on every instance, which is generally impossible. Instead, we are interested in finding an algorithm that is as good as any other reasonable algorithms that are not completely customized to a single instance.
We say algorithm is consistent if its expected regret satisfies Regy,, o(n²) for every p > 0 and f E F (Lai et al.) 1985). Most of the reasonable algorithms are consistent, such as the UCB algorithm for multi-armed bandits (Lattimore & Szepesvári, 2020), UCBVI, and UCB-Q algorithm for tabular reinforcement learning (Simchowitz & Jamieson 2019 Yang et al.) (02T), because all of them achieve asymptotically (Inn) regrets on any instance, where O hides constants that depend on the property of the particular instance However, consistent algorithms exclude the algorithm mentioned in the previous paragraph which is purely customized to a particular instance.
We say an algorithm is asymptotically instance-optimal if on every instance f E F, lim x R In is the smallest among all consistent algorithms (Lai al., 1985). We note that even though an instance-optimal algorithm only needs to perform as well as every consis- tent algorithm, a priori, it's still unclear if such an algorithm exists.
Some prior works have also used slightly weaker definition in place of consistent algorithms, e.g., a-uniformly good algorithms in Tirinzoni et al. (2021). which allows a sublinear regret bound (nn) for some constant < 1. The alternative definition, though apparently includes more algorithms, does not change the essence, Our algorithm is still instance-optimal up to a constant factor- simple modification of the lower bound part of the proof shows that its asymptotic regret is at most
Here the regret scales in logn because we are in the asymptotic setting where the instance is fixed and tends to infinity. If the instance can depend on n (which is not the setting are interested in), then the minimax regret typically scales in (vyR).
3

---

Published as a conference paper at ICLR 2023
(1-a) a) factor bigger than any a-uniformly good algorithms any instance. This paper thus primarily compares with consistent algorithms for simplicity.
MAIN RESULTS
In this section, we present an intrinsic complexity measure C(J) of an instance / (Section 3.1 and an instance-optimal algorithm that achieves an asymptotic regret C(J) In n. (Section 3.2)
3.1 COMPLEXITY MEASURE AND REGRET LOWER BOUNDS
In this section, our goal is to understand the minimum regret of consistent algorithms, which is an intrinsic complexity measure of an instance. We define deeenneedeeennentt complexity measure C() and prove that any consistent algorithm must have asymptotic regret at least C(J) In
The key observation is that any consistent algorithm has to collect enough information from the observations to tell apart the ground-truth instance from other instances with different optimal de- cisions. Consider the situation when a sequence of decisions is insufficient to distinguish two instances, denoted by f and g, with different optimal decisions. If an algorithm achieves a sublinear regret on f. the sequence must contain ' (f) (the optimal decision for f) at least o(n) times. As result, if the true instance were g. the algorithm suffers linear regret (due to the linear number of πt" (f)), and therefore cannot be consistent.
An ideal algorithm should find out decisions that can most efficiently identify the ground-trutt truuh in- stance (or precisely the family of instances with the same optimal decision as the ground-truth However, decisions collect information but also incur regrets. So the algorithm should pick list of decisions with the best tradeoff between these two effects-minimizing the decisions' regret and collecting sufficient information to identify the true instance. Concretely, suppose sequence of de- cisions includes Wxx occurrences decision म. The regret of these decisions is Σxen Wx A(f, T), where A(f, T) A Rf))*(()) (T) is the sub-optimality gap of decision We use KL diver- gence between the observations of π under two instances f and (denoted by [ [=]]][[[=]] to measure πt s's power to distinguish them. The following optimization problem defines the optimal mixture of the decisions (in terms of the regret) that has sufficient power to distinguish f from all other instances with different optimal decision.
C(f.n) A min
WER ΣTEM (=)(f.
(2)
s.t. Even DKL ([b]]lg()) 21, Vy E
(3)
||w|o00 $ n.
(4)
The last constraint makes sure that wx < even if the decision has regret (i.e., -m, A(J, mT) 0)- We only care about the case when n approaches infinity. The asymptotic complexity of is
C(f) A lim,- n(f,n).
(5)
In Eq. 3 we only require separation between instances f.g when they have different optimal decisions. As there are only finite decisions, there are finite equivalent classes, so and g are in principle separable with sufficient number of observations. Thus, the complexity measure C(f. n) is well defined as stated in the following lemma.
Lemma 3.1. For any F, C(S,n) n) is non-increasing in n, and there exists no > such that for all > no. C(f, n) < co. As corollary, C(f) < oo and is well defined.
Proof of Lemma 3.1 is deferred to Appendix B.T Section 3.I we formalize the intuition above and prove that C(T) is lower bound of the asymptotic regret, as stated in the following theorem.
Theorem 3.2. For every instance f F, the expected regret of any consistent algorithm satisfies Reg C())
lim sup "In
We prove Theorem 3.2 in Appendix B.2 Theorem 3.2 is inspired by previous works (Lattimore &
Szepesvari] 2017 Trrnzoni et al.) 2021). When applied to tabular RL problems, lower bound is
very similar to that in Tirinzoni et al. (2021) with the only difference that their optimization problems omit the second constraint (Eq. (4), which make slightly less tight (see Section B.5
4

---

Published as a conference paper at ICLR 2023
The complexity
measure C(f) reduces to the well-known inverse action gap bound O(EnEA Ne))o (a) for multi-armes bandits (Proposition B.2 and recovers the result of
Lattimore & Szepesvari 2017) for linear bandits (Proposition B.3p- For reinforcement learning, Tirinzoni al. (2221) prove that the instance-optimal bound can be smaller than the gap-dependent
bound O (5))00) (s a)) in Xu et al. (2021) and Simchowitz & Jamieson (019
3.2
INSTANCE-OPTIMAL ALGORITHMS
Algorithm 1 Test-to-Commit (T2C)
1: Parameters: the number of rounds of interactions n.
Step 1: Initialization.
2: Play each decision In times. We denote these decisions by { where Minit
[[I In In 1. and the corresponding observations by Jer"
3: Compute the max likelihood estimation (MLE) with arbitrary tie-breaking
argmax JEF Emart In ff (o.)
(6)
Step 2: Identification.
4: Let = (In n2 for shorthand, and & be the solution of the program defining C(f. m) Compute W, = (1+ 1/n) + 1/n for all ı E II.
5: Play each decision x for [w= nn times. Denote these decisions by { where m = Σn 02 [n)]], and the corresponding observations by {or]
:= and its corre- 6: Run the log-likelihood ratio test on instance f, the sequence of decision {
sponding observations {or) (that is, compute the event E defined in Eq.
Step 3: Exploitation.
7: if E true then
8:
Commit n" (f) (i.e., run x* (f) for the remaining steps).
9:
else
Run UCB for the remaining steps.
We first present the regret bound for our algorithm of the T2C algorithm. For simplicity, we consider
a finite hypothesis (i.e., [F] < cc) here, and extend to infinite hypothesis case in Section 5
We start by stating condition that excludes abnormal observation distributions f[x]. Recall that for any (0, 1), the Rényi divergence of two distributions p. is
(xlll) = - In J,, p(x)))(()))-5d) Sdr.
The Rényi divergence De(pllq) is non non-decreasing in Ç. and limętı (plll) = DKL (pllg) (an Er- ven Harremos) 2014). We require the limits converge uniformly for all instances 9 and decisions E IT with ( bounded away from (the choice of the constants in Condition is not critical our result), as stated below.
Condition 1. For any fixed > 0,6 > O, instance / E F, there exists Xn(a, f) such that for all À S Ao(a,e,f), g E F and E II, (f=x(f(m]lg(m) 2 min(Duu(leilll a.. Moreover, we require eo(a,e, 2 e min(1/a, ((() for some universal constants C1, 01,02,0 C3 > 0, where (f) is a function that only depends on
Condition holds for a wide range of distributions, such as Gaussian, Bernoulli, multinomial, Laplace with bounded mean, Log-normal (Gil et al.) (013).. and tabular RL where [[T] is dis-
tribution over trajectory consists of state, action and reward tuples (see Theorem [.1 for the proof of tabular RL). A stronger but more interpretable variant of Condition is that the log density ratio of [[r] and g[m] has finite fourth moments (see Proposition B.4), therefore Condition can also be potentially verified for other distributions.
The main theorem analyzing Alg. T shown below. The asymptotic regret of Alg. matches the constants in the lower bound (Theorem 3.2p. indicating its asymptotic instance- -attanc-optimmlltyy.
Theorem 3.3. Suppose F is finite hypothesis class and satisfies Condition The regret of Alg. R & C(
satisfies lim m
5

---

Published as a conference paper at ICLR 2023
Our algorithm is stated in Alg. | and consists of three steps: initialization, identification, and ex- ploitation. In the initialization step. we explore uniformly for a short period and compute the MLE estimate f of the true instance (Line 3 of Alg. D. where we only requires f to be accurate with moderate probability (i.e.. 1 1/ In n)). The estimation is used to compute the lowest-regret list of decisions that can distinguish the optimal decision of f. Since we only collect o(In n) samples, the regret of this step is negligible asymptotically.
In the identification step, we hold the belief that f's the true instance and solve C(f, (In In 2)444) to get the best list of decisions to fortify this belief (see Line 4 of Alg. D Then we collect more samples using this list (with minor decorations) boost the confidence of our initial estimation to 1 - 1/n (or reject when the estimation is not accurate) by the following log-likelihong ratio test:
E acc
A4 and xg))) # TT (f), Em In A(..((.)) Inn). a(m.](a)
Intuitively, if ff not the ground-truth f*, Elece is unlikely to hold because the expected log- likelihood ratio is non-positive: / (o)](//(([[((((())((() Hence, with high probability wrong guess cannot be accepted. On the other hand, the first con- straint (Eq. 33) the definition of C(f) guarantees that when f f", the expected log- log-likelihood ratio large for all E FF and π (g) + x (f), so an accurate guess will be accepted. In this step m = (In n). so Step 2 dominates the regret of Alg. In other words, the efficiency of the log-likelihood test is critical our analysis.
- - -DxI. [+]] < 0.
Finally in the exploitation step, the algorithm commits the optimal decision of f if it believes this estimation with confidence 1 - 1/n,, or run standard UCB algorithm as if on a multi-armed bandits problem (with a well- (In n)) regret) when the initial estimation not accurate (happens with probability at most 1/ In n). Hence, the expected regret here is (In n + Onn/nn n = O(1).
Our three-stage algorithm is inspired by Lattimore Szepesvari (2017). where their test in Step only uses the reward information. However, the observation for general interactive decision making problem contains much more information such as the transition tabular RL problems. contrast, the T2C algorithm relies on general hypothesis testing method (i.e., log- oggliiklihood ratio test) and achieves optimal regret for general interactive decision making problems.
PROOF SKETCHES OF THE MAIN RESULTS
In this section, we discuss the proof sketch of our main results. Section 4.1 discusses the proof sketch of the lower bound, and Section 4.2 shows the main lemmas for each step in Alg. T In
Section 4.3 we discuss the log- likeliidd ratio test in detail.
4.1 PROOF SKETCH OF THEOREM 3.2
Recall that C(J) is the minimum regret of list of decisions that can distinguish the instance f with all other instances g (with different optimal decision). Hence, to prove the lower bound, we show that the sequence of decisions played by any consistent algorithm must also distinguish f. and thus, C()) lower bounds the regret of any consistent algorithm.
For any consistent algorithm, number of interactions n > 0, and two instances f.g E F with different optimal decisions, let Pj... and Pg.n denote the probability space generated by running the algorithm on instances f and respectively for n rounds. Since f g have different optimal decisions, Py.,. and Pg.n. should be very - following the same proof strategy in (Lattimore) & Szepesvari 2017). we can show that
DKL. (Pr.lll) 2 (1 + (())) Inn. Let the random variable ne be the decision of the algorithm in round i. The chain rule of KL divergence shows
(P.(P)..lIPo..)> = E [E DKL = E, (Flelll)))))))
Now consider the vector w E !e!!!! where w. E [Ns o(1)) Inn). Based on the derivation above, we can verify that w is valid solution to C(F, and therefore
Regz, Ey
Σx n A(, (1 (1)) C(S, + Inn))nnn.

---

Published as a conference paper at ICLR 2023
Then the final result is proved by the fact that C(f) limn C(f, n(f
4.2 PROOF SKETCH OF THEOREM 3.3
In the following, we discuss main lemmas and their proof sketches for the three steps of Alg
Step 1: Initialization. In this step we show that the max likelihood estimation can find the exact instance (i.e., f = f*) with probability at least 1 1/ In and negligible regret. Note that the failure probability is not small enough directly commit to the optimal decision of ʃ (i.e., play rt (f()) forever), which would incur linear regret when * f Formally speaking, the main lemma for Step is stated as follows, whose proof is deterred to Appendix A.1
Lemma 4.1. Under Condition 1 with probability at least 1/ In we gel = f addition, the regret of Step I is upper bounded by O(
lam
Ia la
Lemma 4.1 is not surprising since the MLE only requires (log(1/6)) samples to reach a failure probability 5 in general (Van de Geer, 2000 Section 7). Here require 1/ In failure probability but allow In n nln In = 12( In n) samples, hence the result is expected for large enough n.
Step 2: Identification. In the identification step, we boost the failure probability to 1/n using the log-likelihood test. To this end, we compute the optimal list of decisions w { , /Tmm that distinguishes f by solving C(ʃ, (In In 22/2/4) (Line of Alg.
The choice of (In In n2 is not eritical, and could be replaced by any smaller quantity that approaches infinity - co. Then run the log-likee likelihood ratio test using the observations collected by executing the list decision w, and achieve the following:
when the true instance /* and the estimation f have different optimal decisions, accept f with probability at most 1 l/n;
(b) when f ft, accept f with probability at least 1 - 1/ In..
In Section we will discuss the log-likelihood ratio test in detail. Note that the regret after we falsely reject the true instance is O(In n) (by the regret bound of UCB algorithm), so we only require a 1/ In failure probability for (b) because then it leads to a (lnn)/ In O(1) expected regret. The main lemma for Step 2 is stated as follows, and its proof is deferred to Appendix A.2
Lemma 4.2. Under Condition ! for any finite hypothesis F. for large enough the following holds:
(a) conditioned on the event Tt* (f) + xf*),, El true with probability at most 1 1/n:
(b) conditioned on the event f = f*, Elco is true with probability at least 1 - 1/ Inn;
(c) conditioned on the event f f*, the expected regret of Step is upper bounded by (C(f*, (In In m)1/4) + o(1)) Inn. Otherwise, the expected regret of Step 2 is upper bounded by OInn In
Step 3: Exploitation. Finally, in Step 3 we either commits to the optimal decision x² when the estimation f is accepted, or run standard UCB algorithm with O n) regret (Lattimore & Szepesvári 2020). Combining Lemma 4.1 and Lemma 4.2 we can prove that
(a) the probability of Step 3 incurring a (n)) regret is at most 1/n, and (b) the probability of Step 3 incurring a O n) regret is at most 1/ In n.
As result, the expected regret in Step 3 is (1) and negligible. Finally Theorem 3.3 is proved by stitching the three steps together, and deferred to Appendix A.4
4.3 THE LOG-LIKELITOOD RATIO TEST
The goal of the log- logelikelihood ratio test is to boost the confidence of our initial estimation f to 1- 1/n, so that the algorithm can safely commit to its optimal decision in Step 3. In other words, the test should reject wrong estimation but also accept correct one.
7

---

Published as a conference paper at ICLR 2023
Formally speaking, in the test we observe a list of observations fo1, Om collected by the list of decision {T1,'.. TTm] on the true instance f", and achieve the following two goals simultaneously,
(a) when f and f are sufficiently different (i.e., their KL divergence is large in the sense that 2 (1 + o(1) In), accept f with probability at most 1/n, and (b) when f = f*, accept f with probability at least 1 1/ In..
Ei=1 DKI (f[x:]ll
We prove that the log- legeiikeiioodd ratio test with proper parameters achieves (a) and (b) under Condi- tion in the next lemma, whose proof is deferred to Appendix A.3
Lemma 4.3. Given two sequences of distributions P (P:) and Q {Qt) and sequence of independent random variables o for hm For any fixed X 0, > 0, and
D Di-1(P:l(Q:), the test event Eacc = 1 1 Q.(o.)
P(lod) 2 c] satisfies
Pro-o(Eaco S exp( Pro (Eaco)
(9)
exp(-X(mp c)).
(10)
To use Lemma 4.3 in the proof of Lemma C.2 we set c = In and poly(In In n).
Note that the choice of u in Line 4 of Alg. and Condition implies m3 = -i=1 Di D 2
= (1 + ((1) Inn when f ff have different optimal policies. So the conclusion of this lemma matches the first two items in Lemma 4.2
Exn DKL
and Lemma 4.3 closely related to the Chernoff- Stein lemma (see Chernoff 1959) and Mao (002 The- orem 4. 4.11)), with the difference that the failure probability of Eq. (10 in classical Chernoff-S Steiin lemma is a constant, while here it decreases with m. The proof of Eq. (9) is the same as in Chernof-- Stein lemma, and proof of Eq. (10) only requires an one-sided concentration of the empirical log- likelihood ratio. Indeed, the expectation of empirical log- logllikel ratio can be lower bounded P.(o.) by Ep E In Q.(o.). Dm DKL. (P))IQ;) > Σ Di (P: = mB. Hence, Prp(Ener) is the probability that the empirical log- likelihood ratio is (approximately) larger than its expecta-
tion. We also note that the concentration is non-trivial because we do not make assumptions on the
boundedness the tail of Q,
EXTENSIONS TO INFINITE HYPOTHESIS CLASS
Now we extend our analysis to infinite hypothesis settings, and instantiate our results on tabular RL. Our results in the infinite hypothesis case need two additional conditions. The first condition requires upper bound covering number of the hypothesis, and is used to prove infinite- hypothesis version of Lemma 4.2] Formally speaking, for any f.g E F, define their distance as [f[=[(o) gom]
d(f.g) sup
(11)
An e (proper) covering of F is a subset C C F, such that for any E F. there exists g E C with d(g. g') S The covering number N e) is the size of the minimum covering of F. Condition 2. There exists constant that depends on F such that InN((Fe)) S (ccln(1/e)) for every e 0. In addition, the base measure of the probability space has a finite volume Vol < cc.
The second condition upper bounds the distance of two instances by a polynomial of their KL divergence, and is used to prove a stronger version of Lemma 4.1
Condition 3. There exists a constant Cmin > O (which may depend on f*) such that for all E II and o E supp(f*(T]) [T( > Cmin. In addition. there exists a constant i(ft) > 0 that only depends on I and 05 > 0, such that for all f E F, E II, when (m)))[) $
- S
A lot of interactive decision making problems satisfy Conditions 3 such as multi-armed ban- dits and linear bandits with Bernoulli reward or truncated Gaussian reward. For bandit problems, Conditions 2 and only depend on the noise of the reward function and can be verified easily.
For tabular RL, an observation o denotes a trajectory (3) Q1, r.. Sr Qnz, QH,TH) where the state- action pairs (s),ax) are discrete random variables but the rewards rh are continuous. A decision
8

---

Published as a conference paper at ICLR 2023
< c0. In Appendix D we formally define the tabular RL problems where the reward т given (sp, an) follows a truncated Gaussian distribution, and prove that Conditions] I
: - A is mapping from the state space to action space, so [I] |||||
I
are satisfied stated in the following theorem.
Theorem 5.1. Let F be the family of tabular RL with truncated Gaussian reward and unique optimal
policies. Then Conditions
223
holds simultaneously.
For tabular RL with truncated Gaussian reward, the observation is mixture of discrete random variables (i.e., the states and actions Sh, az)) and continuous random variables (i.e., the rewards rh). To prove Conditions 3 we deal with the discrete and continuous part of the observation separately. We also have flexibility in the reward distribution, e.g., our proof technique can deal with other distributions such as truncated Laplace distribution. We present these unified conditions for bounded random variables, but Conditions 2 and do not hold for unbounded random variables because the base measure has an infinite volume (which contradicts to Condition 2), and the density of the observation cannot be lower bounded (which contradicts to Condition 3). However, we can still prove the same result using a slightly different approach (see Appendix
With Conditions 1 we can prove our main results for infinite hypothesis class. The asymptotic regret of Alg. [ in this case still matches the lower bound exactly. The proof of Theorem 5.2 is deferred to Appendix C.
Theorem 5.2. Suppose F is an infinite hypothesis class that satisfies Conditions 73 the regret of
Reg.-.n < <(()))
Alg. satisfies lim suPn-+00 lun
As corollary of Theorem 5.1 and Theorem 5.2, our algorithm strictly improves upon previous best
gap-dependent bounds 0 (e,e))) 1/4
[x, [+, a)) in Xu et al. (202)) Simchowwizz & Jamieson
2019 because the gap-dependent bounds are not tight for many instances TTrnnoon et al. 2021).
In the following we discuss the challenges when extending to infinite hypothesis settings.
Covering Number. With infinite hypothesis, we need to accept an accurate estimation even when there are infinitely many other choices. Recall that the accept event is
8/ = Vg E F and n" (g) # T" (f), Em In fixlle)) gp.]aa] 2 Inn]
(12)
So informally speaking, we need to show that with high probability,
Vg E Fnd (g) # T (f), Em, In flslloss R (DT-x(fllo) c)m 2 Inn,
(13)
g|a.][o;]
which is essentially an uniform concentration inequality as discussed in Section 4.3 So we resort to a covering number argument. The standard covering argument is not directly suitable in this case - even d(g. g¹) is small, it's still possible that
is very different from (n( ['][m (o)) (especially when g (o) is very close to 0). Instead, we consider the distribu- tion with density [o) A (g)(=]()) + eZ where Z is the normalization factor, and only prove a one-sided covering (that is, In(]|m][o)/g]] (o)) Z In(/(=(()/]]]]())) O(e)). We state and prove the uniform concentration in Appendix
Initialization. With infinite hypothesis, we cannot hope to recover the true instance f exactly some instances can be arbitrarily close to I* and thus indistinguishable. Instead, we prove that the estimation in Step I satisfies supren DKL(f* [x]]](]] < <poly( (llllr)) The main lemma of Step in the infinite hypothesis class case stated in Lemma C.1
CONCLUSION
In this paper, we design instance-optimal algorithms for general interactive decision making prob- lems with finite decisions. As an instantiation, our algorithm is the first instance-optimal algorithm for tabular MDPs For future works, we raise the following open questions.
(a) To implement Alg. we need to solve C(f. (In In /2), which is a linear programming with [II] variables and infinitely many constraints. However, [II] is exponentially large for tabular MDPs Can we compute this optimization problem efficiently for tabular MDPs?
(b) Although our algorithm is asymptotically optimal, the lower order terms may dominate the regret unless n is very large. Can we design non-asymptotic instance optimal algorithms?

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENT
The authors would like to thank Yuanhao Wang, Jason D. Lee for helpful discussions, and the support from JD.com.
REFERENCES
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pp. 1638-1646, 2014.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning, pp-
2017.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung. Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 1912. 2.6680, 2019.
Apostolos N Burnetas and Michael N Katehakis. Optimal adaptive policies for Markov decision processes. Mathematics of Operations Research, 22(1):222-25) 255, 1997.
Herman Chernoff. Sequential design of experiments. The Annals of Mathematical Statistics, 30(3): 755-770, 1959.
Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. Advances in Neural Information Processing Systems, 30, 2017.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Rémy Degenne, Han Shao, and Wouter Koolen. Structure adaptive algorithms for stochastic bandits. In International Conference on Machine Learning, pp. 2443-2452. PMLR, 2020.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Mag- netic control of tokamak plasmas through deep reinforcement learning. Nature, 602((897):414- 419, 2022.
Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. arXiv preprini (tt::2/02.04//00 2021.
Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3199 3210. PMLR, 13-18 Jul 2020.
Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement- perspective. arXiv preprint arXiv:2010.03104 2020.
Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487 2021.
Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used uni- variate continuous distributions. Information Sciences, 249:124 2013.
Todd L Graves and Tze Leung Lai. Asymptotically efficient adaptive choice of control laws incon- trolled markov chains. SIAM journal control and optimization, 35(3):715-743 1997.
Samarth Gupta, Shreyas Chaudhari, Gauri Joshi, and Osman Yağan. Multi-ammdd bandits with correlated arms. IEEE Transactions on Information Theory, 67(10):6711-6732 2021.
Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit. In International Conference Artificial Intelligence and Statistics, pp. 3536-3545. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2023
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 4868 4878, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020.
Kwang- Sung Jun and Chicheng Zhang. Crush optimism with pessimism: Structured bandits beyond asymptotic optimality. Advances in Neural Information Processing Systems, 33:6366-6376, 2020.
Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. Asymptotically optimal coermatiio-directer sampling. In Conference on Learning Theory, pp. 2777-2821. PMLR, 2021.
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in finite stochastic partial monitoring. Advances in Neural Information Processing Systems, 28, 2015.
Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. Artificial Intelligence and Statistics, pp. 728-737. PMLR, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Yingkai Li, Yining Wang, and Yuan Zhou, Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pp. 2173-2174. PMLR, 2019.
Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pp. 975-999, PMLR, 2014.
Cheng Mao. Hypothesis testing: Lecture notes for math 6263 at georgia tech. 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602,200 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature. 5 318(7540):599-333 2015.
Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforcement learning. Advances in Neural Information Processing Systems, pp. 8874-8882. 2018
A Rajeev, Demosthenis Teneketzis, and Venkatachalam Anantharam. Asymptotically efficient adap- tive allocation schemes for controlled iid processes: Finite parameter space. IEEE Transactions on Automatic Control, 34(3), 1989.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of Go without human knowledge. Nature, 550(7676):355 2017.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. In Advances in Neural Information Processing Systems, pp. 1153-1162, 2019.
Andrea Tirinzoni, Alessandro Lazaric, and Marcello Restelli. A novel confidence-baut based algorithm for structured bandits. In International Conference on Artificial Intelligence and Statistics, pp. 3175-3185. PMLR, 2020.
11

---

Published as a conference paper at ICLR 2023
Andrea Tirinzoni, Matteo Pirotta, and Alessandro Lazaric. A fully problem-dependen regret lower bound for finite-horizon mdps. arXiv preprint arXiv:2106.13013, 2021.
Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Near instance-optimal pac reinforce- ment learning for deterministic mdps. arXiv preprint arXiv:2203.09253 2022.
Sara Van de Geer. Empirical Processes in M-estimation. Cambridge University Press, 2000.
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions Information Theory, 6007):3777-3820, 2014.
Bart PG Van Parys and Negin Golrezaei. Optimal learning for structured bandits. arXiv preprint arXiv:2007.07302, 2020.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathicu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-344 2019.
Haike Xu, Tengyu Ma, and Simon S Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. arXiv preprint arXiv:2102.04000 2021.
Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Con- ference Artificial Intelligence and Statistics, pp. 1576-1584. PMLR, 2021.
Andrea Zanette and Emma Brunskill. Tighter learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312 2019.
regret bounds in reinforcement
12


Reviews:
[{"review_id": "XJSZ-DgYFV", "reviewer": "Reviewer_hFWY", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the theoretical bounds of the classical stochastic MAB problems, and if the conclusion of this paper is not wrong, then as far as I know, this would be the first paper to close the gaps between the asymptotic instance-wise regret upper bounds and lower bounds. \nTo be specific, this paper proves that for any consistent algorithm A with regret R_A(n) (n is the time horizon), it must satisfy that limsup_{n->\\inf}R_A(n)/log(n) >= C where C is a number determined by the instance and is independent of n and the algorithm. Then, this paper proposes an algorithm with regret bound R(n) such that limsup_{n->\\inf}R(n)/log(n) <= C, which perfectly matches the upper bound with no gap. ", "summary_of_the_review": "This paper studies a very fundamental problem of stochastic MAB, and proves the asymptotic upper bounds and lower bounds for this problem, which closes the gap that has existed for decades. The algorithm and and conclusions in this paper are novel, and should inspire and influence all MAB related researches to help improve the theoretical conclusions on the upper bounds and lower bounds. Thus, I tend to give a strong accept.", "strength_and_weaknesses": "Strength: This paper's results are very strong and impactful to the community. If the result is not wrong, then this should be the first instance-wise asymptotic algorithm for stochastic MAB, and closes the gap that has been studied for decades. The algorithm proposed in this paper uses a pretty novel method, and the linear-optimization based instance-wise factor is also new.\n\nWeakness: No major weakness, but it is hard for me to guarantee that the proofs and mathematical conclusions are 100% correct.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KDClVKB9eW", "reviewer": "Reviewer_Mrke", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes the first asymptotic instance-optimal algorithm for general interactive decision-making problems with a finite number of decisions. It provides an exact characterization of the complexity of each problem instance ${\\cal C}(f)$, which is related to the amount of information to distinguish instance $f$ from other instances with different optimal decisions. The paper designs a three step algorithm based on uniform sampling (to construct MLE of f), identification (to boost confidence in the estimate of f) and exploitation (to maximize reward), whose lengths are carefully adjusted, and proves an asymptotic regret of ${\\cal C}(f) \\log n$ recovering well-known instance-dependent regret bounds for bandits and improving upon instance-dependent regret bounds for reinforcement learning. ", "summary_of_the_review": "Overall, this paper presents a solid theoretical contribution to interactive decision-making problems. The addition of insights about the finite-time performance and the practical applicability of the proposed algorithm will further strengthen the paper.", "strength_and_weaknesses": "Strengths: \n\n-The paper proposes a framework for developing an instance-optimal algorithm that outperforms all consistent algorithms on every instance under mild conditions. The generality of the treatment in the paper, as it encompasses tabular reinforcement learning problems, is its main strength.\n\nWeaknesses: \n\n-No numerical results. It will be interesting to see how the algorithm performs with a finite horizon. \n\n-Computational complexity of the algorithm can be prohibitive (this was mentioned as a limitation). More discussion on how it scales with the problem size and how to make it computationally efficient will greatly benefit the paper. Please comment on the computational complexity of different interactive decision-making problems.\n \n-The algorithm requires the number of interactions as input.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "JELviYFVBS", "reviewer": "Reviewer_sYY8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies asymptotic instance optimality for interactive decision making with finite decision/action set. The model includes bandits and reinforcement learning, as long as the reward is a function of the observation.\n\nThe authors show that the standard, asymptotic lower bound by Lai and Robbins applies to this setting. They further adapt the approach by Lattimore et al (2017) to the more general setting to match the lower bound (asymptotically). Analysis is presented for both finite hypothesis classes and infinite hypothesis classes.", "summary_of_the_review": "In summary, the conceptual contributions of this paper are somewhat limited as they more or less directly extend prior work; however the technical contributions due to the generality of the setting are non-trivial and could inspire follow up work.\n", "strength_and_weaknesses": "The main contribution of the paper is the analysis of asymptotic optimality in a fairly general setting. The results require only mild conditions on the observation distributions, and the usual caveats of a finite action/decision space and a unique optimal action. At least in this context, I believe that the analysis of the log-likelihood ratio test is novel (Lemma 4.3 and its use in Theorem 3.3). The paper also discusses the required covering arguments to extend the result to infinite hpyothesis classes\n\nOn the other hand, the algorithmic approach is the same as in Lattimore et al (2017). The algorithm is neither practical from a sample complexity perspective (exponential lower order terms, horizon dependent, not worst-case optimal); nor computationally feasible unless both the hypothesis space and decision set is small. The result should therefore be understand a proof of concept with regard to the achievable sample complexity. It should also noted that going beyond this proof of concept is likely to require significantly further insights and assumptions.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "655ve67CBzW", "reviewer": "Reviewer_Li2S", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In Strength And Weaknesses", "summary_of_the_review": "In Strength And Weaknesses", "strength_and_weaknesses": "This paper designs the first asymptotic instance-optimal algorithm for interactive decision making problems, while prior works mostly focus on the hardest instance. Overall, I think this paper is interesting and novel. However, due to my heavy review load, I feel so bad I can't go through all the details of this paper. Based on what I have read, I would highly recommend this paper and give it a score of 8.\n\nIn this part, I will list some questions about some details in this paper.\n1. In the definition of $\\mathcal{C}(f,n)$, the authors mention the last constraint (4) makes sure $w_{\\pi}<\\infty$ even if the decision has no regret. Could the authors be more specific in explaining how $w_{\\pi}=\\infty$ if we remove constraint (4)?\n2. I'm a little confused with the instance complexity $\\mathcal{C}(f)$ and some other instance complexity in [1,2]. Could the authors give some comparisons in rebuttal?\n3. I understand this work provides a tight instance-optimal regret in the asymptotic regime. However, I'm more curious about how the technique used in this paper could inspire other future works. \n4. About the assumption that the optimal policy is unique. I'm thinking about a simple multi-arm bandit problem, where $\\mu_1=\\mu_2>\\mu_i$ for $i=3,...,n$. If the optimal policy is not unique, will the instance-optimality still hold? Or how will it fail?\n\nDue to my limited time, I will consider adding more questions in the rebuttal phase.\n\n[1]Koulik Khamaru, Eric Xia, Martin J Wainwright, and Michael I Jordan. Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning. arXiv preprint arXiv:2106.14352,2021b.\n[2]Li X, Yang W, Zhang Z, et al. Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient[J]. arXiv preprint arXiv:2112.14582, 2021\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1KvVJRc5Kq", "reviewer": "Reviewer_ahML", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper presents an asymptotic instance-optimal algorithm for decision problems under mild and natural conditions. This is interesting because it circumvents the weaknesses of minimax regret bounds. The idea behind the algorithm is that it alternates between having an estimate of the instance and testing whether estimate is correct. Doing this repeatedly results in increasing the confidence in the estimate. The optimality in the above statement, refers to comparing to the best \\emph{consistent} algorithm for the instance at hand -- and consistent algorithms are very natural to consider for this purpose.\n\n\nA typo: Page 2, belongs -> belong", "summary_of_the_review": "This is a very interesting and good paper, I recommend acceptance.", "strength_and_weaknesses": "Strengths:\n- interesting problem\n- natural but elegant approach\n- Well presented content\n\n\nWeaknesses:\n- the algorithm is not computable for every problem of interest, so it is unclear to me whether the results are also of practical relevance.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster