Journal of Machine Learning Research volume (year) pages

Submitted submitted; Published published

Variance-Aware Regret Bounds for Undiscounted
Reinforcement Learning in MDPs
Mohammad Sadegh Talebi∗

mstms@kth.se

KTH Royal Institute of Technology, Stockholm, Sweden

Odalric-Ambrym Maillard†

odalric.maillard@inria.fr

arXiv:1803.01626v1 [stat.ML] 5 Mar 2018

INRIA Lille – Nord Europe, Villeneuve d’Ascq, France

Editor: Mehryar Mohri and Karthik Sridharan

Abstract
The problem of reinforcement learning in an unknown and discrete Markov Decision Process
(MDP) under the average-reward criterion is considered, when the learner interacts with
the system in a single stream of observations, starting from an initial state without any
reset. We revisit the minimax lower bound for that problem by making appear the local
variance of the bias function in place of the diameter of the MDP. Furthermore, we provide
a novel analysis
the KL-Ucrl
q of
 algorithm establishing a high-probability regret bound
P
e
scaling as O
S s,a V?s,a T for this algorithm for ergodic MDPs, where S denotes the
?
number of states and where Vs,a
is the variance of the bias function with respect to the
next-state distribution following action a in state√s. The resulting bound improves upon
e
the best previously known regret bound O(DS
AT ) for that algorithm, where A and
D respectively denote the maximum number of actions (per state) and the diameter of
MDP. We finally compare the leading terms of the two bounds in some benchmark MDPs
indicating that the derived bound can provide an order of magnitude improvement in some
cases. Our analysis leverages novel variations of the transportation lemma combined with
Kullback-Leibler concentration inequalities, that we believe to be of independent interest.
Keywords: Undiscounted Reinforcement Learning, Markov Decision Processes, Concentration Inequalities, Regret Minimization, Bellman Optimality

1. Introduction
In this paper, we consider Reinforcement Learning (RL) in an unknown and discrete Markov
Decision Process (MDP) under the average-reward criterion, when the learner interacts with
the system in a single stream of observations, starting from an initial state without any reset.
More formally, let M = (S, A, ν, P ) denote an MDP where S is a finite set of states and A
is a finite set of actions available at any state, with respective cardinalities S and A. The
reward function and the transition kernel is respectively denoted by ν and P . The game goes
as follows: the learner starts in some state s1 ∈ S at time t = 1. At each time step t ∈ N,
the learner chooses one action a ∈ A in her current state s ∈ S based on her past decisions
and observations. When executing action a in state s, the learner receives a random reward
r drawn independently from distribution ν(s, a) with support [0, 1] and mean µ(s, a). The
state then transits to a next state s0 ∈ S sampled with probability p(s0 |s, a), and a new
∗. The authors contributed equally.
†. The authors contributed equally.
©year M. Sadegh Talebi and Odalric-Ambrym Maillard.
License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided
at http://jmlr.org/papers/vvolume/meila00a.html.

Talebi and Maillard

decision step begins. As the transition probabilities and reward functions are unknown,
the learner has to learn them by trying different actions and recording the realized rewards
and state transitions. We refer to standard textbooks (Sutton and Barto, 1998; Puterman,
2014) for background material on RL and MDPs.
The performance of the learner can be quantified through the notion of regret, which
compares the reward collected by the learner (or the algorithm) to that obtained by an
oracle always following an optimal policy, where a policy is a mapping from states to
actions. More formally, let π : S → P(A) denote a possibly stochastic policy. We further
introduce
p(s0 |s, π(s)) = EZ∼π(s) [p(s0 |s, Z)], and Pπ f to denote the function
P the notation
0
s 7→ s0 ∈S p(s |s, π(s))f (s0 ). Likewise, let µπ (s) = EZ∼π(s) [µ(s, Z)] denote the mean reward
after choosing action π(s) in step s.
Definition 1 (Expected cumulative reward) The expected cumulative reward of policy
π when run for T steps from initial state s1 is defined as
X

T
T
X
Rπ,T (s1 ) = E
r(st , at ) = µπ (s1 ) + (Pπ µπ )(s1 ) + · · · =
(Pπt−1 µπ )(s1 ) .
t=1

t=1

where at ∼ π(st ), st+1 ∼ p(·|st , at ), and finally r(s, a) ∼ ν(s, a).
Definition 2 (Average
gain and bias) Let us introduce the average transition operator
P
P π = limT →∞ T1 Tt=1 Pπt−1 . The average gain gπ and bias function bπ are defined by
∞ 

X
1
gπ (s1 ) = lim Rπ,T (s1 ) = (P π µπ )(s1 ) ,
bπ (s) =
(Pπt−1 − P π )µπ (s) .
T →∞ T
t=1
The previous definition requires some mild assumption on the MDP for the limits to makes
sense. It is shown (see, e.g., (Puterman, 2014)) that the average gain achieved by executing
a stationary policy π in a communicating MDP M is well-defined and further does not
depend on the initial state, i.e., gπ (s1 ) = gπ . For this reason, we restrict our attention to
such MDPs in the rest of this paper. Furthermore, let ? denote an optimal policy, that is1
g? = maxπ gπ .
Definition 3 (Regret) We define the regret of any learning algorithm A after T steps as
T
T
X
X
?
?
r(st , ?(st )) −
r(st , at ) where at = A(st , ({st0 , at0 , rt0 })t0 <t ) ,
RegretA,T :=
t=1

t=1

and s?t+1 ∼ p(·|s?t , ?(s?t )) with s?1 = s1 is a sequence generated by the optimal strategy.
By an application of Azuma-Hoeffding’s inequality for bounded random martingales, it is
immediate to show that with probability higher than 1 − δ,
T 
 p
X
RegretA,T 6
P?t−1 µ? − Pat−1
µ
+ 2T log(2/δ)
a
t
t
=

t=1
T
X

(P?t−1


− P ? )µ? + T g? −

t=1

T
X

Pat−1
µat
t


+

p
2T log(2/δ) .

t=1

Thus, following (Jaksch et al., 2010), it makes sense to focus on the control of the middle
term in brackets only. This leads us to consider the following notion of regret, which we
may call effective regret:
?

RA,T := T g −

T
X

r(st , at ) .

t=1

1. The maximum is reached since there are only finitely many deterministic policies.

2

Variance-Aware Regret Bounds in MDPs

To date, several algorithms have been proposed in order to minimize the regret based on
the optimism in the face of uncertainty principle, coming from the literature on stochastic
multi-armed bandits (see (Robbins, 1952)). Algorithms designed based on this principle
typically maintain confidence bounds on the unknown reward and transition distributions,
and choose an optimistic model that leads to the highest average long-term reward. One of
the first algorithms based on this principle for MDPs is due to (Burnetas and Katehakis,
1997), which is shown to be asymptotically optimal. Their proposed algorithm uses the
Kullback-Leibler (KL) divergence to define confidence bounds for transition probabilities.
Subsequent studies by (Tewari and Bartlett, 2008), (Auer and Ortner, 2007), (Jaksch et al.,
2010), and (Bartlett and Tewari, 2009) propose algorithms that maintain confidence bounds
on transition kernel defined by L1 or total variation norm. The use of L1 norm, instead of
KL-divergence, allows one to describe the uncertainty of the transition kernel by a polytope,
which in turn brings computational advantages and ease in the regret analysis. On the
other hand, such polytopic models are typically known to provide poor representations of
underlying uncertainties; we refer to the literature on the robust control of MDPs with
uncertain transition kernels, e.g., (Nilim and El Ghaoui, 2005), and more appropriately
to (Filippi et al., 2010). Indeed, as argued in (Filippi et al., 2010), optimistic models
designed by L1 norm suffer from two shortcomings: (i) the L1 optimistic model could lead
to inconsistent models by assigning a zero mass to an already observed element, and (ii) due
to polytopic shape of L1 -induced confidence bounds, the maximizer of a linear optimization
over L1 ball could significantly vary for a small change in the value function, thus resulting
in sub-optimal exploration (we refer to the discussion and illustrations on pages 120–121 in
(Filippi et al., 2010)).
Both of these shortcomings are avoided by making use of the KL-divergence and properties of the corresponding KL-ball. In (Filippi et al., 2010), the authors introduce the
KL-Ucrl algorithm that modifies the Ucrl2 algorithm of (Jaksch et al., 2010) by replacing
L1 norms with KL divergences in order to define the confidence bound on transition probabilities. Further, they provide an efficient way to carry out linear optimization over the
KL-ball, which is necessary in each iteration of the Extended Value Iteration. Despite these
favorable properties and the strictly superior performance in numerical experiments (even
for very short time horizons), the best known regret bound for KL-Ucrl matches that of
Ucrl2. Hence, from a theoretical perspective, the potential gain of use of KL-divergence to
define confidence bounds for transition function has remained largely unexplored. The goal
of this paper is to investigate this gap.
Mainq
contributions. In this paper we provide a new regret bound for KL-Ucrl scaling
√ 
e S P V? T + D T for ergodic MDPs with S states, A actions, and diameter
as O
s,a s,a
? := V
?
?
D. Here, Vs,a
p(·|s,a) (b ) denotes the variance of the optimal bias function b of the
true (unknown) MDP with respect to next state distribution
√ under state-actionp(s, a). This
? 6 D.
e
bound improves over the best previous bound of O(DS
AT ) for KL-Ucrl as Vs,a
√
p ?
p ?
Interestingly, in several examples Vs,a  D and actually Vs,a is comparable to D.
q P
? could be
Our numerical experiments on typical MDPs further confirm that S s,a Vs,a
√
orders of magnitude smaller than DS A. To prove this result, we provide novel transportation concentration inequalities inspired by the transportation method that relate the
so-called transportation cost under two discrete probability measures to the KL-divergence

3

Talebi and Maillard

