Learning Algorithms for Markovian Bandits:\\Is Posterior Sampling more Scalable than Optimism?
Authors: Nicolas Gast
Bruno Gaujal
Kimang Khun
Venue: Accepted by TMLR ()

Abstract: In this paper, we study the scalability of model-based algorithms learning the optimal policy of a discounted \blue{rested} Markovian bandit  problem with $n$ arms. There are two categories of model-based reinforcement learning algorithms: Bayesian algorithms (like PSRL), and optimistic algorithms (like UCRL2 or UCBVI).  A naive application of these  algorithms is not scalable because  the state-space is exponential in $n$. In this paper, we construct variants of these algorithms specially tailored to Markovian bandits (MB) that we call MB-PSRL, MB-UCRL2, and MB-UCBVI. \blue{We consider an episodic setting with geometrically distributed episode length, and measure the performance of the algorithm in terms of regret (Bayesian regret for MB-PSRL and expected regret for MB-UCRL2 and MB-UCBVI)}. We prove that, for this setting, all algorithms have a low regret in $\tilde{O}(S\sqrt{nK})$ -- where $K$ is the number of episodes, $n$ is the number of arms and $S$ is the number of states of each arm. Up to a factor $\sqrt{S}$, these regrets match the \blue{Bayesian minimax regret} lower bound of $\Omega(\sqrt{SnK})$ that we also derive.

Even if their theoretical regrets are comparable, the {\it time complexities} of these  algorithms vary greatly: We show that MB-UCRL2, as well as all  algorithms that use bonuses on transition matrices have a { time} complexity  that grows  exponentially in $n$.  In contrast, MB-UCBVI does not use bonuses on transition matrices and we show that  it can be implemented efficiently, with a time complexity linear in $n$. Our numerical experiments show, however, that its empirical regret is large. Our Bayesian algorithm, MB-PSRL, enjoys the best of both worlds: its running time is linear in the number of arms and its empirical regret is the smallest of all algorithms.
This is a new addition in the understanding of the power of Bayesian algorithms, that can often be  tailored to the structure of the problems to learn.