between the two measures and the associated variances. To the best of our knowledge, these
inequalities are new and of independent √
interest. To complete our result, we provide a new
? . In view
minimax regret lower bound of order Ω( SAVmax T ), where Vmax := maxs,a Vs,a
of the new minimax
√ lower bound, the reported regret bound for KL-Ucrl can be improved
by only a factor S.
Related work. RL in unknown MDPs under average-reward criterion dates back to the
seminal papers by (Graves and Lai, 1997), and (Burnetas and Katehakis, 1997), followed by
(Tewari and Bartlett, 2008). Among these studies, for the case of ergodic MDPs, (Burnetas
and Katehakis, 1997) derive an asymptotic MDP-dependent lower bound on the regret and
provide an asymptotically optimal algorithm. Algorithms with finite-time regret guarantees
and for wider class of MDPs are presented by (Auer and Ortner, 2007), (Jaksch et al., 2010;
Auer et al., 2009), (Bartlett and Tewari, 2009), (Filippi et al., 2010), and (Maillard et al.,
2014).
√
e
Ucrl2 and KL-Ucrl achieve a O(DS
AT ) regret bound with high probability
in com√
e 0 S AT ) regret
municating MDPs, for any unknown time horizon. Regal obtains a O(D
with high probability in the larger class of weakly communicating MDPs, provided that
we know an upper bound D0 on the span of the bias function. It is however still an open
problem to incorporate this knowledge into an implementable algorithm. The TSDE√algoe 0 S AT )
rithm by Ouyang et al. (Ouyang et al., 2017) achieves a regret growing as O(D
0
for the class of weakly communicating MDPs, where D is a given bound on the span of
the bias function. In a recent study, (Agrawal and Jia, 2017) propose an algorithm based
on posterior sampling for the class of communicating MDPs. Under the assumption of
known reward √
function and known time horizon, their algorithm enjoys a regret bound
e
scaling as O(D SAT ), which constitutes the best known regret upper bound for learning
in communicating MDPs and has a tight dependencies on S and A.
We finally mention that some studies consider regret minimization in MDPs in the
episodic setting, where the length of each episode is fixed and known; see, e.g., (Osband
et al., 2013), (Gheshlaghi Azar et al., 2017), and (Dann et al., 2017). Although RL in
the episodic setting bears some similarities to the average-reward setting, the techniques
developed in these paper strongly rely on the fixed length of the episode, which is assumed
to be small, and do not directly carry over to the case of undiscounted RL considered here.

2. Background Material and The KL-Ucrl Algorithm
In this section, we recall some basic material on undiscounted MDPs and then detail the
KL-Ucrl algorithm.
Lemma 4 (Bias and Gain) The gain and bias function satisfy the following relations
(Bellman equation)
(Fundamental matrix)

bπ + gπ = µπ + Pπ bπ
bπ = [I − Pπ + Pπ ]−1 [I − P π ]µπ .

This result is an easy consequence of the fact that P π (see Definition 2) satisfies P π Pπ =
Pπ P π = P π P π = P π (see (Puterman, 2014) as well as Appendix E for details).
According to the standard terminology, we say a policy is b? -improving if it satisfies
π(s) = argmaxa∈A µ(s, a) + (Pa b? )(s) . Applying the theory of MDPs (see, e.g., (Puterman,
4

Variance-Aware Regret Bounds in MDPs

2014)), it can be shown that any b? -improving policy is optimal and thus that we can choose
? to satisfy2 the following fundamental identity3


X
(Bellman optimality equation) ∀s ∈ S, b? (s) + g? = max µ(s, a) +
p(y|s, a)b? (y) .
a∈A

y∈S

We now recall the definition of diameter and mixing time as we consider only MDPs with
finite diameter or mixing time.
Definition 5 (Diameter (Jaksch et al., 2010)) Let Tπ (s0 |s) denote the first hitting time
of state s0 when following stationary policy π from initial state s. The diameter D of an
MDP M is defined as
D := max0 min E[Tπ (s0 |s)].
s6=s

π

Definition 6 (Mixing time (Auer and Ortner, 2007)) Let Cπ denote the Markov chain
induced by the policy π in an ergodic MDP M and let TCπ represent the hitting time of Cπ .
The mixing time TM of M is defined as
TM := max TCπ .
π

For convenience, we also introduce, for any function f defined on S, its span defined by
S(f ) := maxs∈S f (s) − mins∈S f (s). It actually acts as a semi-norm (see (Puterman, 2014)).
We finally introduce the following quantity that appears in the known problem-dependent
lower-bounds on the regret, and plays the analogue of the mean gap in the bandit literature.
Definition 7 (Sub-optimality gap) The sub-optimality of action a at state s is
ϕ(s, a) = µ(s, ?(s)) − µ(s, a) + (p(·|s, ?(s)) − p(·|s, a))> b? .

(1)

Note importantly that ϕ is defined in terms of the bias b? of the optimal policy ?. Indeed, it
can be shown that minimizing
P the effective regret (in expectation) is essentially equivalent
to minimizing the quantity s,a ϕ(s, a)E[NT (s, a)], where NT (s, a) is the total number of
steps when action a has been played in state s. More precisely, it is not difficult to show
(see Appendix E for completeness) that for any stationary policy π and all t,
X
X

E[Rπ,t ] =
ϕ(s, a)E[Nt (s, a)] + (Pπt−1 − I)b? (s1 ) 6
ϕ(s, a)E[Nt (s, a)] + D .
(2)
s,a

s,a

The KL-Ucrl algorithm. The KL-Ucrl algorithm (Filippi et al., 2010; Filippi, 2010) is a
model-based algorithm inspired by Ucrl2 (Jaksch et al., 2010). To present the algorithm,
we first describe how it defines, at each given time t, the set of plausible MDPs based on
the observation available at that time. To this end, we introduce the following notations.
Under a given algorithm and for a state-action
P pair (s, a), let Nt (s, a) denote the number
+
of visits, up to time t, to (s, a): Nt (s, a) = t−1
t0 =0 I{st0 = s, at0 = a}. Then, let Nt (s, a) =
max{Nt (s, a), 1}. Similarly, Nt (s, a, s0 ) denotes the number of visits to (s, a), up to time
2. The solution to this fixed-point equation is defined only up to an additive constant. Some people tend
to use this equation in order to define b? and g? , but this is a bad habit that we avoid here.
3. Throughout this paper, we may use g ? (resp. b? ) and g? (resp. b? ) interchangeably.

5

Talebi and Maillard

P
0
t, followed by a visit to state s0 : Nt (s, a, s0 ) = t−1
t0 =0 I{st0 = s, at0 = a, st0 +1 = s }. We
introduce the empirical estimates of transition probabilities and rewards:
Pt−1
rt I{st0 = s, at0 = a}
Nt (s, a, s0 )
0
0
µ̂t (s, a) = t =0
,
p̂
(s
|s,
a)
=
.
t
Nt (s, a)+
Nt (s, a)+
KL-Ucrl, as an optimistic model-based approach, considers the set Mt as a collection
of all MDPs M 0 = (S, A, ν 0 , P 0 ), whose transition kernels and reward functions satisfy:
KL(p̂t (·|s, a), p0 (·|s, a)) 6 Cp /Nt (s, a) ,
q
|µ̂t (s, a) − µ0 (s, a)| 6
Cµ /Nt (s, a) ,

(3)
(4)

where µ0 denotes the mean of ν 0 , and where Cp := Cp (T, δ) = S (B + log(G)(1 + 1/G)),
with B = B(T, δ) := log(2eS 2 A log(T )/δ) and G = B + 1/ log(T ), and Cµ := Cµ (T, δ) =
log(4SA log(T )/δ)/1.99. Importantly, as proven in (Filippi et al., 2010, Proposition 1), with
probability at least 1 − 2δ, the true MDP M belongs to the set Mt uniformly over all time
steps t 6 T .
Similarly to Ucrl2, KL-Ucrl proceeds in episodes of varying lengths; see Algorithm 1.
We index an episode by k ∈ N. The starting time of the k-th episode is denoted tk , and by a
slight abuse of notation, let Mk := Mtk , Nk := Ntk , µ̂k = µ̂tk , and p̂k := p̂tk . At t = tk , the
algorithm forms the set of plausible MDPs Mk based on the observations gathered so far.
It then defines an extended MDP Mext,k = (S, A × Mk , µext , Pext ), where for an extended
action aext = (a, M 0 ), it defines µext (s, aext ) = µ0 (s, a) and pext (s0 |s, aext ) = p0 (s0 |s, a).
Then, a √1t -optimal extended policy πext,k is computed in the form πext,k (s) = (M̃k , π̃k (s)),
k
in the sense that it satisfies
1
def
g̃k = gπ̃k (M̃k ) > 0max gπ (M 0 ) − √ ,
M ∈Mk ,π
tk
where gπ (M ) denotes the gain of policy π in MDP M . M̃k and π̃k are respectively called
the optimistic MDP and the optimistic policy. Finally, P
an episode stops at the first step
t = tk+1 when the number of local counts vk,t (s, a) = tt0 =tk I{st0 = s, at0 = a} exceeds
Ntk (s, a) for some (s, a). We denote with some abuse vk = vk,tk+1 −1 .
√
Remark 8 The value 1/ tk is a parameter of Extended Value Iteration and is only here
for computational reasons: with sufficient computational power, it could be replaced with 0.
Algorithm 1 KL-Ucrl (Filippi et al., 2010), with input parameter δ ∈ (0, 1]
Initialize: For all (s, a), set N0 (s, a) = 0 and v0 (s, a) = 0. Set t = 1, k = 1, and observe initial state s1
for episodes k > 1 do
Set tk = t
Set Nk (s, a) = Nk−1 (s, a) + vk−1 (s, a) for all (s, a)
Find a √1t -optimal policy π̃k and an optimistic MDP M̃k ∈ Mk using Extended Value Iteration
k
while vk (st , at ) > Nk (st , at ) do
Play action at = π̃k (st ), and observe the next state st+1 and reward r(st , at )
Update Nk (s, a, x) and vk (s, a) for all actions a and states s, x
end while
end for

6

Variance-Aware Regret Bounds in MDPs

3. Regret Lower Bound
In order to motivate the dependence of the regret on the local variance, we first provide the
following minimax lower bound that makes appear this scaling.
Theorem 9 There exists an MDP M with S states and A actions with S, A > 10, such
that the expected regret under any algorithm A after T > DSA steps for any initial state
satisfies
p
E[RA,T ] > 0.0123 Vmax SAT ,
where
Vmax := max Vp(·|s,a) (b? ) .
s,a

Let us recall
√ that (Jaksch et al., 2010) present a minimax lower bound on the regret
scaling as Ω( DSAT ). Their lower bound follows by considering a family of hard-tolearn MDPs. To prove the above theorem, we also consider the same MDP instances as
in (Jaksch et al., 2010) and leverage their techniques. We however show that choosing a
slightly different choice
√ of transition probabilities for the problem instance leads to a lower
bound scaling as Ω( Vmax SAT ), which does not depend on the diameter (the details are
provided in the appendix).
We also remark that for the considered problem instance, easy calculations
show that for
√
any state-action pair (s, a), the variance of bias function satisfies c1 D 6 Vp(·|s,a) (b? ) 6 c2 D
for some constants c1 and c2 . Hence, the lower bound in Theorem 9 can serve as an
alternative minimax lower bound without any dependence on the diameter.

4. Concentration Inequalities and The Kullback-Leibler Divergence
Before providing the novel regret bound for the KL-Ucrl algorithm, let us discuss some
important tools that we use for the regret analysis. We believe that these results, which
could also be of independent interest beyond RL, shed light on some of the challenges of
the regret analysis.
Let us first recall a powerful result from mathematical statistics (we provide the proof
in Appendix B for completeness) known as the transportation lemma; see, e.g., (Boucheron
et al., 2013, Lemma 4.18):
Lemma 10 (Transportation lemma) For any function f , let us introduce ϕf : λ 7→
log EP [exp(λ(f (X) − EP [f ]))]. Whenever ϕf is defined on some possibly unbounded interval
I containing 0, define its dual ϕ?,f (x) = supλ∈I λx − ϕf (λ). Then it holds
∀Q  P,

EQ [f ] − EP [f ] 6 ϕ−1
+,f (KL(Q, P ))

where ϕ−1
+,f (t) = inf{x > 0 : ϕ?,f (x) > t} ,

∀Q  P,

EQ [f ] − EP [f ] > ϕ−1
−,f (KL(Q, P ))

where ϕ−1
−,f (t) = sup{x 6 0 : ϕ?,f (x) > t} .

This result is especially interesting when Q is the empirical version of P built from n
i.i.d. observations, since in that case it enables to decouple the concentration properties of
the distribution from the specific structure of the considered function. Further, it shows
that controlling the KL divergence between Q and P induces a concentration result valid
for all (nice enough) functions f , which is especially useful when we do not know in advance
the function f we want to handle (such as bias function b? ).
7

Talebi and Maillard

−1
The quantities ϕ−1
look complicated. When f (X) (where X ∼ P ) is Gaus+,f , ϕ−,f may
p
sian, they coincide with t 7→ ± 2VP (f )t. Controlling them in general is challenging.
However for bounded functions, a Bernstein-type relaxation can be derived that uses the
variance VP (f ) and the span S(f ):

Corollary 11 (Bernstein transportation) For any function f such that VP [f ] and S(f )
are finite,
p
2
∀Q  P, EQ [f ] − EP [f ] 6
2VP [f ]KL(Q, P ) + S(f )KL(Q, P ) ,
3
p
2VP [f ]KL(Q, P ) .
∀Q  P, EP [f ] − EQ [f ] 6
We also provide below another variation of this result that is especially useful when the
bounds of Corollary 11 cannot be handled, and that seems to be new (up to our knowledge):
Lemma 12 (Transportation method II) Let P ∈ P(X ) be a probability distribution on
a finite alphabet X . Then, for any real-valued function f defined on X , it holds that
q
q
p
∀P  Q, EQ [f ] − EP [f ] 6
VP,Q (f ) + VQ,P (f )
2KL(P, Q) + S(f )KL(P, Q) ,
X
where
VP,Q (f ) :=
P (x)(f (x) − EP [f ])2 .
x∈X :P (x)>Q(x)

When P is the transition law under a state-action pair (s, a) and Q is its empirical estimates
up to time t, i.e. Q = p̂t (·|s, a) and P = p(·|s, a), the first assertion in Corollary 11 can be
used to decouple EQ [f ] − EP [f ] from specific structure of f . In particular, if f is some bias
e −1 ), the first order terms
function, then f has a bounded span D, and since KL(Q, P ) = O(N
t
q
e S P V? T )
makes appear the variance of f . This would result in a term scaling as O(
s,a s,a
e hides poly-logarithmic terms.
in our regret bound, where O(·)
Now, for the case when Q = p̂t (·|s, a) and P = p̃t (·|s, a) is the optimistic transition
law at time t, the second inequality in Corollary 11 allows us to bound EP [f ] − EQ [f ]
by the variance of f under law p̃(·|s, a), which itself is controlled by the variance of f
under
true law p(·|s, a). Using such an approach would lead to a term scaling as
q the
P
2 1/4 ). We can remove the term scaling as O(T
?
e S
e 1/4 ) in our regret
O(
s,a Vs,a T + DS T
analysis by resorting to Lemma 12 instead, in combination with the following property of
the operator V:
Lemma 13 Consider two distributions P, Q ∈ P(X ) with |X | > 2. Then, for any realvalued function f defined on X , it holds that
(i)
(ii)

VP,Q (f ) 6 VP (f ) ,
q
q
p
VP,Q (f ) 6 2VQ (f ) + 3S(f ) |X |KL(Q, P ) .

5. Variance-Aware Regret Bound for KL-Ucrl
In this section, we present a regret upper bound for KL-Ucrl that leverages the results
presented in the previous section. Let Ψ := S(b? ) denote the span of the bias function, and
8

Variance-Aware Regret Bounds in MDPs

? := V
?
for any (s, a) ∈ S × A define Vs,a
p(·|s,a) (b ) as the variance of the bias function under
law p(·|s, a).
Let ˜
?k denote the optimal policy in the extended MDP Mk , whose gain g̃˜?k satisfies
g̃˜?k = maxM 0 ∈Mk ,π gπ (M 0 ). We consider a variant of KL-Ucrl, which computes, in every
episode k, a policy π̃k satisfying: maxs |b̃k (s) − b̃˜?k (s)| 6 √1t , and g̃k > g̃˜?k − √1t .4
k
k
In the following theorem, we provide a refined regret bound for KL-Ucrl:

Theorem 14 (Variance-aware regret bound for KL-Ucrl) With probability at least 1−
6δ, the regret under KL-Ucrl for any ergodic MDP M and for any initial state satisfies
 q P
p
√
√
? + 35S A + 2D + 1
RKL-Ucrl,T 6 31 S s,a Vs,a
T B(T, δ)


e SA(TM SA + D + S 3/2 ) log(T ) ,
+O
e hides the terms scaling as polylog(log(T )/δ). Hence, with probability at least 1 − δ,
where O
 q P

p
? +D
RKL-Ucrl,T = O
S s,a Vs,a
T log(log(T )/δ) .
+ := {s0 : p(s0 |s, a) > 0} for state-action (s, a) is
Remark 15 If the cardinality of the set Ss,a
known, then one can use the following improved confidence bound for the pair (s, a) (instead
of (3)):

Nt (s, a)KL(p̂t (·|s, a), p0 (·|s, a)) 6 Cps,a ,

(5)

|S + |

where Cps,a = Ss,a Cp (see, e.g., (Filippi, 2010, Proposition 4.1) for the corresponding con+ | for all (s, a) ∈ S × A is known, it is then straightcentration result). As a result, if |Ss,a
forward to show thatq
the corresponding variant of KL-Ucrl, which relies on (5), achives a
√ 
P
+ |V? T + D T .
e
regret growing as O
|Ss,a
s,a
s,a

The regret bound provided in the aforementioned remark is of particular importance in
the case of sparse MDPs, where most states transit to only a few next-states under various
actions. We would like to stress that to get an improvement of a similar flavour for Ucrl2,
+ for all (s, a) ∈ S × A rather
to the best of our knowledge, one has to know the sets Ss,a
than their cardinalities.
Sketch of proof of Theorem 14. The detailed proof of this result is provided in Appendix C. In order to better understand it, we now provide a high level sketch of proof
explaining the main steps of the analysis.
First note that by an application P
of Azuma-Hoeffding
p inequality, the effective regret
T
is upper bounded by RA,T 6 T g? − t=1 µ(st , at ) + T log(1/δ)/2, with probability at
P
least 1 − δ. We proceed by decomposing the term T g? − Tt=1 µ(st , at ) on the episodes
k = 1, . . . , m(T ), where m(T ) is the total number of episodes after T steps. Introducing
4. We study such a variant to facilitate the analysis and presentation of the proof. This variant of KL-Ucrl
may be computationally less efficient than Algorithm 1. We stress however that, in view of the number
of episodes (growing as SA log(T )) as well as Remark 8, with sufficient computational power such an
algorithm could be practical.

9

Talebi and Maillard

vk (s, a) as the number of visits to (s, a) during episode k for any (s, a) and k, with probability
at least 1 − δ we have
m(T )

RA,T 6

X

∆k +

m(T )
X
p
T log(1/δ)/2 =
∆k

k=1

where ∆k =

X

vk (s, a)(g ? − µ(s, a)) .

s,a

k=1

We focus on episodes such that M ∈ Mk , corresponding to valid confidence intervals, up to
losing a probability only 2δ. In order to control ∆k I{M ∈ Mk }, we use the decomposition
X
X
vk (s, a)(g ? − µ(s, a)) =
vk (s, a)(g̃k − µ(s, a) + (g ? − g̃k )) .
s,a

s,a

√
We refrain from using the fact that g ? − g̃k 6 1/ tk and instead use it as a slack later in
the proof. We then introduce the bias function from the identity g̃k − µ̃k = (Pek − I)b̃k , and
thus get


X
∆k =
vk (s, a) (Pek − Pk )b? + (Pk − I)b̃k + (Pek − Pk )(b̃k − b? ) + (g ? − g̃k )
{z
} | {z } |
{z
}
|
s,a

(a)

(b)

(c)

Term (a). The first term is controlled thanks to our variance-aware concentration inequalities:
(Pek − Pk )b? = (Pbk − Pk )b? + (Pek − Pbk )b? , where
q
2
?
∀s, ((Pbk − Pk )b? )(s) 6
2Vs,π̃
KL(p̂k , p) + S(b? )KL(p̂k , p) and
k (s)
3
√
√ q
e
b
∀s, ((Pk − Pk )b? )(s) 6 (1 + 2) 2Vp̂k (b? )KL(p̂k , p̃k ) + S(b? )(1 + 3 2S)KL(p̂k , p̃k ) .
The first inequality is obtained by Corollary 11 whilepthe second one
p by a combination of
Lemma 12 together with Lemma 13. We then relate Vp̂k (b? ) to Vp (b? ) thanks to:
Lemma 16 For any episode k > 1 such that M ∈ Mk , it holds that for any pair (s, a),
q
q
6SS(f )B
Vp̂k (·|s,a) (f ) 6 2Vp(·|s,a) (f ) + p
with probability at least 1 − δ.
Nk (s, a)
It is then not difficult to show
this first term, when summed over all episodes, conq that
p
P
?
e
tributes to the regret as O( S s,a Vs,a
T log(log(T )/δ)), where the log(log(T )) terms
comes from the use of time-uniform concentration inequalities.
Term (b). We then turn to Term (b) and observe that it makes appear a martingale
difference structure. Following the same reasoning as in (Jaksch et al., 2010) or (Filippi
et al., 2010), the right way to control it is however to sum this contribution over all episodes
and make appear a martingale difference sequence of T deterministic terms, bounded by
the deterministic quantity D, since S(b̃k ) 6 D. This comes at the price of losing a constant
error D per episode. Now, since it can be shown that m(T ) 6 SA log2 (8T /SA) as for Ucrl2,
we deduce that with probability higher than 1 − δ,
m(T )

XX

vk (s, a)(Pk − I)b̃k 6 D

p
2T log(1/δ) + 2DSA log2 (8T /SA) .

k=1 s,a

10

Variance-Aware Regret Bounds in MDPs

Term (c). It thus remains to handle Term (c). To this end, we first partition the states
into Ss+ = {x ∈ S : Pek (s, x) > Pk (s, x)} and its complementary set Ss− , and get
X
X
vk (Pek − Pk )(b̃k − b? ) =
vk (s, π̃k (s))
(Pek (s, x) − Pk (s, x))(b̃k (x) − b? (x))
s

+

X

x∈Ss+

X

vk (s, π̃k (s))

s

(Pek (s, x) − Pk (s, x))(b̃k (x) − b? (x)) .

x∈Ss−

We thus need to control the difference of bias from above and from below. To that end, we
note that by property of the bias function, it holds that
b̃k − b? = g̃˜?k − g̃k + (µ̃k − µk ) + (Pek − Pk )b? −ϕk + Pek (b̃k − b? ) .
|
{z
}
(d)

√
Owing to the fact that g̃˜?k − g̃k 6 1/ tk and by the previous
results on concentration
q

?
SV
s,a
e
inequalities, the term (d) can be shown to be scaling as O
. Thus, this means
Nk (s,a)

?
SVs,a
,
ϕ(s,a)2

that provided that for all s, a, Nk (s, a) &
then (d) − ϕ(s, a) 6 0, and thus b̃k − b? 6
0 + Pek (0 + . . .) 6 0. On the other hand, for the control of the last term, we first note that
for an b̃˜?k -improving policy (which is optimal in the extended MDP), then for all J ∈ N it
holds
6 (g̃˜?k − g? ) + P? (b? − b̃˜?k ) 6 J(g̃˜?k − g? ) + P?J (b? − b̃˜?k ) .

b? − b̃˜?k

Thus, we obtain that
vk (Pek − Pk )(b̃k − b? ) + vk (g? − g̃˜?k )1 6

X

vk (s, π̃k (s))

s

+

X

X


(Pk (s, x) − Pek (s, x)) P?J (b? − b̃˜?k ) (x)

x∈Ss−

h
i
X
vk (s, π̃k (s)) 1 − J
(Pk (s, x) − Pek (s, x)) (g? − g̃˜?k ) + ηk ,

s

(6)

x∈Ss−

where ηk is controlled by the error of computing b̃k in episode k (which, for the considered
√
P
(s,a)
In order to handle the
variant of the algorithm, is bounded by 32SB s,a Nvkk(s,a)
+ ).
remaining terms in (6), and choose J, we use the fact that P? is γ-contracting for some
log(D)
γ < 1. Thus, choosing J = log(1/γ)
ensures that contribution of the first term in (6) is
√
P
vk (s,a)
less than 32SB s,a √
. Furthermore, provided that Nk (s, a) & SBJ 2 for all s
+
Nk (s,a)

and a, we observe that the term in brackets is non-negative, and hence the second term in
(6) becomes negative (later on we consider the case where this condition is not satisfied).
√
P
Putting together, we get (c) 6 (2 32SB + 1) s,a √vk (s,a) + .
Nk (s,a)

Finally, it remains to handle the case where some state-action pair is not sufficiently
sampled, that is there exists (s, a) such that Nk (s, a) < `s,a , where

n
e SB max
`s,a = `s,a (T, δ) := O
11

Ψ
log(D) o2 
,
,
ϕ(s, a) log(1/γ)

∀s, a.

Talebi and Maillard

0.4

0.05

0.6

0.35

0.6
s1

0.95
(r = 0.05)

0.05

0.6

0.05

0.05

0.35

0.35

s3

s2

0.6

0.05

0.6
(r = 1)

0.35
sN

sN −1

0.05

0.05

0.05

0.05

0.05

0.95

0.95

0.95

0.95

0.95

Figure 1: The N -state Ergodic RiverSwim MDP
Borrowing some arguments from (Auer and Ortner, 2007), we show that a given state-action
pair (s, a), which is not sufficiently sampled, contributes to the regret (until it becomes
sufficiently sampled) by at most O(TM max(`s,a , log(SA/δ))) with probability at least 1 −
δ
SA . Summing over (s, a) gives the total contribution to regret. At this point, the proof is
essentially done, up to some technicalities and careful handling of second order terms.
Remark 17 Most steps in the proof of Theorem 14 carries over to the case of communicating MDPs without restriction (up to considering the fact that for a communicating MDP,
P? may not induce a contractive mapping. Yet there exists some integer β > 1 such that
e
)) in
P?β induces a contractive mapping; this will only affect the terms scaling as O(log(T
the regret bound). It is however not clear how to appropriately bound the regret when some
state-action pair is not sufficiently sampled.
Illustrative numerical experiments. In order to better highlight the magnitude of the
main terms in Theorem 14 when compared to other existing results, we consider a standard
class of environments for which we compute them explicitly.
For the sake of illustration, we consider the RiverSwim MDP, introduced in (Strehl and
Littman, 2008), as our benchmark environment. In order to satisfy ergodicity, here we
consider a slightly modified version of the original RiverSwim (see Figure 1). Furthermore,
to convey more intuition about the potential gains, we consider varying number of states.
The benefits of KL-Ucrl have already been studied experimentally in (Filippi et al., 2010),
and we compute in Table 1 features √
that we believe
explain the reason behind this. In
√
?
particular, it is apparent that while Ψ SA 6 D SA grows very large as S increases, Vs,a
is very small, on all tested environments,q
and does not change as S increases. Further, even
P
?
on this simple environment, we see that
s,a Vs,a is an order or magnitude smaller than
√
Ψ SA. We believe that these computations highlight the fact that the regret bound of
Theorem 14 captures a massive improvement over the initial analysis of KL-Ucrl in (Filippi
et al., 2010), and over alternative algorithms such as Ucrl2.

6. Conclusion
In this paper, we revisited the analysis of KL-Ucrl as well as the lower bound on the regret in ergodic MDPs, in order to make appear the local variance of the bias function of
the MDP. Our findings show that, owing to properties of the Kullback-Leibler divergence,
12

Variance-Aware Regret Bounds in MDPs

S

Ψ

?
maxs,a Vs,a

√
Ψ SA

6
12
20
40
70
100

6.3
14.9
26.3
54.9
97.7
140.6

0.6322
0.6327
0.6327
0.6327
0.6327
0.6327

21.9
72.9
166.4
490.9
1156.5
1988.3

qP

s,a

?
Vs,a

1.8
2.8
3.7
5.3
7.1
8.5

Table 1: Comparison of span and variance for S-state Ergodic RiverSwim.
√
e
the leadingterm
 ) obtained for the regret of KL-Ucrl and Ucrl2 can be req PO(DS AT
?
e
S s,a Vs,a T , while the lower bound for any algorithm can be shown to be
duced to O
√
? . Computations of these terms in some illusΩ( SAVmax T ), where Vmax := maxs,a Vs,a
trative MDP show that the reported upper bound may improve an order of magnitude over
the existing ones (as observed experimentally in (Filippi, 2010)), thus highlighting the fact
that trading the diameter of the MDP to the local variance of the bias function may result
in huge improvements.
√
We note that this improvement
often
corresponds
to
a
gain
of
a
factor
O(
D). A
√
natural question is whether the S gap between the upper and lower bounds can be filled
in. In the simpler setting of episodic reinforcement learning with known horizon H, several
papers have shown that by taking advantage of this√knowledge, it is possible to design
strategies for which the regret bound does not lose a S factor. However, such strategies
do not apply straightforwardly to undiscounted reinforcement learning. Nonetheless, we
believe that combining techniques of such studies with the tools that we have developed is
a fruitful research direction.

Acknowledgment
M. S. Talebi acknowledges the Ericsson Research Foundation for supporting his visit to INRIA Lille Nord – Europe. This work has been supported by CPER Nord-Pas de Calais/FEDER
DATA Advanced data science and technologies 2015-2020, the French Ministry of Higher
Education and Research, INRIA, and the French Agence Nationale de la Recherche (ANR),
under grant ANR-16- CE40-0002 (project BADASS).

References
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning:
Worst-case regret bounds. In Advances in Neural Information Processing Systems 30
(NIPS), pages 1184–1194, 2017.
Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in Neural Information Processing Systems 19 (NIPS), 19:
49, 2007.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In Advances in Neural Information Processing Systems 22 (NIPS), pages
13

Talebi and Maillard

89–96, 2009.
Peter L Bartlett and Ambuj Tewari. REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), pages 35–42, 2009.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A
nonasymptotic theory of independence. Oxford University Press, 2013.
Apostolos N. Burnetas and Michael N. Katehakis. Optimal adaptive policies for Markov
decision processes. Mathematics of Operations Research, 22(1):222–255, 1997.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform
PAC bounds for episodic reinforcement learning. In Advances in Neural Information
Processing Systems 30 (NIPS), pages 5711–5721, 2017.
Sarah Filippi. Stratégies optimistes en apprentissage par renforcement. PhD thesis, Ecole
nationale supérieure des telecommunications-ENST, 2010.
Sarah Filippi, Olivier Cappé, and Aurélien Garivier. Optimism in reinforcement learning
and Kullback-Leibler divergence. In Proceedings of the 48th Annual Allerton Conference
on Communication, Control, and Computing (Allerton), pages 115–122, 2010.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true
shape of regret in bandit problems. arXiv preprint arXiv:1602.07182, 2016.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for
reinforcement learning. In Proceedings of the 34th International Conference on Machine
Learning (ICML), pages 263–272, 2017.
Todd L. Graves and Tze Leung Lai. Asymptotically efficient adaptive choice of control laws
in controlled markov chains. SIAM Journal on Control and Optimization, 35(3):715–743,
1997.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. The Journal of Machine Learning Research, 11:1563–1600, 2010.
Odalric-Ambrym Maillard, Timothy A. Mann, and Shie Mannor. How hard is my MDP?
“the distribution-norm to the rescue”. In Advances in Neural Information Processing
Systems 27 (NIPS), pages 1835–1843, 2014.
Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with
uncertain transition matrices. Operations Research, 53(5):780–798, 2005.
Ian Osband, Dan Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via
posterior sampling. In Advances in Neural Information Processing Systems 26 (NIPS),
pages 3003–3011, 2013.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown Markov
decision processes: A Thompson sampling approach. In Advances in Neural Information
Processing Systems 30 (NIPS), pages 1333–1342, 2017.
14

Variance-Aware Regret Bounds in MDPs

Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming.
John Wiley & Sons, 2014.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the
American Mathematical Society, 58(5):527–535, 1952.
Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation
for Markov decision processes. Journal of Computer and System Sciences, 74(8):1309–
1331, 2008.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction, volume 1. MIT Press Cambridge, 1998.
Ambuj Tewari and Peter L. Bartlett. Optimistic linear programming gives logarithmic
regret for irreducible MDPs. In Advances in Neural Information Processing Systems 20
(NIPS), pages 1505–1512, 2008.
Flemming Topsøe. Some bounds for the logarithmic function. Inequality theory and applications, 4:137, 2006.

Appendix A. Regret Lower Bound
The proof of Theorem 9 mainly relies on the problem instance for the derivation of the
minimax lower bound in (Jaksch et al., 2010) and related arguments there. For the sake of
completeness, we first recall their problem instance and then compute the variance of the
corresponding bias function.
To get there, we first consider the two-state MDP M 0 shown in Figure 2, where there
are two states {s0 , s1 }, each having A0 = b A−1
2 c actions. We consider deterministic rewards
defined as r(s0 , a) = 0 and r(s1 , a) = 1 for all a ∈ A. The learner knows the rewards but
4
not the transition probabilities. Let δ := D
, where D is the diameter of the MDP for which
we derive the lower bound. Under any action a, p(s0 |s1 , a) = δ. In state s0 , there is a
unique optimal action a? , which will be referred to as the good action. For any a 6= a? , we
have p(s1 |s0 , a) = δ whereas p(s1 |s0 , a? ) = δ + ε for some ε ∈ (0, 2δ ) that will be determined
later. Note that the diameter D0 of M 0 satisfies: D0 = 1δ = D
4.
δ+ε