Published in Transactions on Machine Learning Research (11/2022)
Learning Algorithms for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?
Nicolas Gast
dicoolss.ass@@iinri gyuno.gonjal@tirrio kimang. chun@inriaa,
Bruno Gaujal
Kimang Khun
Unio. Grenobie Alpes, Inria, CNRS, Grenoble INP" LIG
38000 Crenoble, France
Institade of Engineering Uniu. Grenoble Alpes
Reviewed on OpenReview: https: openevvee........ net/ per/forum? id (4
Abstract
In this paper, we study the scalability of model-based algorithms learning the optimal policy of a discounted rested Markovian bandit problem with n arms. There are two categories of model-based reinforcement learning algorithms: Bayesian algorithms (like PSRL), and optimistic algorithms (like UCRL2 or UCBVI). A naive application of these algorithms not scalable because the state-space is exponential in n. In this paper, we construct variants of these algorithms specially tailored to Markovian bandits (MB) that we call MB- PSRL, MB-UCRL2, and MB-UCBVI. We consider an episodic setting with geometrically distributed episode length, and measure the performance of the algorithm in terms of regret (Bayesian regret for MB-PSRL and expected regret for MB-UCRL2 and MB-UCBVI We prove that, for this setting, all algorithms have a low regret in Ö(SvnK) where K is the number of episodes, n is the number of arms and S is the number of states of cach arm. Up to a factor V3, these regrets match the Bayesian minimax regret lower bound of ((vSnK) that we also derive.
Even if their theoretical regrets are comparable, the time complerities of these algorithms vary greatly: We show that MB-UCRL2, as well as all algorithms that use bonuses on transition matrices have a time complexity that grows exponentially n. In contrast, MB- UCBVI does not use bonuses on transition matrices and we show that it can be implemented efficiently, with a time complexity lincar in n. Our numerical experiments show, however, that its empirical regret is large. Our Bayesian algorithm, MB-PSRL, enjoys the best of both worlds: its running time is linear in the number of arms and its empirical regret is the smallest of all algorithms. This is a new addition in the understanding of the power of Bayesian algorithms, that can often be tailored to the structure of the problems to learn.
1 Introduction
Markov decision processes (MDPs) are a powerful model solve stochastic optimization problems. They suffer, however, from what is called the curse of dimensionalityy, which basically says that the state size of Markov process is exponential in the number of system components. This implics that the complexity of computing optimal policy is, in general, exponential in the number of system components. The same holds for general purpose reinforcement learning algorithms: they all have a regret and runtime exponential in the number of components, so they also suller from the same curse. Very few MDPs are known to escape from this curse of dimensionality. One of the most famous examples is the Markovian bandit problem in which a docision maker faces n Markov reward processes (the n components, that we will call the n arms in the rest of the paper), and must decide which arm activate at each decision epoch. Markovian bandit is well structured MDP; and optimal policy for such a system can be computed in O(n), by using the

---

Published in Transactions on Machine Learning Research (11/2022)
Gittins indices (computed for each arm independently),, and its value can be computed by using retirement values (see for example Whittle (1996)). In this paper, we investigate how reinforcement learning algorithms can exploit these two advantages.
We consider an episodic setting with geometrically distributed episode length, in which the optimal strategy for a decision maker who know all parameters of the system is to use Gittins index policy. We study a specialization of PSRL (Osband et al. 2013) to Markovian bandits, that we call Markovian bandit posterior sampling (MB-PSRL) that consists in using PSRL with prior tailored to Markovian bandits. We show that the Bayesian regret of MB-PSRL is sub-linear in the number of episodes and arms. We also provide an expected regret guarantee for two optimistic algorithms that we call MB-UCRL2 and MB-UCBVI, and that are based respectively on UCRL2 (Jaksch et al. 2010 and UCBVI (Azar et al. 2017]. They both use modified confidence bounds adapted to Markovian bandit problems. The upper bound for their regret is similar to the bound for MB-PSRL. This shows that in terms of regret, the Bayesian approach (MB- PSRL) and the optimistic approach (MB-UCRL2 and MB-UCBVI) scale well with the number of arms. We also provide Bayesian minimax regret lower bound for any learning algorithm in rested Markovian bandit problems with the aforementioned setting, which shows that the regret bounds that we obtain for the three algorithms are close to optimal.
The situation is radically different when considering the processing time: the runtime of MB-PSRI. is linear (in the number of arms), while the runtime of MB-UCRL2 is exponential. We show that this is not an artifact of our implementation of MB-UCRL2 by exhibiting a Markovian bandit problem for which being optimistic in each arm is not optimistic in the global MDP. This implics that UCRL2 and its variants (Bourel et al, 2020 Fruit et al., 2018 Talebi & Maillard 2018 Filippi et al.] 2010) cannot be adapted to have efficient runtime in Markovian bandit problems unless oracle gives the optimal policy. We argue that this non- scalability of UCRL2 and its variants is not a limitation of the optimistic approach but comes from the fact that UCRL2 relies on extended value iteration (Jaksch et al. 2010) needed to deal with upper confidence bounds on the transition matrices. We show that MB-UCBVI, an optimistic algorithm that docs not add bonus on transition probabilities and hence does not rely on extended value iteration, does not suffer from the same problem. Its regret is sub-linear in the number of episodes, and arms (although larger than the regret of both MB-PSRL and MB-UCRL2)), and its runtime is linear in the number of arms. This allows to conclude that, on the one hand, if a weakly coupled MDP or factored MDP can be solved efficiently when all the parameters are known, then the Bayesian approach is efficient both in terms of learning and computation time. On the other hand, knowing how to solve a weakly coupled MDP or a factored MDP efficiently is not sufficient for all optimistic algorithms to be computationally efficient.
We also conduct a series of numerical experiments to compare the performance of MB-PSRL, MB-UCRL2 and MB-UCBVI. They confirm the good behavior of MB-PSRL, both in terms of regret and computational complexity. These numerical experiments also show that the empirical regret of MB-UCBVI is larger than the regret of MB-PSRL and MB-UCRL2, confirming the comparisons between the upper bounds derived in Theorem 1 All this makes MB-PSRL. the better choice between the three learning algorithms.
Related work Markovian bandits have been applied to many problems such as single-machine scheduling, choosing a job in ressource constraint problems as well as other industrial research problems. Many appli- cations can be found in Puterman 2014 Section 3.6) and Gittins et al. 2011I. Gittins (1799 shows that rested Markovian bandit can be solved linearly in the number of arms using Gittins index policy. Therefore, several papers are focused on the complexity of computing Gittins index (Chakravorty & Mahajann 2014
Gast et al. ) In this paper, we focus on rested Markovian bandit problems with discount factor 3 where all reward functions and transition matrices unknown. A possible approach to learn under these conditions is to ignore the problem structure and view the Markovian bandit problem as generic MDP. There are two main familics of generic reinforcement learning algorithms with regret guarantees. The first one uses the optimism in face of uncertainly (OFU) principle. OFU methods build a confidence set for the unknown MDP and compute an optimal policy of the "best" " MDP in the confidence set, e.g., Bourel et al. 2020 0: Zhang& & Ji (2019) Talebi & Maillard (2018); Fruit et al. (2017): Azar et al. (2017); Bartlett Tewari
2012 1: Jaksch et al. (2010). UCRL2 (Jaksch et al.) 2010 is a well known OFU algorithm. The second family
uses Bayesian approach, the posterior sampling method introduced by Thompson 1933 Such algorithms
2

---

Published in Transactions on Machine Learning Research (11/2022)
keep posterior distribution over possible MDPs and execute the optimal policy of sampled MDP, see
6. Ouyang et al. 2 Agrawal & Jia (2017: Gopalan & Mannor 2015 Osband et al. (003 PSRL
OSband et al. 2013 is a classical example of Bayesian learning algorithm. All these algorithms, based on
OFU or on Bayesian principles, have sub-linear bounds on the regret, which mcans that they provably learn
the optimal policy. Yet, applied as-is to Markovian bandit problems, these bounds grow exponentially with
the number of arms.
Our work is not the first attempt to exploit the structure of MDP to improve learning. Factored MDPs (the state space can be factored into E No components) are investigated in Guestrin et al. (0003) where asymptotic convergence to the optimal policy is proved to scale polynomially in the number of components. The regret of learning algorithms in factored MDP with a factored action space is considered by Tian et al.
p020p; Rosenberg & Mansour (2020g; Xu & Tewari (2020); Osband & Van Roy (2014). Our work differs substantially from these. First, the Markovian bandit problem not factored MDP because the action space is global and cannot be factored. Socond, our reward is discounted over an infinite horizon while factored MDPs have been analyzed with no discount. Finally, and most importantly, the factored MDP framework assumes that the successive optimal policies computed by unspecified solver (oracle). There is no guarantee that the time complexity of this solver scales lincarly with the number of components, especially for OFU-based algorithms. For Markovian bandits, we get an additional leverage: when all parameters are known, the Gittins index policy is known to be an optimal policy and its computational complexity is linear in the number of arms. This reveals an interesting difference between Bayesian and extended value based algorithms (the former being scalable and not the latter). This difference is not present in the literature about factored MDPs because such papers do not consider the time complexity.
Our Markovian bandit setting is known in the literature as rested or restful bandit or a family of alternative bandit processes. Tekin & Liu (2012) consider a non-discounted setting, / = 1, and provide algorithms with logarithmic regret guarantee for rested as well as restless settings (a generalization of rested). However, they consider a notion of regret known as weak regret that measures how fast the learning algorithm identifies the best arm in stationary regime. So, it ignores the learning behavior at the beginning of learning process. In contrast, we consider the discounted rested bandit setting in which the regret of Tekin & Liu (2012) makes no more senses due to the discount factor and we propose regret definition that is frequently used in reinforcement learning literature and captures the performance of learning algorithm during the whole learning process. In addition, Ortner et al. (2012 2 Jung & Tewari (2019); ; Wang et al.] (2020b) consider a non non-discounted restless bandit setting in which only the state of chosen arms are observed by the learner. Ortner et al. (2012; Wang et al.] (2020b) propose optimistic algorithms for infinito-horizon sctting and provide regret bounds that are sub-linear in time. Again the discounted case is not considered in these papers while
particularly interesting bocause learning algorithms can leverage the optimal Gittins index policy. Jung & Tewari (2019) propose a Bayesian algorithm in the episodic finite-horizon setting and also provide a regret bound that is oub-linear in the mumber of episodes. However, the computational complexity is not studied in their work (the algorithm of Ortner et al. (2022) is intractable while the ones of Jung & Tewari (2019); Wang et al. (2020b) rely on the unspecified problem solver called oracle). Contrarily, we -provide both performance guarantee and computational complexity analysis of each algorithm that we consider in this paper. Finally, Killian et al. (021) consider a more general setting of restless bandits in which each arm is itsclf a MDP and the learner has to decide which arms to choose and which action to execute on each chosen arm under a global action constraint. The authors propose a Lagrangian suboptinal policy to solve the restless bandit. problem with known parameters and a sampling algorithm to learn their Lagrangian policy when the parameters are unknown. Unfortunately, no performance guarantee is provided in their work.
Since index policies scale with the number of arms, using Q-learning approaches to learn such a policy is also popular, see e.g., Avrachenkov & Borkar (202); Fu et al. (2019) Duff (1955). Duff (1995) addresses the same Markovian bandit problem as we do: their algorithm learns the optimal value in the restart-in-state MDP (Katehakis & Veinott Jr. 1987) for each arm and uses Softmax exploration to solve the exploration- exploitation dilemma. As mentioned on page 250 of Auer et al. (2002), however, there cxists no finite-time regret bounds for this algorithm. Furthermore, tuning its hyperparameters (learning rate and temperature) is rather delicate and unstable in practice.
3

---

Published in Transactions on Machine Learning Research (11/2022)
2
Markovian bandit problem
In this section, we introduce the Markovian bandit problem and recall the notion of Gittins index when the parameters (r",0") Q2) of all arms are known.
2.1 Definitions and main notations
We consider a Markovian bandit problem with n arms. Each arm (S",r", (Q") for (I....,m) =: [n] is Markov reward process with finite state space 8 of size S. Each has mean reward vector, r [0, 1]s, and transition matrix Q". When Arm is activated in state Da E 8a, it moves to state Va E - with probability (Ta, Ma). This provides a reward whose expected value is (r(a)). Without loss of generality, we assume that the state spaces of the arms are pairwise distinet: S n = 9 for a # b. In the following, the state of an arm a will always be denoted with an index a: we will denote such a state by Ta or Ma. As state spaces are disjoint, this allows us to simplify the notation by dropping the index from the reward and transition matrix: when convenient, we will denote them by r(x.) instead of rd (*()) and by (z ya) instead of (T Va) since no confusion is possible.
At time 1, the global state X1 is distributed according to some initial distribution p over the global state space & = S x.. x At time 1, the decision maker observes the states of all arms, x; (X ... Xt,)); and chooses which arm A, to activate. This problem can be cast as MDP that we denote by M with state space & and action space [n]. Let a E [n] and x, y E E. If the state at time t is X, = x, the chosen arm is As = a, then the agent receives a random reward RG drawn from some distribution on j0, 1] with mean r(za) and the MDP M transitions to state X,+1 = y with probability pa (x. y) that satisfies:
(a v) -
(Q( Ma)
if r.' ya for all a' &a; otherwise.
(1)
That is, the active arm makes a transition while the other arms remain in the same state.
Let II be the set of deterministic policics, i.e., the set of functions E> [n]. For the MDP M, denote by V (œ) the expected cunulative discounted reward of M under policy starting from an initial state a:
VT (x)=E
g 8 XI=0,AA-(XX)
An alternative definition of V is to consider a finite-horize problem with geometrically distributed length. Indeed, let H be a time-horizon geometrically distributed with parameter 1 - -3 > 0. We have
H Σ
VT (x)=E
Rs X1= A(-T(X
(2)
Problem 1. Given Markovian bandit M with arms, each is Markov reward process (Sa, r Qa) with finile state space of size S, find a policy n: S'x... S + [m] that mazimizes V (ax) for any state a distributed according to initial global state distribution p.
By a small abuse of notation, we denote by V (p) the expected reward when the initial state randomly generated according to p. (T) = p ((x VT (z). policy n, is optimal for Problem L VT (x) 2 V (x) for π and æ E. By Puterman (2014). such policy exists and does not depend on æ (or p). One well-known optimal policy is the Gittins index policy, defined below.
Throughout the paper, use capital letters (like Xt) denote random variables and small letter (like at) denote their realizations. Bold letters (X, or æ:) design vectors. Normal letters (X,aa or ra) are scalar values.
4

---

Published in Transactions on Machine Learning Research (11/2022)
2.2 Gittins index policy
It is possible to compute an optinal policy n. for Problem 1 in reasonable amount of time using the so called Gittins indices: Gittins (979 defines the Gittins index for any arm a in state Ta E 8 as
SI (a)) Z1 = =xo
GIndex(xa)
sup T>0
E 11 3t-1 Z1 Tal
(3)
where is a Markov chain whose transitions are given by Qa and T can be any stopping time adapted to the natural filtration of (Z))e21. So, Gittins index can be considered as the maximal reward density over time of arm at the given state.
GitLins 1979 shows that activating the arm having the largest current index is an optimal policy. Such a policy can be computed very efficiently: The computation of the indices of an arm with S states can be done in O(52) arithmetic operations, which mcans that the computation of Gittins index policy is lincar in the number of arms as it takes O(n5²) arithmetic operations. For more details about Gittins indices and optimality, we refer to Gittins et al. (2011): Weber 1992.. For a survey on how to compute Gittins indices, we refer to Chakravorty & Mahajan (2014), and to Gast et al. (2022) for a recent paper that shows how compute Gittins index in subcubic time (i.c., o(5*)) for each of the n arms).
3 Online learning and episodic regret
We now consider extension of Problem in which the decision maker does not know the transition matrices nor the rewards. Our goal is to design a reinforcement learning algorithm that learns the optimal policy from past observations. Similarly to what is done for finite-horizon reinforcement learning with deterministic
horizon see e.g., Zanette & Brunskil] (2019); Jin et al.] (2018) : Azar et al. (011)) Osband et al. (2013)
we consider a decision maker that faces a sequence of independent replicas of the same Markovian bandit problem, where the transitions and the rewards are drawn independently for each episode. What new here is that the time horizon H is random and has geometric distribution with expected value 1/(1 -3. It is drawn independently for each episode. This implies that Gittins index policy is optimal for decision maker that would know the transition matrices and rewards.
In this paper, we consider episodic learning algorithmss Let HI,..., H3 be the sequence of random episode lengths and let 4 == 1+ k-1 H; be the starting time of the kth episode. Tet Ok-1 = (X, Ri...., ,....,X-uu -1,,1, (ia-1,As, A R denote the observations made prior and up to episode kt An Episodic Learning Algorithm L is a function that maps observations Ox-1 to L(Ox-1), probability distribution whose support is IT. At the beginning of episode k, the algorithm samples मą L(Ox-1) and uses this policy during the whole kth episode. Note that one could also design algorithms where learning takes place inside each episode. We will see later that episodic learning as described here is enough to design algorithms that are essentially optimal, in the sense given by Theorem D and Theorem 2
For an instance M of a Markovian bandit problem and a total mumber of episodes K, we denote by Reg(K, K, C, M) the regret of learning algorithm L, defined as
Reg(K, M)
Σ V (X.) VITA (X..).
(4)
It is the sum over all episodes of the value of the optimal policy minus the value obtained by applying the policy Te chosen by the algorithm for episode k. In what follows, we will provide bounds on the expected regret.
A no-regret algorithm is an algorithm L such that its expected regret [Reg( (, M)] grows sub-linearly in the number of episodes K. This implies that the expected regret over episode k converges to 0 & goes to infinity. Such algorithm learns an optimal policy of Problem [
Note that, for discounted MDPs, an alternative regret definition (used for instance by He ct al. 2021 is to use the non-episodic version Σi (X,) V (X.)). In our defiitiio at Equation we use episodic
5

---

Published in Transactions on Machine Learning Research (11/2022)
approach where the process is restarted according to p after each episode of geometrically distributed length F4--
4 Learning algorithms for Markovian bandits
In what follows, we present three algorithms having a regret that grows like Ö(SynK), that we call MB- PSRL, MB-UCRL2 and MB-UCBVI. As their names suggest, these algorithms are adaptation of PSRL, UCRL2 and UCBVT to Markovian bandit problems that intend to overcome the exponentiality in of their regret. The structure of the three MB-* algorithms are similar and is represented in Algorithm D All algorithms are episodic learning algorithms. At the beginning of each episode, MB-* learning algorithm computes a new policy тę that will be used during an episode of geometrically distributed length. The difference between the three algorithms lics in the way this new policy 7y is computed. MB-PSRL uses posterior sampling while MB-UCRL2 and MB-UCBVI use optimism. We detail the three algorithms below.
Algorithm Pscudo-code of the three MB-* * algorithms.
input Discount factor 3, initial distribution (and prior distribution {Ø") JaE[n] for MB-PSRL)
1: for episodes k = 1.2.... do
2: Compute a new policy т (using posterior sampling or optimism). Set t& 1 Σ H;, sample X1, p and H₃ Gcom - B).
4: for L la to La + H4 1 do
5: Activate arm A₁- = TA (X.).
6: Observe Re and X,-1-
7: end for
end for
4.1 MB-PSRL
MB-PSRL starts with prior distribution da over the parameters (r" (r",Q"). At the start of each episode k MB-PSRL computes a posterior distribution of parameters (- Ox-1) for cach arm E [n] and samples parameters (rg Q2) from (- OR-1) ) for each arm. Then, MB-PSRL uses {(rg, Q2) Jaein) to compute the Gittins index policy Th that is optimal for the sampled problem. The policy T& is then used for the whole episode Note that as TH Gittins index policy, it can be computed efficiently.
The difference between PSRL and MB-PSRL is mostly that MB-PSRL uses a prior distribution tailored to Markovian bandit. The only hyperparameter of MB-PSRL is the prior distribution 6. As see in Appendix D MB-PSRL seems robust to the choice of the prior distribution, even if a coherent prior gives a better performance than a misspecified prior, similarly to what happens for Thompson's 's sampling [Russo
et al. 2018
4.2 MB-UCRL2
At the beginning of each episode k MB-UCRL2 computes the following quantities for each state Ha S": Na-1 (1ra) the number of times that Arm is activated before episode while being in state las and fx-1( and Qx-1(Zas)) are the empirical means of r(x.) and Q(F...). We define the confidence bonuses log log(2SnK(t) (x)( V (1N6 and ( = V ma, II - This defines confidence set M, follows: Markovian bandit problem M' is in M,, if for all E [n]] and xa E Sa:
- - s by (xa) and I|Q' (æa, QA-1(Ka. (I S (xa).
(5)
MB-UCRL2 then chooses policy mi that is optimal for the most optimistic problem Mj. E Mlg:
Th arg max max (p) MM,
(6)

---

Published in Transactions on Machine Learning Research (11/2022)
Note that explain later in Section 6.1 believe that there is no efficient algorithm to compute the best optimistic policy of Equation B
Compared to a vanilla implementation of UCRL2, MB-UCRL2 uses the structure of the Markovian bandit problem: The constraints Equation / are on Q whereas vanilla UCRL2 uses constraints on the full matrix P (defined Equation D. This leads MB-UCRT.2 use the bonus term that scales as VS/Ns-1(Ta) whereas vanilla UCRL2 would use the term in /55//N-i(2,
4.3 MB-UCBVI
At the beginning of episode k MB-UCBVI uses the same quantities Nk-1 (ata), P and ( :) MB-UCRL2. The difference lies in the definition of the bomus terms. While MB- MB-UCRL2 uses bomus the log(28nkKaa) that
reward and the transition matrices, MB-UCBVI defines a bonus (xa)(=))==T) V ma.x1, 14.)) is used on the reward only. MB-UCBVI computes the Gittins index policy Ti that is optimal for the bandit problem ( (f 1-1))))(
Similarly to the case of UCRL2, a vanilla implementation of UCBVI would use bonus that scales expo- nentially with the number of arms. MB-UCBVI makes an even better use of the structure of the learned problem because the optimistic MDP ( Q [))=))) is still Markovian bandit problem. This implies that the optimistic policy πe is Gittins index policy, and that can therefore be computed efficiently,
5 Regret analysis
In this section, we first present upper bounds on the expectod regret of the three learning algorithms. These bounds are sub-linear in the number of episodes (hence the three algorithms no-regret algorithms) and sub-linear in the number of arms. We then derive minimax lower bound on the Bayesian regret of any learning algorithm in the Markovian bandit problem.
5.1 Upper bounds on regret
The theorem below provides upper bounds on the regret of the three algorithms presented in Scction Note that since MB-PSRL. is Bayesian algorithm, we consider its Bayesian regrel, that the expectation over all possible models. More precisely, if the unknown MDP M is drawn from a prior distribution o, the Bayesian regret of a learning algorithm L is BayReg((, C, Φ) E[Reg( K, C, M)], where the expectation is taken over all possible values of M ~ & and all possible runs of the algorithm. The expected regret E [Reg(K, K, C, M)) is defined by taking the expectation over all possible runs of the algorithm.
Theorem 1. Let [(S n, K,9) Sn (log K/(1-B))² + SSK (log K/(1-B)) There exists universal constants C,C" and C" independent of the model (i.e., that do not depend S, n, K and B) such that:
For any prior distribution 6:
SnK log K BayReg(K, K, MB-MSRL-P... Φ) S <
f(S, n, K, K)
1 1
For any Markovian bandit model M:
SnK log K 1 1-
E. [Reg(K, MB-UBRBB, M)) S
VSS+ log
/ J(S,n, K,9),
VSS
SnK log K
E [Reg[K, K, MB-UCBVI, S C"
log
[(S, n, K29).
1 B
1
We provide a sketch of proof below. The detailed proof is provided in Appendix in the supplementary material.

---

Published in Transactions on Machine Learning Research (11/2022)
This theorem calls for several comments. First, it shows that when K Snn((1 B), the regret of MB-PSRL and MB-UCRL2 is smaller than
ò o( Svnk (1-3)3/2
(1 - /33/2
where the notation Ô mcans that all logarithmic terms removed. The regret of MB-UCBVI has an extra 1/(1 99) factor.
Hence, the regret of the three algorithms is sub-linear in the number of episodes K which means that they all are no-regret algorithms. This regret bound is sub-linear in the number of arms which is very significant in practice when facing a large number of arms. Note that directly applying PSRI., UCRL2 or UCBVI would lead to regret in Ô (5 (s*)kk)
Ô (vnS=K). which is exponential in n.
Second, the upper bound on the expected regret of MB-UCRL2 (and of MB-UCBVI) is guarantee for a specific problem M while the bound on Bayesian regret of MB-PSRL is a guarantee in average overall the problems drawn from the prior ø. Hence, the bounds of MB- and MB-UCBVI are stronger guarantee compared to the one of MB-PSRL. Yel, as we will see later in the numerical experiments reported Section MB-PSRL seems to have smaller regret in practice, even when the problem does not follow the correct prior. An interesting open question would be to find prior that would guarantoe that MB-PSRL has good worst-case regret bound. We do not know if such prior exists and to the best of our knowledge, this question is also open for the classical PSRL. Note that there exist Bayesian type algorithms with worst-case guarantees, see e.g., [Ishfaq et al. 2021 Agrawal et al. 2021 Wang et al.) 2020a Agrawal & Jia 2017p but they contain an optimistic part and it is not clear how to implement them in an efficient manner for Markovian bandits.
Third, the result of Theorem is the statistical evaluation of the three learning algorithms and does not require them to use Gittins index policy (in particular, MB-UCRL2 does not use Gittins index policy). What is required is that policy ग is optimal for the sampled problem M, for MB-PSRL (so that Lemma 3 applies) or for the optimistic problem Ms for MB-UCBVI (so that 11 is valid). Indeed, instead of using Gittins index policy for MB-PSRL or MB-UCBVI, assume that we have access to an oracle that provides an optimal policy for any given Markovian bandit problem. Then, the upper bound on regret in Theorem [| when MB-PSRL and MB-UCBVI use the oracle to compute policy Tg. Gittins index policy required only for the runtime evaluation as we will see in Section 6.
still holds
Finally, our bound in Equation is linear in S, the state space size of each arm. Having regret bound linear in the state space size is currently state-of-the-art for Bayesian algorithms, see e.g., Agrawal & Jia (0177; 1 Ouyang et al. (0117] and our discussion in Appendix A.3.4 For optimistic algorithms, the best regret. bounds are linear in the square root of the state size because they use Bernstein's concentration bounds instead of Weissman's inequality (Azar et al. 2017 yet this approach does not work in our setting due the randomness of episode's 's length and the bound of MB-UCBVI depends linearly on S. We discuss more about this in Appendix A.5.4 UCBVI has also been studied in the discounted case by He al. (2021). They use, however, different definition of regret, making their bound on the regret hardly comparable to ours.
Sketch of proof
A crucial ingredient of our proof is to work with the value function over a random finite time horizon (W defined below), instead of working directly with the discounted value function V. For a given model M, and a deterministic policy म, a horizon H and a time step h < H, we define by Wa (a:) the value function of policy n over the finite time horizon H - h + I when starting in x at time h. It defined as
W (M..H() = r (x)) Σ
(a. (MM.HHH)))
WEE
with WM.n. (x) ;= r (x)) and where n and p are reward vector and state transition matrix when following policy
8

---

Published in Transactions on Machine Learning Research (11/2022)
By definitions of W in Equation X and V in Equation 2 for fixed model M, policy a and a state æ, and time horizon H that is goometrically distributed, one has (x)) = E [ [..))
This characterization is important in our proof. Since the episode length H4 is independent of the observa- tions available before episode k, Ok-1, for any policy TH that is independent of Hş, one has
VVM TV (X.,) Ok-1, EE [WM... (Xx+) 1k-1, TT
(
(9)
In the above Equation g the expectation is taken over all initial state X and all possible horizon Ha.
Equation will be very useful in our analysis as it allows to work with either V or W interchangeably. While the proof of MB-PSRL could be done by only studying the function W, the proof of MB-UCRIE and MB-UCBVI will use the expression of the regret as function of V to deal with the non-determinism. Indeed, at episode k, all algorithus compare the optimal policy т. (that is optimal for the true MDP M) and a policy म chosen by the algorithm (that is optimal for a MDP My that is either sampled by MB-PSRL or chosen by an optimistic principle). The quantity D == W M.I.H. (Xt,) WM..HH (Xt,) equals:
W M,H.H, (X -- M.H. (Xtx) W M.,..H (Xt,) - M.I.H, (Xi.).
(10)
(4)
The analysis of the term B is similar for the three algorithms: it is bounded by the distance between the sampled MDP Mj and the true MDP M that can in turn be bounded by using a concentration argument (Temma based on Hoeffding's and Weissman's inequalities. Compared with the literature 4Azar et al., 2017 Ouyang al.] 2017), our proof leverages on taking conditional expectations, making all terms whose conditional expectation zero disappear. One of the main technical hurdle is to deal with the random episodes lengths H1..... Hy. This is required in our approach and is not needed in the classical analysis of finite horizons problems.
The analysis (A] depends heavily on the algorithm used. The easiest case is PSRL: As our setting is
Bayesian, the expectation of the first term (A) with respect to the model is zero (see Lemma 5 The case of MB-UCRL2 and MB-UCBVI are harder. In fact, our bonus terms are specially designed so that VM (z) is an optimistic upper bound of the true value function with high probability, that is:
Th Mr
(w) max max Vr (x) M'EM
V (ar).
(11)
This requires the use of V and not W and it is used to show that the expectation of the term A of Equation 10 cannot be positive.
5.2 Bayesian minimax lower bound
After obtaining upper bounds the regret, natural question is: can we do better? Or in other terms, does there exist learning algorithm with smaller regret? To answer this question, the metric used in the literature is the notion of minimax lower bound: for a given set of parameters (S, n, K, B), a minimax lower bound is a lower bound on the quantity inf sup Reg(K, C, M), where the supremum is taken among all possible models that have parameters (S, n, K, 3) and the infimum is taken over all possible lcarning algorithms. The next theorem provides a lower bound on the Bayesian regret. It is therefore stronger than minimax bound for two reasons: First, the Bayesian regret is average over models, which means that there exists at least one model that has a larger regret than the Bayesian lower bound; And second, in Theorem 2 we allow the algorithm to depend on the prior distribution ó and to use this information.
Theorem 2 (Lower bound). For any slate size S, number of arms n, discount factor 3 and wamber of episodes K 2 16S, there exists a prior distribution &f on Markovian bandit problems with parameters (S, n, K,3) B) such that, for any learning algorithm L:
1
SnK
BayReg(K, C, >
(12)
60 (1 B))
9

---

Published in Transactions on Machine Learning Research (11/2022)
The proof is given in Appendix B and uses a counterexample inspired by the one of Jaksch et al. (2010) Note that for general MDPs, the minimax lower bound obtained by Osband & Van Roy (2016); Jaksch et al.
(2100) says that learning algorithm cannot have a regret smaller than ((VSAAT), where S is the number of states of the MDP, Å is the number of actions and I is the number of time steps. Yet, the lower bound of
Osband & Van Roy 2016); Jaksch et al. (2010) is not directly applicable to our case with S = 5" because Markovian bandit problems are very specific instances of MDPs and this can be exploited by the learning algorithm. Also note that this lower bound on the Bayesian regret is also lower bound on the expected regret of any non-Baycsian algorithm for any MDP model M.
Apart from the logarithmic terms, the lower bound provided by Theorem 2 differs from the bound of Theorem 1 by a factor VS/(1- 3). This factor is similar to the one observed for PSRL and UCRL2 (Osband ctt al. 2013 Jaksch et al., 2010 There are various factors that could explain this. We believe that the extra Tactor 1/(11 - B) might be hall due to the episodic nature of MB-PSRL and MB-UCRL2 (when 1/(1- - B) is large, algorithms with internal episodic updates might have smaller regret) and half due the fact that the lower bound of Theorem 2 is not optimal and could include term 1/ 1/VI-B (similar to the term O(vD) of the lower bound of Osband & Van Roy (2016); Jaksch et al. (2010)). ). The factor vS between our two bounds comes from our use of Weissman's 's inequality. It might be possible that our regret bounds are not optimal with respect to this term although such an improvement cannot be obtained using the same approach of Azar et al. 2017
6 Scalability of learning algorithms for Markovian bandits
proposed Gittins indices. This is because previous solutions were based on Dynamic Programming in the global MDP which are computa- tionally expensive. Hence, after establishing regret guarantees, we are now interested in the computational complexity of our learning algorithms, which is often disregarded in the learning literature.
Historically, Problem ! was considered unresolved until Gittins 1979
6.1 MB-PSRL and MB-UCBVI are scalable
If one excludes the simulation of the MDP, the computational cost of MB-PSRL and MB-UCBVI of each episode is low. For MB-PSRL, its cost is essentially due to three components: Updating the observations, sampling from the posterior distribution and computing the optimal policy. The first two are relatively fast when the conjugate posterior has a closed form: updating the observation takes O(1) at each time, and sampling from the posterior can be done in ( more details on posterior distributions are given in Appendix D When the conjugate posterior implicit (i.e., under the integral form), the computation can be higher but remains linear in the number of arms. For MB-UCBVI, the cost is due to two components: computing the bonus terms and computing the Gittins policy for the optimistic MDP. Computing the bonus is linear in the number of bandits and the length of the episode. As explained in Section 2.2 the computation of the Gittins index policy for a given problem can be done in O(nS*). Hence, MB-PSRL and MB-UCBVI have a regret and a runtime both linear in the number of arms.
6.2 MB-UCRL2 is not scalable because it cannot use an Index Policy
While MB-UCRL2 has a regret equivalent to the one of MB-PSRL, its computational complexity, and in particular the complexity of computing an oplimústic policy that maximizes Equation D does not scale with n. Such policy can be computed by using entended value iteration (Jaksch et al. 2010 This computation is polynomial in the number of states of the global MDP and is therefore exponential in the nunber of arms, precisely ((nS2n). For MB-PSRL (or MB-UCBVI), the computation is easier because the sampled (optimistic) MDP is Markovian bandit problem. Hence, using Gittins Theorem, computing the optimal policy can be done by computing local indices. In the following, we show that it is not possible to solve Equation T by using local indices. This suggests that MB-UCRL2 (nor any of the modifications of UCRL2's variants that would use extended value iteration) cannot be implemented efficiently.
More preciscly, find an optimistic policy (that satisfies Equation 11 UCRL2 and its variants, e.g., KL- UCRL (Filippi et al. 2010), compute policy Te that is optimal for the most optimistic MDP in M2. This
10

---

Published in Transactions on Machine Learning Research (11/2022)
can be done by using extended value iteration. We now show that this cannot be replaced by the computation of local indices.
Let us consider that the estimates and confidence bounds for given arm are Bu = (f=, bas b8). We say that an algorithm computes indices locally for Arm if for each Fa E 8", it computes index 78" (ara) by using only 8 but not 3 for any d' + a. We denote by 7 the index policy that uses index 18 for arm a and by Mi the set of Markovian bandit. problems M' that satisfy Equation 5
Theorem 3. For any algorithm that computes indices locally there exists a Markovian bandit problem M, an initial state a and estimates Bax = (f Q0, by 62) such that M MI(B and
sup (B)
R(B) VM val.
(x) < sup (x).
C is obtained by constructing set M and two MDPs M1 and M2 in M such that Equation cannot hold simultaneously for both M1 and M2.
Proof. The proof presented in Appendix
]
This theorem implics that one cannot define local indices such that Equation 11 holds for all bandit problems M E Mr. Yet, the use of this inequality is central in the regret analysis of UCRL2 (see the proof of UCRL2 (Jaksch et al. 2010 This implies that the current methodology
obtain regret bounds for UCRL2 and
its variants, e.g., [ourel et al. (2020); Fruit et al. (2018) : Talebi & Maillard (218)); Filippi et al. 2010), that use Extended Value Iteration is not applicable lo bound the regret of their modified version that computes
indices locally.
Note that for any set M such that M E M, there still exists an index policy x innd that is optimistic because all MDPs are Markovian bandit problems. This optimistic index policy satisfies
sup V sup VT.
M'EM
This means that restricting index policies is not a restriction for optimism. What Theorem shows is that an optimistic index policy can be defined only after the most optimistic MDP M E M is computed and computing optimistic policy and M simultancously depends on the confidence sets of all arms.
Therefore, we believe that UCRL2 and its variants cannot compute optimistic policy locally: they should all require the joint knowledge of all JaE]].]]]
7 Numerical experiments
In complement to theoretical analysis, we report, in this section, the performance of our three algorithms in model taken from the literature. The model is an environment with 3 arms, all following Markov chain that is obtained by applying the optimal policy on the river swim MDP. A detailed description is given in Appendix D along with all hyperparameters that we used. Our numerical experiments suggest that MB-PSRL outperforms other algorithms in term of average regret and computationally less expensive than other algs To ensure reproducibility, the code and data of our experiments are available https://gitlab. inria. wwwpuu///eernnnnng--eeeeteeeaara
Performance result We investigate the average regret and policy computation time of each algorithm. To do so, run each algorithm for 80 simulations and for K = 3000 episodes per simulation. We arbitrarily choose the discount factor 3 0.99. In Figure [(a) algorithms. We obscrve that the average regret of UCBV is larger than those of MB-PSRL and MB- UCRL2 Moreover, we observe that MB-PSRL obtains the best performance and (hat its regret seems to grow slower than OVVK). This in accordance to what was observed for PSRL (Osband et al. 2013). Note that the expected number of time steps after K episodes K/(1 - :3) which means that in our sctting with K = 3000 episodes there are 300 000 time steps in average. In Figure [(b] we compare the computation time of the various algorithms. We observe that the computation time (the y-axis is in log-scale) of MR-PSRT.
show the average cumulative regret of the 3
11

---

Published in Transactions on Machine Learning Research (11/2022)
3000
MBB-UBVI
MB-UCBVI
Time per episode (seconds)
MB-UCRL2
2500
MB-UCRL2
MB-UCRL2
NB-UCBVI
Average regret
2000
MB-PSRL
10
ME-PSRL
1500
10"
1000
MB-UCRL2
10
MB-UCBVI
500
MB-PSRL
MB-PSRL
500
1500
2000
3000
500
1000
1500
2000
2500
3000
Number of episodes
Number of episodes
(a) Average cunulative regret function of number of (b) Average runtime per episode. The vertical axis log- episodes.
scale.
Figure Experimental result for the three 4-state random walk arms given in Table ! The 2-axis is the number of episodes. Each algorithm is identified by unique color for all figures.
and MB-UCBVI, the index-based algorithms, are the fastest by far. Moreover, the computation time of these algorithms seem to be independent of the number of episodes. These two figures show that MB-PSRL has the smallest regret and computation time among all compared algorithms.
Robustness (larger models and different priors) To test the robustness of MB-PSRL, we conduct two more sets experiments that are reported in Appendix They confirm the superiority of MB-PSRL. The first experiment an example from Duff (1995) with 9 arms each having 11 states. This model illustrates the effect of the curse of dimensionality: the global MDP has 11 states which implies that the runtime of MB-UCRL2 makes it impossible to use, while MB-PSRL and MB-UCBVI take few minutes to complete 3000 episodes. Also in this example, MB-PSRL seems to converge faster to the optimal policy than MB- UCBVI. The second experiment tests the robustness of MB-PSRL to the choice of prior distribution. We provide numerical evidences that show that, even when MB-PSRL is run with a prior & that is not the one from which M is drawn, the regret of MB-PSRL remains acceptable (around twice the regret obtained with a correct prior).
8 Conclusion
In this paper, we present MB-PSRL, modification of PSRL for Markovian bandit problems. We show that its regret is close the lower bound that we derive for this problem while its runtime scales linearly with the number of arms. Furthermore, and unlike what is usually the case, MB-PSRL does not have optimistic counterpart that scales well: we prove that MB-UCRT2 also has sub-linear regret but has a computational complexity exponential in the number of arms. This result generalizes to all the variants of UCRL2 that rely on extended value iteration. We nevertheless show that OFU approach may still be pertinent for Markovian bandit problem: MB-UCBVI, a version of UCBVI can use Gittins indices and does not suffer from the dimensionality curse: it has a sub-lincar regret terms of the number of episodes and number of arms well as linear time complexity. However its regret remains larger than MB-PSRL.
The broad implication of this work is that, the one hand, if weakly coupled MDP or factored MDP can be solved efficiently when all the parameters are known, then PSRL can be adapted to have efficient regret and runtime. On the other hand, solving weakly coupled MDP or factored MDP efficiently when all the parameters are known does not imply that all optimistic algorithms are computationally efficient. This is a major difference between the Bayesian and the optimistic approach.
References
Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-caso regret bounds for randomized least- squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6566-6573, 2021.
12

---

Published in Transactions on Machine Learning Research (11/2022)
Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. arXiv preprint Xiv: 1XX::100000000 775,07041, 2017.
Peter Auer, Nicolo Cesa- Gesa-Bianchi, and Paul Fischer. Finile-lime analysis of the multiarmed bandit problem. Machine learning, 47(2):235 256, 2002.
Konstantin E Avrachenkov and Vivek S Borkar. Whittle index based q-learning for restless bandits with averago reward. Automatica, 139:110186, 2022.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pp. 263 272. PMLR, 2017.
Peter L. Bartlctt and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement lcarning in weakly communicating mddps. arXiv prepriul arXiv:1205.260 2012.
Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening exploration in upper confi-
dence reinforcement learning. In International Conference on Machine Learning, pp. 1056-1066 PMLR, 2020.
Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trendso in Machine Learning, 5(1):1 122, 2012.
Jhelum Chakravorty and Aditya Mahajan. Multi-armed bandits, gittins index, and its calculation. Methods and applicalions of statisties in clivical trials: Planning, analysis, and inferential melhods, 2(416-435): 455, 2014.
Michael O Duff. Q-learning for bandit problems. In Machine Learning Proceedings 1995, pp. 209 217. Elsevier, 1995.
Sarah Filippi, Olivier Cappé, and Aurélien Garivier. Optimism in reinforcement learning and kullback- leibler divergence. In 2010 48th Arnual Allerton Conference on Communicattio, Control, and Computing (Allerlon), pp. 115-122. 122. IEEE, 2010.
Daniel Fink. saaees/d//////// cett:/aaes/d/6///OONI/II CON.IITTReeu 20TEX. pdf, 46, 1997.
compendium of conjugate priors.
See hllp://www. people. cornell.
Ronan Fruit. Exploration- Explonation-explotatton dilemma in Reinforcement Learning under various form of prior knowledge. PhD thesis, Université de Lille 1, Sciences et Technologies; CRIStAL UMR 9189, 2019.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret minimization in mdps with options without prior knowledge. Advances in Neural Information Processing Systems, 30, 2017.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-sparr-onnstraneed
exploration-expllotatoo in reinforcement learning. In International Conference on Machine Learning, pp. 1578 1586. PMLR, 2018
Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian & New Zealand Control Conference (ANZCC), pp. IEFE, 2019.
Nicolas Gast, Bruno Gaujal, and Kimang Khun. Computing whittle (and gittins) index in subcubic time. arXiv preprint arXim:2203.0520 05207, 2022.
John Gittins, Kevin Glazebrook, and Richard Weber. Multi-armed bandit allocation indices. John Wiley & Sons, 2011.
John C Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), 41 41(2):148-164 1979.
Aditya Gopalan and Shie Mannor. Thompson sampling for learning parameterized markov decision processes. In Conference Learning Theory, pp. 861-895 PMI.R, 2015.
13

---

Published in Transactions on Machine Learning Research (11/2022)
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha. Venkataraman. Efficient solution algorithms for factored mdps. Journal of Arlificial Intelligence Research, 19:399-466 2003.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. Advances in Neural Information Processing Systems, 34, 2021.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pp. 4607 4616. PMLR, 2021.
Thomas Jaksch, Ronald Ortner, and Peter Aucr. Near-optimal regret bounds for reinforcement learning. Jowrnal of Machine Learning Research, 11(51):1563 1600, 2010. URL http://jmlr. http://jmlr..ogppppeeree. orgppapers/vl1/
jaksch10a. html
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Young Hun Jung and Ambuj Tewari. Regret bounds for thompson sampling in episodic restless bandit problems. Advances in Newral Information Processing Systems, 32, 2019.
Michael N Katehakis and Arthur F Veinott Jr. The multi-armed bandit problem: decomposition and computation. Mathematics of Operations Research, 12(2):262 268, 1987.
Jackson A Killian, Andrew Perrault, and Milind Tambe. Beyond to act or not to act": Fast lagrangian approaches to general multi-action restless bandits. In Proceedings of the 20th International Conference on Aulonomous Agents and MulliAgent Systems, pp. 710-7107110 718, 2021.
Kevin Murphy. Conjugate bayesian analysis of the gaussian distribution. def, 1(2o2):16, 2007.
Ronald Ortner, Daniil Ryabko, Peter Aucr, and Rémi Munos. Regret bounds for restless markov bandits. In International conference on algorithmic learning theory, pp. 214-228. Springer, 2012.
Ian Osband and Benjamin Van Roy. Ncar-optimal reinforcement learning in factored mdps. Advances in Newral Information Processing Systems, 27, 2014.
Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. orXiv preprint arXiv:1608.025 02732, 2016.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pp. 2701-2710. PMLR, 2017.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown markov decision processes:
A thompson sampling approach. Advances in neural information processing systems, 30, 2017.
Martin L Puterman. Markow decision processes: discrete stochastic dynamic programming. John Wiley &
Sons, 2014.
Jian Qian, Ronan Fruit, Mattco Pirotta, and Alessandro Lazaric. Concentration incqualitics for multinoull random variables. arXiv preprint arXiv:2001.11595, 2020.
Aviv Rosenberg and Yishay Mansour. Oraclo-efficient reinforcement lcarning in factored mdps with unknown structure. arxio preprinl urXiv:2009.055: 05986, 2020.
Danicl J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial thompson sampling. Foundalions and Trendso in Machine Leurning, 11(1):1 96, 2018.
Mohammad Sadegh Talebi and Odalric-Ambryn Maillard. Varianco-aware regret bounds for undiscounted reinforcement learning in mdps In Algorithmic Learning Theory, pp. 770-805. PMLR, 2018.
14

---

Published in Transactions on Machine Learning Research (11/2022)
Cem Tekin and Mingyan Liu. Online learning of rested and restless bandits. IEEE Transactions on Infor- mation Theory, 58 58(8))5588-566 5611, 2012.
William Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):25529%)) 1933.
Yi Tian, Jian Qian, and Suvrit Sra. Towards minimax optimal reinforcement learning in factored markov decision processes. Advances in Neural Information Processing Systems, 33:19896 19907, 2020.
Roman Vershynin. High-dimennional probability: An introduction with applications in data science, vol- ume 47. Cambridge university press, 2018.
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, 2020a.
Siwei Wang, Longbo Huang, and John Lui. Restless-uch, an efficient and low-complexity algorithm for online restless bandits. Advonces in Neural Information Processing Systems, 33:11878 11889, 2020b.
Richard Weber. On the gittins index for multiarmed bandits. The Annals of Applied Probabilily, pp- 1024- 1033, 1992.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the 11 deviation of the empirical distribution. Hewkett-Packard Labs, Tech. Rep, 2003.
Peter Whittle. Optimal control: basics and beyond. John Wiley & Sons, Inc., 1996.
Ziping Xu and Ambuj Tewari. Reinforcement learning in factored mdps: Oracle-efficient algorithms and tighter rogret bounds for the non-cpisodic setting. Advances in Neural Information Processing Systems, 33:18226 18236, 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7314 PMLR, 2019.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. Advances in Newral Information Processing Systems, 32, 2019.
15


Reviews:
[{"review_id": "IrSKTZOyvE", "reviewer": "Reviewer_UZTB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n========\nThe studied setting (restful bandit, reward discounting factor matching with the geometric time-horizon length) allows to efficiently compute the exact optimal policy when problem-instance parameters are completely known, by using the celebrated Gittins indices policy. Since we are able to efficiently solve the planning version problems, plugging the exact planning solutions to common UCB-optimistic frameworks and TS posterior-sampling frameworks leads to the proposed new algorithms. Hence the overall picture of this paper is clear and intuitive. The key proofs seem rigorous and convincing.\n\nThe impossibility result in Section 6.2 is interesting. It does rule out some candidates for optimistic MB algorithms (computing local indices before picking an optimistic problem parameter instance won't have desired optimistic properties).\n\nWeekness and Concern\n=====================\nThe paper's approach heavily relies on exact planning via Gittins indices, which further heavily relies on the equivalence between discounted infinite time-horizons and finite geometric time horizons with a matching parameter. If the setting is slightly changed (e.g., all episodes have fixed uniform time-horizon lengths, or they are still geometrically i.i.d. but the parameter is no longer $1-\\beta$), then Gittins indices policy is no longer optimal. I would like to see more discussion this. Intuitively, as long as the rewards are discounted, when time-horizon lengths are sufficiently large, Gittins indices policy should be very close to the optimal policy, so maybe the regret guarantees of MB-PSRL and MB-UCBVI can still hold after carefully analyzing the error between Gittins indices policy and OPT.\n\nDue to the above reason, I am afraid it is not very fair to claim advantages over prior works on finite-horizon settings when making comparisons in the literature review section, they are just different settings.\n\nFinally, I think it is better to emphasize more on the regret guarantee of MB-PSRL in the abstract and introduction section. The presented regret upper-bound of MB-PSRL is for Bayasian regret, not for worse-case regret. It is an interesting open problem to find a prior for MB-PSRL so that the posterier can be efficiently maintained (e.g., having conjugate distributions) and upon which we can also develop worst-case style regret guarantees.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies Markovian bandit problems where\n a) arm state transitions are restful;\n b) rewards come with an expoential discounting factor $\\beta$;\n c) the time-horizen length in each episode is i.i.d. geometrically distributed with parameter $1-\\beta$.\n\nIn the paper, three new algorithms MB-PSRL, MB-UCRL and MB-UCBVI are presented, all achieving $\\tilde O(S\\sqrt {nK})$ regret, which is nearly optimal up to an $\\sqrt S$ factor compared to a Bayesian minimax regret lower-bound given in the paper. Among the three proposed algorithms, MB-PSRL and MB-UCBVI can be implemented efficiently.\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The paper's approach heavily relies on exact planning via Gittins indices, which further heavily relies on the equivalence between discounted infinite time-horizons and finite geometric time horizons with a matching parameter. If the setting is slightly changed (e.g., all episodes have fixed uniform time-horizon lengths, or they are still geometrically i.i.d. but the parameter is no longer $1-\\beta$), then Gittins indices policy is no longer optimal. I would like to see more discussion this. \n\nDue to the above reason, I am afraid it is not very fair to claim advantages over prior works on finite-horizon settings when making comparisons in the literature review section, they are just different settings.\n\nFinally, I think it is better to emphasize more on the regret guarantee of MB-PSRL in the abstract and introduction section. The presented regret upper-bound of MB-PSRL is for Bayasian regret, not for worse-case regret. It is an interesting open problem to find a prior for MB-PSRL so that the posterier can be efficiently maintained (e.g., having conjugate distributions) and upon which we can also develop worst-case style regret guarantees.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xrsTB4Cenz", "reviewer": "Reviewer_GzA5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nMarkovian bandits problem is interesting. But I’m not familiar with the literature in this specific setting.\n\n\nWeaknesses:\nPresentation could be improved.\nLiterature/references seems to be outdated.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is concerned with Markov bandits. Three algorithms MB-PSRL, MB-UCRL2, and MB-UCBVI are proposed. Theoretical guarantees and empirical investigations are provided.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. I'm not familiar with the specific Markovian bandit setting and probably I'm missing something, could you provide some motivating examples?\n\n2. \"its number of dimensions\" is unclear in the introduction. I guess here you mean the number of state is exponential in some dimensions. And I think tabular algorithms just pays the complexity about the size of the state space. The proposed algorithm computationally also has a dependence in n, so I don't quite understand the argument here.\n\n3. Some clarification is needed about Bayesian regret vs frequentist regret. Bayesian regret is a weaker guarantee. Recently there is a line of research that studies the frequentist regret for Beyesian/posterior sampling RL algorithms. The refs also seems to be outdated. See the below ref and the refs therein.\n\nRefs:\nWorst-Case Regret Bounds for Exploration via Randomized Value Functions\nImproved worst-case regret bounds for randomized least-squares value iteration\nRandomized Exploration for Reinforcement Learning with General Value Function Approximation\n\n4. I think MB-UCBVI should have a better bound, i.e., a root S bound which matches the lower bound. Could you comment on why the S dependence is loose in MB-UCBVI? This is different from the optimal S dependence in UCBVI.\n\n5. Could you comment on why there is no similar length of horizon factor (H) appearing in the bound? I think the problem setting is also sort of episodic, and in the standard MDP we would have H dependence.\n\n6. The beginning of the related work is not clear. It has an informal and vague description about the setting and I feel it does not help. I still do not see the definition after reading that. Maybe just drop this part since you formally introduce it later.\n\n7. In Alg1, I think the update of policy pi is missing. Probably add a line and pointers to the specific equations afterwards.\n\n8. “The situation is radically different when considering the processing time: the runtime of MB-PSRL is linear in the number of arms, while the runtime of MB-UCRL2 is exponential in n”   It looks like n is not the number of arms, but it turns out yes. Probably be consistent. \n\n9. \"Hence, MB-PSRL and MB-UCBVI successfully escape from the curse of dimensionality.\" Can you comment on what they mean specifically?\n\n10. I didn't check the proof, so no comment about its correctness.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KMK6Gmdwr5", "reviewer": "Reviewer_pt7A", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe claims in the paper are supported by the content. The authors claim that the three algorithms that they propose have regret guarantees that are linear in S and sublinear in K. The authors provided proof to support the results. I did not check the details but the theory part seems to be sound. The authors also claim that two algorithms MB-PSRL and MB-UCBVI are computationally scalable, whereas MB-UCRL2 is not. This is supported by empirical evidence. Overall, I think this is a solid work, the paper is overall well-written and easy to follow.\n\nWeaknesses:\n\nAfter reading the paper, I did not get why Markovian bandit is an important problem. What is the practical motivation to study this problem? I think some discussions would be helpful.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a general framework to solve the Markovian bandit problem and three algorithms under this framework. The authors provided regret guarantees for the three algorithms. The regret is linear in the size of the state space associated with each arm. If we naively apply the existing regret guarantees for MDP problems, the regret will be exponential. The authors also provided a lower bound as well as empirical results.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "As mentioned above, I would like to see a better discussion on the motivation of studying this problem.\n\nRelatively minor changes:\n\nThe authors use “markovian” and \"bayesian\" in many places. It should be “Markovian” and \"Bayesian\"\n\nLast paragraph on page 3: what is the difference between the symbol \\mathcal{X} and \\mathcal{E}?\n\nFirst paragraph of Section 4: “The structure of the three MB-* algorithm is similar” -> “The structures of the three MD-* algorithms are similar”\n\nI think it would be helpful to discuss the motivation of choosing geometrically distributed episode length.", "broader_impact_concerns": "I don't see any concerns on the ethical implications of this work. So I don't think a Broader Impact Statement is needed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the paper presents results that are supported by theoretical as well as empirical results. While two of the reviewers also consider the findings sufficiently interesting, one is a bit skeptical about the relevance of the setting. In that respect I agree with the authors in that the amount of literature on Markovian bandits shows that there is sufficient interest in research in that field and also provides several applications, that need not be further discussed in detail by the paper at hand.

However, the reviews also point out that the paper does not adequately discuss the limitations of the work and is rather sloppy when comparing different settings. Thus, while I reommend to accept the paper, in the final version the following minor revisions shall be made:
- Abstract as well as introduction shall point out the specific setting that is considered (i.e., rested bandits, episodic setting with a particular choice of the episodes).
- The term 'regret' (without any further specification) should not be used unless it is completely clear from context which precise notion of regret (e.g., Bayesian or expected) is considered. This holds in particular for the abstract where currently regret bounds with a different meaning are mentioned in the same sentence in quite a misleading manner.
- The limitations of the considered specific setting (as particularly pointed out by reviewer UZTB) should be adequately discussed. 

Beside these important revisions I also noted that you cite the conference version (Auer et al 2008) instead of the extended journal version (Jaksch et al, JMLR 2010) of the UCRL2 paper.
Decision: Accept (poster)