1−δ−ε

1−δ

1−δ

... ...

s0

... ...

δ

s1

δ

Figure 2: The MDP M 0 for lower bound (Jaksch et al., 2010)
15

Talebi and Maillard

We consider δ ∈ (0, 13 ).5 After straightforward calculations, one finds that the average
reward in M 0 is given by
g? =

δ+ε
1/δ
=
.
1/δ + 1/(δ + ε)
2δ + ε

Furthermore, from Bellman optimality equation we obtain
b? (s0 ) +

δ+ε
= (δ + ε)b? (s1 ) + (1 − δ − ε)b? (s0 ) ,
2δ + ε

thus giving Ψ := S(b? ) = b? (s1 ) − b? (s0 ) =
follows that:

1
2δ+ε .

Consider a 6= a? and let p = p(·|s0 , a). It

Ep [b? ] = δb? (s1 ) + (1 − δ)b? (s0 ) = b? (s0 ) + δΨ ,
Vp (b? ) = δ(b? (s1 ) − Ep [b? ])2 + (1 − δ)(b? (s0 ) − Ep [b? ])2 = δ(1 − δ)Ψ2 .
Similarly, we obtain
Vp(·|s0 ,a? ) (b? ) = (δ + ε)(1 − δ − ε)Ψ2 ,
Vp(·|s1 ,a) (b? ) = δ(1 − δ)Ψ2 ,

∀a.

Hence, using the facts that x 7→ x(1 − x) is increasing for x ∈ [0, 12 ] and ε + δ 6 12 , we obtain
Vmax := max Vp(·|s,a) (b? ) = (δ + ε)(1 − δ − ε)Ψ2 .
s,a

A.0.1 The composite MDP
We now build a composite MDP M as considered in (Jaksch et al., 2010), as a concatenation
of k := b S2 c copies of M 0 in the form of an A0 -ary tree, where only one copy contains the
good action a? (see Figure 3). To this end, we first add A0 + 1 additional actions so that M
has at most A actions per state. For any state s0 , one of these new actions connects s0 to the
root, and the rest connect s0 to the leaves. Whereas for any state s1 , all new actions make
a transition to the same state s1 . By construction, the diameter of the composite MDP M
S
A0 −1
A0 −1
does not exceed 2( D
4 +logA0 k), so that MDP M has 2b 2 c 6 S states, b 2 c+b 2 c+1 6 A
actions, and a diameter less than D.
A.1 Proof of Theorem 9
To derive the claimed result, we derive a lower bound on the regret for the composite MDP
presented above. Our analysis is largely built on the techniques used in the proof of (Jaksch
et al., 2010, Theorem 5). We also closely follow the notations used in (Jaksch et al., 2010).
Let us assume, as in the proof of (Jaksch et al., 2010, Theorem 5), that all states s0
are identified so that M is equivalent to an MDP M 0 with kA0 actions (note that following
the same argument as in (Jaksch et al., 2010), despite the same maximal average reward,
learning in M 0 is easier than in M , and so any regret lower bound for M 0 implies a lower
5. The case of δ > 1/3 can be handled similarly to the analysis of (Jaksch et al., 2010).

16

Variance-Aware Regret Bounds in MDPs

Figure 3: The composite MDP M (Jaksch et al., 2010)
bound in M , too). Note that by construction of M , it holds that Vmax in M equals Vmax
in M 0 . Denote by (s?0 , a? ) the good copy, i.e., the one containing the good action a? . We
assume that a? is chosen uniformly at random among all actions {1, . . . , k} × {1, . . . , A0 }.
Let E? [·] and Eunif [·] respectively denote the expectation with respect to the random choice
of (s?0 , a? ) and the expectation when there is no good action. Furthermore, let Ea [·] denote
the expectation conditioned on a = a? , and introduce N1 , N0 , and N0? as the respective
number of visits to s1 , s0 , and (s0 , a? ).
The proof proceeds in the same steps as in the proof of (Jaksch et al., 2010, Theorem 5)
up to Equation (36) there, where it is shown that assuming that the initial state is s0 ,
Ea [N1 ] 6 Ea [N0 − N0? ] + (δ + ε)D0 Ea [N0? ] 6 T − Eunif [N1 ] + εD0 Ea [N0? ] ,
Eunif [N1 ] >

T − D0
,
2

so that the accumulated reward RA,T by the algorithm A in M 0 up to time step T satisfies
Ea [RA,T ] 6 Ea [N1 ] 6

T + D0
+ εD0 Ea [N0? ] .
2

The following lemma, which is a straightforward modification to (Jaksch et al., 2010,
Lemma 13), enables us to control Ea [N0? ]:
Lemma 18 Let f : {s0 , s1 }T +1 7→ [0, B] be any function defined on any trajectory sT +1 =
(st )16t6T +1 in M 0 . Then, for any δ ∈ [0, 31 ], ε ∈ (0, 1 − 2δ), and a ∈ {1, . . . , kA0 },
s
log(2)Eunif [N0? ]
Ea [f (s)] 6 Eunif [f (s)] + εB
.
2(δ + ε)(1 − δ − ε)
17

Talebi and Maillard

Noting that N0? is a function of sT +1 satisfying N0? ∈ [0, T ], by Lemma 18 we deduce
s
log(2)Eunif [N0? ]
?
?
Ea [N0 ] 6 Eunif [N0 ] + εT
2(δ + ε)(1 − δ − ε)
s
log(2)Eunif [N0? ]
,
= Eunif [N0? ] + εΨT
2Vmax
p
√
where we used Vmax = Ψ (δ + ε)(1 − ε − δ). As shown in the proof of (Jaksch et al.,
p
P 0
PkA0 p
?
0
2010, Theorem 5), kA
Eunif [N0? ] 6 kA0 (T + D0 )/2,
a=1 Eunif [N0 ] 6 (T + D )/2 and
a=1
1 PkA0
so that we finally get, using the relation E? [RA,T ] = kA
0
a=1 Ea [RA,T ],
δ+ε
T − E? [RA,T ]
2δ + ε
δ+ε
T
εD0 T
εD02
T− −
−
>
2δ + ε
2
2kA0
2kA0
s
s
ε2 ΨD0 T log(2)kA0 T
ε2 ΨD0 T log(2)kA0 D0 D0
−
−
−
kA0
4Vmax
kA0
4Vmax
2
0
2
0
√
εD
0.42ε ΨD T √
εT
D0
0
0) −
√
(
−
(T
+
D
)
−
.
>
T
+
D
4δ + 2ε 2kA0
2
kA0 Vmax

E? [RA,T,M 0 ] =

Noting that the assumption T > DSA implies T > 16D0 kA0 , we deduce that
√
εT
εD0 T 
1  0.42ε2 ΨD0 T T 
1  D0
√
√
E? [RA,T,M 0 ] >
−
1
+
−
1
+
.
−
4δ + 2ε
2kA0
16kA0
2
kA0 Vmax
4 kA0
The first term in the right-hand side of the above satisfies
εT
εT Ψ
5εVmax T
=
>
,
4δ + 2ε
2
6
since
Ψ
2δ + ε
δ
5
=
>1+
> ,
Vmax
(δ + ε)(1 − δ − ε)
δ+ε
3
where we used ε 6

δ
2

in the last step. Hence, we get

√
5
εD0 T 
1  0.42ε2 ΨD0 T T 
1  D0
√
√
E? [RA,T,M 0 ] > εVmax T −
1
+
.
1
+
−
−
6
2kA0
16kA0
2
kA0 Vmax
4 kA0
q
0
In particular, setting ε = c VkA
for some c (which will be determined later) yields
max T



p
5 p 0
cD0
1 
0
E? [RA,T,M 0 ] > c kA Vmax T − kA Vmax T
1+
6
2kA0 Vmax
16kA0


p
0.42c2 D0 Ψ 
1 
D0
√
− kA0 Vmax T
1
+
−
.
2
kA0 Vmax
2
4 kA0
18

Variance-Aware Regret Bounds in MDPs

To simplify the above bound, note that
 2δ + ε 2
(2δ + ε)2
D0
6
6 12.5 ,
62
Vmax
δ(δ + ε)(1 − δ − ε)
δ
where we used 1 − ε − δ >

1
2

(7)

since ε 6 2δ . Moreover,

D0 Ψ
D0 Ψ
=
2
Vmax
Ψ4 (δ + ε)2 (1 − δ − ε)2
 2δ + ε 3
(2δ + ε)3
6
4
6 62.5 .
=
δ(δ + ε)2 (1 − δ − ε)2
δ
Putting these together with the fact that
r
r
p
√ r
12.5/16 Vmax T
D0
T
Vmax T
D0
6
6 0.45
,
6
0
0
2
2
16kA
2
kA
kA0
which follows from (7), we deduce that
 5c 12.5c
p
12.5c
26.25c2
6.6c2
0.45 
E? [RA,T,M 0 ] > kA0 Vmax T
−
−
−
−
−
,
6
2kA0
32(kA0 )2
kA0
kA0
(kA0 )3/2
Taking c = 0.132 and using the facts k = b S2 c > 5 and A0 = b A−1
2 c > 4 yield the announced
result. This completes the proof provided that we show that this choice of c satisfies ε 6 2δ .
0
To this end, observe that by the assumption T > DSA > 16kA
δ , it follows that
s
r
r
kA0
0.132
δ
0.132
δ(2δ + ε)2
ε = 0.132
6
6
6 0.047(2δ + ε) ,
Vmax T
4
Vmax
4
(δ + ε)(1 − δ − ε)
so that ε 6 0.1δ. This concludes the proof.



A.2 Proof of Lemma 18
The lemma follows by a slight modification of the proof of (Jaksch et al., 2010, Lemma 13).
We recall that according to Equations (49)-(51) in (Jaksch et al., 2010),
Bp
Ea [f (s)] − Eunif [f (s)] 6
2 log(2)KL(Punif , Pa ) ,
(8)
2
where
KL(Punif , Pa ) =
=

T
X
t=1
T
X
t=1

KL(Punif (st+1 |st ), Pa (st+1 |st ))

 δ 
 1 − δ 
Punif (st = s0 , at = a) δ log
+ (1 − δ) log
.
δ+ε
1−δ−ε
(a−b)2
b(1−b)

valid for all a, b ∈ (0, 1) (instead of (Jaksch et al.,
P
2010, Lemma 20)) and noting that Eunif [N0? ] = Tt=1 Punif (st = s0 , at = a), we obtain

Now using the inequality kl(a, b) 6

KL(Punif , Pa ) = kl(δ, δ + ε)Eunif [N0? ] 6
Plugging this into (8) completes the proof.

ε2
Eunif [N0? ] .
(1 − δ)(1 − δ − ε)


19

Talebi and Maillard

Appendix B. Concentration Inequalities
B.1 Proof of Lemma 10
Let us recall the fundamental equality
∀λ ∈ R,

 


log EP [exp(λ(X − EP [X])] = sup λ EQ [X] − EP [X] − KL(Q, P ) .
QP

In particular, we obtain on the one hand that (see also (Boucheron et al., 2013, Lemma 2.4))
∀Q  P,

EQ [f ] − EP [f ] 6

min

λ∈R+

ϕf (λ) + KL(Q, P )
.
λ

Since ϕf (0) = 0, then the right-hand side of the above is non-negative. Let us call it u. Now,
we note that for any t such that u > t > 0, by construction of u, it holds that KL(Q, P ) >
ϕ?,f (t). Thus, {x > 0 : ϕf,? (x) > KL(Q, P )} = (u, ∞) and hence, u = ϕ−1
+,f (KL(Q, P )).
On the other hand, it holds
∀Q  P,

EQ [f ] − EP [f ] >

max

λ∈R−

ϕf (λ) + KL(Q, P )
.
λ

Since ϕ(0) = 0, then the right-hand side quantity is non-positive. Let us call it v. Now, we
note that for any t such that v 6 t 6 0, by construction of v, it holds that KL(Q, P ) > ϕ?,f (t).

Thus, {x 6 0 : ϕ?,f (x) > KL(Q, P )} = (−∞, v) and hence, v = ϕ−1
−,f (KL(Q, P )).
B.2 Proof of Corollary 11
By a standard Bernstein argument (see for instance (Boucheron et al., 2013, Section 2.8)),
it holds
∀λ ∈ [0, 3/S(f )),

ϕf (λ) 6

VP [f ]
λ2
,
2 1 − S(f )λ
3

∀x > 0,

ϕ?,f (x) >

x2
2(VP [f ] +

S(f )
3 x)

.

Then, a direct computation (solving for x in ϕ?,f (x) = t) shows that
r
 S(f ) 2 p
2
S(f )
−1
ϕ+,f (t) 6
t + 2tVP [f ] +
t 6 2tVP [f ] + tS(f ) ,
3
3
3
r


p
2
S(f )
S(f )
ϕ−1
t − 2tVP [f ] +
t > − 2tVP [f ] ,
−,f (t) >
3
3
√
√
√
where we used that a + b 6 a + b for a, b > 0. Combining these bounds, we get
p
2
2VP [f ]KL(Q, P ) + S(f )KL(Q, P ) ,
3
p
EP [f ] − EQ [f ] 6
2VP [f ]KL(Q, P ) .

EQ [f ] − EP [f ] 6


20

Variance-Aware Regret Bounds in MDPs

B.3 Proof of Lemma 12
If EQ [f ] 6 EP [f ], then the result holds trivially. We thus assume that EQ [f ] > EP [f ]. It is
straightforward to verify that
X

EQ [f ] − EP [f ] =

(f (x) − EQ [f ])(Q(x) − P (x)) +

+

(f (x) − EP [f ])(Q(x) − P (x))

x:Q(x)<P (x)

x:Q(x)>P (x)

X

X

(EP [f ] − EQ [f ])(Q(x) − P (x)) .

(9)

x:P (x)>Q(x)

The first term in the right-hand side of (9) is upper bounded as
X

p
Q(x) − P (x)
Q(x)(f (x) − EQ [f ]) p
Q(x)
x:Q(x)>P (x)
v
u
X
(Q(x) − P (x))2
u
Q(x)(f (x) − EQ [f ])2 t
Q(x)

(f (x) − EQ [f ])(Q(x) − P (x)) =

x:Q(x)>P (x)
(a)

s

X

6

x:Q(x)>P (x)

X

x:Q(x)>P (x)

(b) q
p
6 VQ,P (f ) 2KL(P, Q) ,

(10)

where (a) follows from Cauchy-Schwarz inequality and (b) follows from Lemma 22.
Similarly, the second term in (9) satisfies
X

p
Q(x) − P (x)
P (x)(f (x) − EP [f ]) p
P (x)
x:Q(x)<P (x)
q
p
(11)
6 VP,Q (f ) 2KL(P, Q) .
X

(f (x) − EP [f ])(Q(x) − P (x)) =

x:Q(x)<P (x)

Finally, we bound the last term in (9):
(EP [f ] − EQ [f ])

X

(a)

(Q(x) − P (x)) =

x:P (x)>Q(x)

1
(EQ [f ] − EP [f ])kP − Qk1
2

(b)
1
6 S(f )kP − Qk21 6 S(f )KL(P, Q) ,
2

(12)

where
(a) follows from thePfact that for any pair of distributions U, V ∈ P(X ), it holds that
P
x∈X |U (x) − V (x)| = 2
x:U (x)>V (x) (U (x) − V (x)), and where (b) follows from Pinsker’s
inequality. The proof is concluded by combining (10), (11), and (12).

B.4 Proof of Lemma 13
Statement (i) is a direct consequence of the definition of VP,Q . We next prove statement
(ii). Observe that Lemma 22 implies that for all x ∈ X
p
|P (x) − Q(x)| 6 2 max(P (x), Q(x))KL(Q, P ) .
21

Talebi and Maillard

Hence,
X

VP,Q (f ) =

P (x)(f (x) − EP [f ])2

x:P (x)>Q(x)

X

6

Q(x)(f (x) − EP [f ])2 +

X

p
2KL(Q, P )

x:P (x)>Q(x)

p
P (x)(f (x) − EP [f ])2 .

x:P (x)>Q(x)

(13)
The first term in the right-hand side of (13) is bounded as follows:
X
X
Q(x)(f (x) − EQ [f ])2 + 2(EQ [f ] − EP [f ])2
Q(x)(f (x) − EP [f ])2 6 2
x:P (x)>Q(x)

x:P (x)>Q(x)

6 2VQ (f ) + 2(EQ [f ] − EP [f ])2 .
Note that
(EQ [f ] − EP [f ])2 6 S(f )2 kP − Qk21 6 2S(f )2 KL(Q, P ) ,
which further gives
X

Q(x)(f (x) − EP [f ])2 6 2VQ (f ) + 4S(f )2 KL(Q, P ) .

x:P (x)>Q(x)

Now we consider the second term in (13). First observe that
s
s
X
X
X
p
2
2
(f (x) − EP [f ])2
P (x)(f (x) − EP [f ]) 6
P (x)(f (x) − EP [f ])
x:P (x)>Q(x)

x:P (x)>Q(x)

x

q
p
6 VP,Q (f )S(f ) |X | ,
thanks to Cauchy-Schwarz inequality. Hence, the second term in (13) is upper bounded by
q
S(f ) 2|X |VP,Q (f )KL(Q, P ) .
Combining the previous bounds together, we get
q
VP,Q (f ) 6 2VQ (f ) + 4S(f )2 KL(Q, P ) + S(f ) 2|X |VP,Q (f )KL(Q, P ) ,
which leads to
2
q
p
VP,Q (f ) − S(f ) |X |KL(Q, P )/2 6 2VQ (f ) + S(f )2 (|X |/2 + 4)KL(Q, P ) ,
√
√
√
so that using the inequality a + b 6 a + b, we finally obtain
q
q
p
VQ,P (f ) 6 2VQ (f ) + S(f )2 (|X |/2 + 4)KL(Q, P ) + S(f ) |X |KL(Q, P )/2
q
p
p
6 2VQ (f ) + S(f )( 2|X | + 2) KL(Q, P ) .
The proof is completed by observing that

p
p
2|X | + 2 6 3 |X | for |X | > 2.
22



Variance-Aware Regret Bounds in MDPs

B.5 Proof of Lemma 16
Let δ ∈ (0, 1) and (s, a) ∈ S × A. Consider an episode k > 1 such that M ∈ Mk , and define
p̂k = p̂k (·|s, a), p = p(·|s, a), and Nk = Nk (s, a). Observe that by a Bernstein-like inequality
(Dann et al., 2017, Lemma F.2), we have: for all s0 ∈ S, with probability at least 1 − δ,
s
2p(s0 )Cb 2Cb
p̂k (s0 ) − p(s0 ) 6
+
,
Nk
Nk
with Cb = Cb (t, δ) := log(3 log(max(e, t))/δ). It then follows that with probability at least
1 − δ,
X
Vp̂k (f ) =
p̂k (s0 )(f (s0 ) − Ep̂k [f ])2
s0

6

X

0

0

r

2

p(s )(f (s ) − Ep̂k [f ]) +

s0

6

2Cb X
2Cb X p 0
p(s )(f (s0 ) − Ep̂k [f ])2 +
(f (s0 ) − Ep̂k [f ])2
Nk 0
Nk 0
s

X

r

p(s0 )(f (s0 ) − Ep̂k [f ])2 +

s0

|

{z

}

Z1

s

2Cb X p 0
2Cb SS(f )2
p(s )(f (s0 ) − Ep̂k [f ])2 +
.
Nk 0
Nk
|s
{z
}

(14)

Z2

Next we bound Z1 and Z2 . Observe that
X
Z1 6 2
p(s0 )(f (s0 ) − Ep [f ])2 + 2(Ep [f ] − Ep̂k [f ])2
s0

6 2Vp (f ) + 4S(f )2 KL(p̂k , p) ,
where the last inequality follows from
(Ep [f ] − Ep̂k [f ])2 6 S(f )2 kp − p̂k k21 6 2S(f )2 KL(p̂k , p) .
For Z2 we have
Z2 6 2

Xp
Xp
p(s0 )(f (s0 ) − Ep [f ])2 + 2(Ep [f ] − Ep̂k [f ])2
p(s0 ) .
s0

s0

Now, using Cauchy-Schwarz inequality
sX
X
Xp
0
2
0
p(s )(f (s ) − Ep [f ]) 6
p(s0 )(f (s0 ) − Ep [f ])2
(f (s0 ) − Ep [f ])2
s0

s0

6

q

s0

SVp (f )S(f ) ,

so that using (15), we deduce that
q
Xp
p(s0 )
Z2 6 2S(f ) SVp (f ) + 4S(f )2 KL(p̂k , p)
s0

q
√
6 2S(f ) SVp (f ) + 4S(f )2 KL(p̂k , p) S ,
23

(15)

Talebi and Maillard

where the last inequality follows from Jensen’s inequality:
s
s
X
Xp
X p(s0 ) √
1
0
p(s0 ) =
p(s )
6
= S.
p(s0 )
p(s0 )
0
0
0
s

s

s

Putting together, we deduce that with probability at least 1 − δ,
r
q


2SCb 
2SCb 
Vp̂k (f ) 6 2Vp (f ) + 2S(f )
Vp (f ) + 2S(f )KL(p̂k , p) + S(f )2 4KL(p̂k , p) +
.
Nk
Nk
Noting that M ∈ Mk , we obtain
s
√
8SVp (f )Cb
2SCb Cp (4Cp + 2SCb )S(f )2
+
Vp̂k (f ) 6 2Vp (f ) + S(f )
+ 4S(f )2
3/2
Nk
Nk
Nk
s
p
8SVp (f )Cb SS(f )2
+
(16B 2SCb + 16B + 2Cb )
6 2Vp (f ) + S(f )
Nk
Nk
s
8SVp (f )B 36S 3/2 B 3/2 S(f )2
6 2Vp (f ) + S(f )
+
,
Nk
Nk
with probability at least 1 − δ, where we used Cp = 4SB, Cb 6 B, and S > 2. The proof is
concluded by observing that
s
r
q
q
SB
S 3/2
+ 6S(f )B
Vp̂k (f ) 6 2Vp (f ) + S(f )
Nk
Nk
q
6SS(f )B
,
6 2Vp (f ) + √
Nk
with probability at least 1 − δ.



Appendix C. Regret Upper Bound for KL-Ucrl
In this section, we provide the proof of the main result (Theorem 14). We will try to closely
follow the notations used in the proof of (Jaksch et al., 2010, Theorem 2).
We first recall the following result indicating that the true model belongs to the set of
plausible MDPs with high probability. Recall that for δ ∈ (0, 1] and t ∈ N,
Cµ := Cµ (T, δ) = log(4SA log(T )/δ)/1.99 ,
Cp := Cp (T, δ) = S (B + log(G)(1 + 1/G)) ,
where
B : = B(T, δ) = log(2eS 2 A log(T )/δ) ,
G : = G(T, δ) = B + 1/ log(T ) .
Moreover, observe that Cp 6 4SB.
24

(16)

Variance-Aware Regret Bounds in MDPs

Lemma 19 ((Filippi et al., 2010, Proposition 1)) For all T > 1 and δ > 0, and for
any pair (s, a), it holds that
q


δ
P ∀t 6 T, |µ̂t (s, a) − µ(s, a)| 6 Cµ /Nt (s, a) > 1 −
,
SA


δ
P ∀t 6 T, Nt (s, a)KL(p̂t (s, a), p(·|s, a)) 6 Cp > 1 −
.
SA
In particular, P(∀t 6 T, M ∈ Mt ) > 1 − 2δ.
Next we prove the theorem.
Proof (of Theorem 14). Let T > 1 and δ ∈ (0, 1). Fix algorithm A = KL-Ucrl. Denote by
m(T ) the number of episodes started by KL-Ucrl up to time step T (hence, 1 6 k 6 m(T )).
By applying Azuma-Hoeffding inequality, as in the proof of (Jaksch et al., 2010, Theorem 2), we deduce that
?

RA,T = T g −

T
X

r(st , at ) 6

X

?

NT (s, a)(g − µ(s, a)) +

q

1
2T

log(1/δ) ,

s,a

t=1

with probability at least 1 − δ. The regret up to time T can be decomposed as the sum of
the regret incurred in various episodes. Let ∆k denote the regret in episode k:
X
∆k :=
vk (s, a)(g ? − µ(s, a)) .
s,a

Therefore, Lemma 19 implies that with probability at least 1 − 3δ,
m(T )

RA,T 6

X

∆k I{M ∈ Mk } +

q

1
2T

log(1/δ) .

k=1

Next we derive an upper bound on the first term in the right-hand side of the above
inequality. Consider an episode k > 1 such that M ∈ Mk . The state-action pair (s, a)
is considered as sufficiently sampled in episode k if its number of observations satisfies
Nk (s, a) > `s,a , with
n 128SB max(Ψ2 , 1)
 log(D) 2 o
`s,a = `s,a (T, δ) := max
,
32SB
,
ϕ(s, a)2
log(1/γ)

∀s, a ,

where B is given in (16), and where γ denotes the contraction factor of the mapping induced
by the transition probability matrix P? of the optimal policy (γ can be determined as a
function of elements of P? ).
Now consider the case where all state-action pairs are sufficiently sampled in episode k
(we analyse the case where some pairs are under-sampled (i.e., not sufficiently sampled) at
the end of the proof). We have
s
Cµ
|µ̃k (s, a) − µ(s, a)| 6 |µ̃k (s, a) − µ̂k (s, a)| + |µ̂k (s, a) − µ(s, a)| 6 2
.
Nk (s, a)+
25

Talebi and Maillard

Hence,
∆k =

X

vk (s, a)(g ? − µ̃k (s, a)) +

s,a

6

X

X

vk (s, a)(µ̃k (s, a) − µ(s, a))

s,a

vk (s, a)(g ? − µ̃k (s, a)) + 2

s,a

p X vk (s, a)
p
Cµ
.
+
N
(s,
a)
k
s,a

Let µ̃k and Pek respectively denote the reward vector and transition probability matrix
induced by the policy π̃k on M̃k , i.e., µ̃k := (µ̃k (s, π̃k (s)))s , Pek := p̃k (s0 |s, π̃k (s)) s,s0 . By
Bellman optimality equation, g̃k − µ̃k (s, a) = (Pek − I)b̃k . Hence, defining vk = (vk (s, π̃k (s))s
yields
∆k 6 vk (Pek − I)b̃k + (g ? − g̃k )vk 1 + 2

p X vk (s, a)
p
Cµ
.
Nk (s, a)+
s,a

Now we use the following decomposition:
vk (Pek − I)b̃k = vk (Pek − Pk )b? + vk (Pek − Pk )(b̃k − b? ) + vk (Pk − I)b̃k .
|
{z
} |
{z
} |
{z
}
F1 (k)

Let c = 1 +

√

F2 (k)

F3 (k)

2. The following two lemmas provide upper bounds for F1 (k) and F2 (k):

Lemma 20 For all k ∈ N such that M ∈ Mk , with probability at least 1 − δ, it holds that
s
X
√ √
F1 (k) 6 (4 + 6 2) SB
vk (s, a)
s,a

?
X vk (s, a)
Vs,a
3/2 3/2
+
63ΨS
B
.
Nk (s, a)+
Nk (s, a)+
s,a

Lemma 21 Let k ∈ N be the index of an episode such that M ∈ Mk . Assuming that
Nk (s, a) > `s,a for all s, a, it holds that
√
 X vk (s, a)
p
F2 (k) + (g ? − g̃k )vk 1 6 2 32SB + 1
.
Nk (s, a)+
s,a
Pm(T )
Analysis of Term F3 . Now we bound the term k=1 F3 (k). To this end, similarly to the
proof of (Jaksch et al., 2010, Theorem 2) and (Filippi et al., 2010, Theorem 1), we define the
martingale difference sequence (Zt )t>1 , where Zt = (p(·|st , at ) − est+1 )b̃k(t) I{M ∈ Mk(t) } for
t ∈ {tk , tk+1 −1}, where k(t) denotes the episode containing t. Note that for all t, |Zt | 6 2D.
Now applying Azuma-Hoeffding inequality, we deduce that with probability at least 1 − δ
m(T )

X
k=1

F3 (k) 6

T
X

Zt + 2m(T )D

t=1

6D

p
2T log(1/δ) + 2DSA log2
26

8T
SA



.

Variance-Aware Regret Bounds in MDPs

The regret due to under-sampled state-action pairs. To analyze the under-sampled
regime, where some state-action pair is not sufficiently sampled, we borrow some techniques
from (Auer and Ortner, 2007). For any state-action pair (s, a), let Ls,a denote the set of
indexes of episodes in which (s, a) is chosen and yet (s, a) is under-sampled; namely k ∈ Ls,a
if π̃k (s) = a and Nk (s, a) 6 `s,a . Furthermore, let τk (s, a) denote the length of such an
episode.
Consider an episode k ∈ Ls,a . By Markov’s inequality, with probability at least 21 , it
takes at most 2TM to reach state s from any state s0 in k, where TM is the mixing time of
M . Let us divide episode k into b τk2T(s,a)
c sub-episodes, each with length greater than 2TM .
M
It then follows that in each sub-episode, (s, a) is visited with probability at least 21 .
Using Hoeffding’s inequality, if we consider n such sub-episodes, with probability at least
δ
1 − SA
,
p
N (s, a) > n/2 − n log(SA/δ).
√
Now we find n that implies N (s, a) < `s,a . Noting that x 7→ x2 − αx is increasing for
x > α, we have that for n > 10 max(`s,a , log(SA/δ)),
q
p
n/2 − n log(SA/δ) > 5 max(`s,a , log(SA/δ)) − 10 max(`s,a , log(SA/δ)) log(SA/δ)
> max(`s,a , log(SA/δ)) .
δ
Hence, with probability at least 1 − SA
, it holds that
X j τk (s, a) k
6 10 max(`s,a , log(SA/δ)) .
2TM
k∈Ls,a

Hence, the regret due to under-sampled state-action pairs can be upper bounded by
X X
X
X
τk (s, a) 6 20TM
max(`s,a , log(SA/δ)) + 2TM
|Ls,a |
s,a k∈Ls,a

s,a

6 20TM

X

s,a

max(`s,a , log(SA/δ)) + 2TM S 2 A2 log2

8T
SA



,

s,a

with probability at least 1 − δ. Here we used that |Ls,a | 6 m(T ).
Now applying Lemmas 20 and 21 together with the above bounds, and using the fact
Cµ 6 B/1.99, we deduce that with probability at least 1 − 3δ
m(T )

X
k=1

X vk (s, a) q
√ √
?
p
∆k I{M ∈ Mk } 6 (4 + 6 2) SB
Vs,a
+
N
(s,
a)
k
s,a
X vk (s, a)
√
√
p
+ (2 32SB + 3 B + 1)
Nk (s, a)+
s,a
X vk (s, a)
+ 63ΨS 3/2 B 3/2
Nk (s, a)+
s,a
p

8T
+ D 2T log(1/δ) + 2DSA log2 SA
X
+ 20TM
max(`s,a , log(SA/δ)) + 2TM S 2 A2 log2
s,a

27

8T
SA



.

Talebi and Maillard

To simplify the above bound, we will use Lemmas 23, 24, and 25 together with Jensen’s
inequality:
m(T )

XX
k=1 s,a
m(T )

XX
k=1 s,a

Xp
√
v (s, a)
p k
6c
NT (s, a) 6 c SAT ,
Nk (s, a)+
s,a
q P
Xq
v (s, a) q ?
?
? N (s, a) 6 c T
p k
Vs,a 6 c
Vs,a
T
s,a Vs,a ,
Nk (s, a)+
s,a

m(T )

X X vk (s, a)
X
log(NT (s, a)) + SA 6 2SA log
6
2
Nk (s, a)+
s,a
s,a

T
SA



+ SA .

k=1

Putting everything together, we deduce that with probability at least 1 − 6δ,
m(T )

RA,T 6

X

∆k I{M ∈ Mk } +

q

1
2T

log(1/δ)

k=1

s X
p
√
√
? T B + 35S AT B + ( 2D + 1) T log(1/δ)
6 31 S
Vs,a
s,a



T
8T
+ 126S 5/2 AB 5/2 log SA
+ 2DSA log2 SA
X
max(`s,a , log(SA/δ)) + 2TM S 2 A2 log2
+ 20TM

8T
SA



+ 63S 5/2 A .

s,a

Hence,
RA,T 6 31

s X
p
√
√
? T B + 35S AT B + ( 2D + 1) T log(1/δ)
S
Vs,a
s,a




e SA(TM SA + D + S 3/2 ) log(T ) .
+O
Noting that B = O(log(log(T )/δ)) gives the desired scaling and completes the proof.
Next we prove Lemmas 20 and 21.
C.1 Proof of Lemma 20
We have
F1 (k) = vk (Pbk − Pk )b? + vk (Pek − Pbk )b?
{z
} |
{z
}
|
G1

G2

Next we provide upper bounds for G1 and G2 .
Term G1 .

We have
X
X

G1 =
vk (s, πk (s))
b? (s0 ) p̂k (s0 |s, πk (s)) − p(s0 |s, πk (s))
s0

s

6

X
s,a

vk (s, a)

X


b (s0 ) p̂k (s0 |s, a) − p(s0 |s, a) .
?

s0

28



Variance-Aware Regret Bounds in MDPs

Fix s ∈ S and a ∈ A. Define the short-hands p = p(·|s, a), p̂k = p̂k (·|s, a), and
Nk+ = Nk (s, a)+ . Applying Corollary 11 (the first statement) and using the fact that
M ∈ Mk give:
X

b? (s0 )(p̂k (s0 ) − p(s0 )) 6

q

2
? KL(p̂ , p) + ΨKL(p̂ , p)
2Vs,a
k
k
3

q

? B/N + +
8SVs,a
k

s0

6

8ΨSB
.
3Nk+

Therefore,
√
G1 6

8SB

X
s,a

Term G2 .

q
X
8
? /N (s, a)+ + ΨSB
vk (s, a) Vs,a
vk (s, a)/Nk (s, a)+ .
k
3
s,a

We have
G2 6

X

vk (s, a)


b? (s0 ) p̃k (s0 |s, a) − p̂k (s0 |s, a) .

s0

s,a

Nk+

X

Fix s ∈ S and a ∈ A. Define the short-hands p̂k = p̂k (·|s, a), p̃k = p̃k (·|s, a), and
= Nk (s, a)+ . An application of Lemma 12 and Lemma 13 gives

X

b? (s0 )(p̃k (s0 ) − p̂k (s0 )) 6

s0

q
p
q
Vp̃k ,p̂k (b? ) + Vp̂k ,p̃k (b? )
2KL(p̂k , p̃k ) + ΨKL(p̂k , p̃k )

q
√
6 c 2Vp̂k (b? )KL(p̂k , p̃k ) + Ψ(1 + 3 2S)KL(p̂k , p̃k ) ,

√
where c = 1 + 2. Note that when M ∈ Mk , an application of Lemma 16 implies that,
with probability at least 1 − δ,
X
s0

q
√
√
√
ΨS 3/2 B 3/2
? B/N + +
b (s )(p̃k (s ) − p̂k (s )) 6 4c SVs,a
(12c
2
+
12
2
+
4/
S)
k
Nk+
q
61ΨS 3/2 B 3/2
? B/N + +
,
6 4c SVs,a
k
Nk+
?

0

0

0

where we used that S > 2. Multiplying by vk (s, a) and summing over s, a yields
q
X
X
√
? /N (s, a)+ + 61ΨS 3/2 B 3/2
G2 6 4c SB
vk (s, a) Vs,a
vk (s, a)/Nk (s, a)+ .
k
s,a

s,a

The lemma follows by combing bounds on G1 and G2 .

C.2 Proof of Lemma 21
Let k > 1 be the index of an episode such that M ∈ Mk . Let ˜? := ˜?k denote the optimal
policy in Mk . The proof proceeds in three steps.
29

Talebi and Maillard

Step 1.

We remark that by definition of the bias functions, it holds that
b̃k − b? = (g ? − g̃k )1 + µ̃k + Pek b? − µ? − P? b? + Pek (b̃k − b? )
6 (g̃˜? − g̃k )1 + µ̃k − µk + (Pek − Pk )b? + Pek (b̃k − b? ) − ϕk ,

where we define ϕk (s) := ϕ(s, π̃k (s)) for all s. Defining
q
p
ξk (s) = 2 Cµ /Nk (s, π̃k (s))+ ,
ζk (s) = Ψ 32SB/Nk (s, π̃k (s))+ ,
we obtain the following bound:
1
b̃k − b? 6 √ 1 + ξk + ζk − ϕk + Pek (b̃k − b? ) .
tk
It is straightforward to check that the assumption Nk (s, π̃k (s)) > `s,π̃k (s) for all s implies
b̃k − b? 6 Pek (b̃k − b? ) .

(17)

Note also that ϕ(s, π̃k (s)) > 0 since ? is b? -improving.
On the other hand, it holds that
b? − b̃˜? = (g̃˜? − g ? )1 + µ? + P? b? − µ̃˜? − Pe˜? b̃˜?
6 (g̃˜? − g ? )1 + µ? + P? b? − µ? − P? b̃˜?
= (g̃˜? − g ? )1 + P? (b? − b̃˜? ) .
Noting P? 1 = 1, and since all entries of P? are non-negative, we thus get for all J ∈ N,
b? − b̃˜? 6 J(g̃˜? − g ? )1 + P?J (b? − b̃˜? ) .
Step 2. Let us now introduce Ss+ = {x ∈ S : Pek (s, x) > Pk (s, x)} as well as its complementary set Ss− = S \ Ss+ . Using (17), b̃k − b? 6 0 so that
X
X
vk (Pek − Pk )(b̃k − b? ) =
vk (s, π̃k (s))
(Pek (s, x) − Pk (s, x))(b̃k (x) − b? (x))
s

6

X

x∈S

X

(Pk (s, x) − Pek (s, x))(b? (x) − b̃k (x)) .
|
{z
}
−

vk (s, π̃k (s))

s

x∈Ss

>0

We thus obtain
vk (Pek − Pk )(b̃k − b? ) 6

X

vk (s, π̃k (s))

s

+

X

6

X

+

X

vk (s, π̃k (s))

s

(Pk (s, x) − Pek (s, x))(b? (x) − b̃˜? (x))

x∈Ss−

X

(Pk (s, x) − Pek (s, x))(b̃˜? (x) − b̃k (x))

x∈Ss−

vk (s, π̃k (s))

s

X

(Pk (s, x) − Pek (s, x))[P?J (b? − b̃˜? )](x)

x∈Ss−

vk (s, π̃k (s))

s

−J

X

X

(Pk (s, x) − Pek (s, x))(b̃˜? (x) − b̃k (x))

x∈Ss−

X
s

vk (s, π̃k (s))

X

(Pk (s, x) − Pek (s, x))(g ? − g̃˜? ) .

x∈Ss−

30

(18)

Variance-Aware Regret Bounds in MDPs

We thus get


X
?
?
vk (s, π̃k (s)) (Pek − Pk )(b̃k − b )(s) + g − g̃˜?
s

6

X

vk (s, π̃k (s))

s

X

(Pk (s, x) − Pek (s, x))[P?J (b? − b̃˜? )](x) + ηk

x∈Ss−



X
X
e
vk (s, π̃k (s)) 1 − J
(Pk (s, x) − Pk (s, x)) (g ? − g̃˜? ) ,
+
s

(19)

x∈Ss−

P
P
where ηk := s vk (s, π̃k (s)) x∈Ss− (Pk (s, x) − Pek (s, x))(b̃˜? (x) − b̃k (x)) is controlled by the
error of computing b̃k in episode k. In particular, for the considered variant of the algorithm,
X
1
vk (s, π̃k (s))kp(·|s, π̃k (s)) − p̃k (·|s, π̃k (s))k1 √
ηk 6
tk
s
X
√
vk (s, π̃k (s))
6 32SB
,
Nk (s, π̃k (s))+
s
where we used tk > Nk (s, π̃k (s)) for all s.
Step 3. It remains to choose J. To this end, we remark that the mapping induced by P?
is a contractive mapping, namely there exists some γ < 1 such that for any function f ,
S(P? f ) 6 γS(f ) .
log(D)
Let us choose J > log(1/γ)
, so that with a simple upper bound, it comes
X
X
vk (s, π̃k (s))
(Pk (s, x) − Pek (s, x))[P?J (b? − b̃˜? )](x)
s

x∈Ss−

6

X

6

X

vk (s, π̃k (s))kp(·|s, π̃k (s)) − p̃k (·|s, π̃k (s))k1

s

S(P?J (b? − b̃?˜? ))
2

vk (s, π̃k (s))kp(·|s, π̃k (s)) − p̃k (·|s, π̃k (s))k1 De− log(D)

s

s
6

X
s

vk (s, π̃k (s))

32SB
.
Nk (s, π̃k (s))+

log(D)
In the sequel, we take J = log(1/γ)
. This enables us to control the first two terms in (19)
and it remains to control the term


X
X
e
vk (s, π̃k (s)) 1 − J
(Pk (s, x) − Pk (s, x)) (g ? − g̃˜? ) .
s

x∈Ss−

In particular we would like to ensure that the term in brackets is non-negative, since in
that case, it is multiplied by a term that is negative. To this end, we note that the term in
brackets is lower bounded by
s
log(D)
32SB
1 − Jkp(·|s, π̃k (s)) − p̃k (·|s, π̃k (s))k1 > 1 −
,
log(1/γ) Nk (s, π̃k (s))+
31

Talebi and Maillard

and is thus guaranteed to be non-negative since
Nk (s, π̃k (s)) > `s,π̃k (s) > 32SB

 log(D) 2
.
log(1/γ)

Putting together, we finally have shown that
1
vk (Pek − Pk )(b̃k − b? ) + vk (g ? − g̃k )1 6 vk (Pek − Pk )(b̃k − b? ) + vk (g ? − g̃˜? )1 + √ vk 1
tk
√
 X vk (s, π̃k (s))
p
6 2 32SB + 1
Nk (s, π̃k (s))+
s
√
 X vk (s, a)
p
6 2 32SB + 1
,
Nk (s, a)+
s,a
which completes the proof.



Appendix D. Technical Lemmas
In this section we provide supporting lemmas for the regret analysis. The following lemma
provides a local version of Pinsker’s inequality for two probability distributions, which can be
seen as the extension of (Garivier et al., 2016, Lemma 2) for the case of discrete probability
measures.
Lemma 22 Let P and Q be two probability distributions on a finite alphabet X . Then,
X
1
(P (x) − Q(x))2
KL(P, Q) >
.
2
max(P (x), Q(x))
x:P (x)6=Q(x)

Proof. The first and second derivatives of KL satisfy:
∂
P (x)
KL(P, Q) = 1 + log
, ∀x ∈ X ,
∂P (x)
Q(x)
∂2
I{x = y}
KL(P, Q) =
, ∀x, y ∈ X .
∂P (x)∂P (y)
P (x)
By Taylor’s Theorem, there exists a probability vector Ξ, where Ξ = tP + (1 − t)Q for
some t ∈ (0, 1), so that
X
∂
KL(P, Q) = KL(Q, Q) +
(P (x) − Q(x))
KL(Q, Q)
∂P
x
1X
∂2
+
(P (x) − Q(x))(P (y) − Q(y))
KL(Ξ, Q)
2 x,y
∂P (x)∂P (y)
X
X (P (x) − Q(x))2
(P (x) − Q(x)) +
2Ξ(x)
x
x
X
(P (x) − Q(x))2
>
,
2 max(P (x), Q(x))

=

x:P (x)6=Q(x)

thus concluding the proof.


32

Variance-Aware Regret Bounds in MDPs

Lemma 23 ((Jakschet P
al., 2010, Lemma 19)) Consider the sequence (zk )16k6n with
0 6 zk 6 Zk−1 := max 1, k−1
i=1 zi for k > 1 and Z0 > 1. Then,
n
X

p
√
z
p k
6 ( 2 + 1) Zn .
Zk−1
k=1

 P
Lemma 24 Consider a sequence (zk )16k6n with 0 6 zk 6 Zk−1 := max 1, k−1
i=1 zi
k > 1 and Z0 = z1 . Then,

for

n
X
zk
6 2 log(Zn ) + 1 .
Zk−1
k=1

Proof. We prove the lemma by induction over n. For n = 1, we have z1 /Z0 = 1. Since
Z1 = max{1, z1 }, it holds that z1 /Z0 6 2 log(Z1 ) + 1.
Pn−1
Now consider n > 1. By the induction hypothesis, it holds that
k=1 zk /Zk−1 6
2 log(Zn−1 ) + 1. Now it follows from the facts zn = Zn − Zn−1 and Zn−1 6 Zn 6 2Zn−1 for
n > 2, that
n
X
zk
zn
6 2 log(Zn−1 ) +
+1
Zk−1
Zn−1
k=1

Zn − Zn−1
+1
Zn


1
= 2 log(Zn−1 ) + 2 1 −
+ 1 6 2 log(Zn ) + 1 ,
Zn /Zn−1
6 2 log(Zn−1 ) + 2

where the last inequality follows from log(x) > 1 −
2006)). This concludes the proof.

1
x

valid for all x > 1 (see, e.g., (Topsøe,


Lemma 25 Let αi , . . . , αd be non-negative numbers and T > 1, and denote by V the optimal
value of the following problem:
max
x

s.t.

d
X
√
i=1
d
X

αi xi

xi = T .

i=1

q P
Then, V = T di=1 αi .
Proof. Introduce the Lagrangian
L(x, λ) =

d
X
√

d


X
αi xi + λ T −
xi .

i=1

i=1

33

Talebi and Maillard

Writing KKT conditions, we observe that the optimal point x?i , i = 1, . . . , d satisfies
α
pi ? − λ = 0, ∀i,
2 xi

and

d
X

x?i − T = 0 .

i=1

Hence,
obtain x?i = αi /(4λ2 ). Plugging this into the equality constraint, it follows that
q weP
Pd
d
1
?
λ = 4T
j=1 αj , thus giving xi = αi T /
j=1 αj . Therefore,
d
d
X
X
p
αi
?
V =
αi xi =
Pd
i=1

i=1

j=1 αj

q P
q P
T dj=1 αj = T dj=1 αj ,

which completes the proof.



Appendix E. Background Material on Undiscounted MDPs
In this section, we provide the proof of a number of standard results for the sake of selfcontainedness, and as we believe it helps get intuition on learning in MDPs.
E.1 Proof of Lemma 4
We provide below a short proof of this standard result for the sake of self-containedness.
The fundamental matrix. We first prove the relation involving the fundamental matrix.
We note that by direct application of the relation P π Pπ = Pπ P π = P π P π = P π , it comes
(I − Pπ + P π )bπ =

∞
X
(I − Pπ )(Pπt−1 − P π )µπ + P π (Pπt−1 − P π ) µπ
|
{z
}
t=1

0

∞
∞
X
X

Pπt−1 − Pπt µπ .
=
(I − Pπ )Pπt−1 µπ − (I − Pπ )P π µπ =
|
{z
}
t=1

0

t=1

Thus, it remains to show that the latter sum equals I − P π . When Pπ is aperiodic, then
the limit limt Pπt exists and is equal to P π . Thus, we easily get
∞
X

Pπt−1 − Pπt = lim (I − PπT ) = I − lim PπT = I − P π .
T →∞

t=1

T →∞

The general case is more intricate, and we refer to (Puterman, 2014).
Bellman equation.

Now in order to obtain the Bellman equation, we simply note that
Pπ bπ =

∞
∞
X
X
(Pπt − P π )µπ =
(Pπt−1 − P π )µπ
t=1

t=2

= bπ − (I − P π )µπ = bπ − µπ + gπ .
34

Variance-Aware Regret Bounds in MDPs

E.2 Value Iteration and Stopping Criterion
Definition 26 (Value iteration) The value iteration procedure defines a sequence of functions (un )n∈N and policies (πn )n∈N according to the following equations
(
un+1 (s) = max
 a∈A µ(s, a) + (Pa un )(s) , where
 u0 = 0
∀n ∈ N
πn+1 (s) = U Argmaxa∈A µ(s, a) + (Pa un )(s) ,
where U(B) denotes the uniform distribution over a set B.
The following result is useful in order to better understand the effect of the classical
stopping criterion used for the value iteration procedure.
Lemma 27 (Value and gain) Let us assume that n is such that S(un+1 − un ) 6 ε. Then
it holds that
g? − gπn+1 6 ε,

|un+1 − un − g? | 6 ε,

and

|un+1 − un − gπn +1 | 6 ε .

Proof. We first show that the average gain satisfies Pπ gπ = gπ and
∀n ∈ N,

P πn+1 [un+1 − un ] 6 gπn+1 6 g? 6 P ? [un+1 − un ] .

Indeed, we note that since P ? P? = P ? , then for any function f , g? = P ? [µ? + P? f − f ].
Applying to the function un , it comes
g? = P ? [µ? + P? un − un ]
6 P ? [µπn+1 + Pπn+1 un − un ]
= P ? (un+1 − un ) ,
where in the second line, we used the maximal property of πn+1 . On the other hand, we
use the equality
gπn+1 = P πn+1 [µπn+1 + Pπn+1 un − un ] = P πn+1 (un+1 − un ) ,
together with the fact that by optimality of ?, g? > gπn+1 .
Thus, all in all it holds on the one hand
g? − gπn+1

6 P ? [un+1 − un ] − P πn+1 [un+1 − un ]
6 max(un+1 − un )(s) − min[un+1 − un ] = S(un+1 − un ) .
s∈S

s∈S

On the other hand, using similar steps,
0 6 P ? [un+1 − un ] − g? 6 max[un+1 − un ] − g?
s∈S

6 max[un+1 − un ] − P πn+1 [un+1 − un ] 6 S(un+1 − un ) .
s∈S

Thus, for all s ∈ S, (un+1 − un )(s) − g? 6 ε. Likewise, we get the reverse inequality
0 6 g? − mins∈S (un+1 − un )(s) 6 S(un+1 − un ) 6 ε. The last bound is immediate from the
relation gπn+1 = P πn+1 (un+1 − un ).

35

Talebi and Maillard

E.3 Pseudo-Regret
The following result relates the effective regret to the pseudo-regret
Lemma 28 (Effective regret to pseudo-regret reduction) Let π be any stationary policy. Then it comes for all T ,
X

E[Rπ,T (s1 )] = [PπT −1 − I]b? (s1 ) +
E[NT (s, a)]ϕ(s, a)
s,a

6 D+

X

E[NT (s, a)]ϕ(s, a) .

s,a

Proof. Since g? is a constant function, it first comes
E[Rπ,T ] =

T 
X

T
 X


g? − Pπt−1 µπ =
Pπt−1 g? − µπ .

t=1

t=1

Then, we note that by construction, it holds that g? − µ? = (P? − I)b? . Introducing the
sub-optimality gap ϕπ (s) := ϕ(s, π(s)) = µ? (s) + (P? b? )(s) − µπ (s) − (Pπ b? )(s), it then
comes
g? − µπ = ϕπ + g? − µ? − P? b? + Pπ̃ b? = (Pπ − I)b? + ϕπ .
Thus far, we have we obtained that
E[Rπ,T ] =

T
X

Pπt−1 ϕπ +

t=1

T
X

Pπt−1 (Pπ − I)b? =

t=1

T
X

Pπt−1 ϕπ + (PπT −1 − I)b? .

t=1

In order to conclude, we note that
T
T
X
X
(
Pπt−1
ϕ
)(s
)
=
Est−1 [ϕπk (st−1 )]
πk
1
k
t=1

t=1

=

X
s,a

ϕ(s, a)

T
X

Est−1 [I{st−1 = s, πk (s) = a}] =

X

ϕ(s, a)E[NT (s, a)] .

s,a

t=1

For the inequality, we use the simple bound [PπT −1 −I]b? 6 kPπT −1 −Ik1 21 S(b? ) 6 D . Putting
these together concludes the proof.


36

