Sleeping Reinforcement Learning
Authors: Simone Drago
Marco Mussi
Alberto Maria Metelli
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Sleeping
Regret Bounds
Lower Bounds
Primary area: reinforcement_learning->online

Abstract: In the standard Reinforcement Learning (RL) paradigm, the action space is assumed to be fixed and immutable throughout the learning process. However, in many real-world scenarios, not all actions are available at every decision stage. The available action set may depend on the current environment state, domain-specific constraints, or other (potentially stochastic) factors outside the agent's control. To address these realistic scenarios, we introduce a novel paradigm called *Sleeping Reinforcement Learning*, where the available action set varies during the interaction with the environment. We start with the simpler scenario in which the available action sets are revealed at the beginning of each episode. We show that a modification of UCBVI achieves regret of order $\widetilde{\mathcal{O}}(H\sqrt{SAT})$, where $H$ is the horizon, $S$ and $A$ are the cardinalities of the state and action spaces, respectively, and $T$ is the learning horizon. Next, we address the more challenging and realistic scenario in which the available actions are disclosed only at each decision stage. By leveraging a novel construction, we establish a minimax lower bound of order $\Omega(\sqrt{T 2^{A/2}})$ when the availability of actions is governed by a Markovian process, establishing a statistical barrier of the problem. Focusing on the statistically tractable case where action availability depends only on the current state and stage, we propose a new optimistic algorithm that achieves regret guarantees of order $\widetilde{\mathcal{O}}(H\sqrt{SAT})$, showing that the problem shares the same complexity of standard RL.

Sleeping Reinforcement Learning
Simone Drago" Marco Mussi"
Alberto Maria Metelli
Abstract
ing sequential decision-making problems mainly in sim- ulated environments. Nowadays, witness an increas- ing demand to transition its capabilities from simulation to real-world applications. However, to move RL to practical domains, we still experience notable challenges that need to be addressed from both the algorithmic and theoretical perspectives. One of these challenges concerns actions' availability. Indeed, in the standard RL framework, the set of actions that can be played in a given state is assumed to be known and immutable throughout the interaction. However, in several real-worke sequential decision decision-making problems, it may not be possible to play some of the actions under some circumstances.
In the standard Reinforcement Learning (RL) paradigm, the action space is assumed to be fixed and immutable throughout the learning process. However, in many real-world scenarios, not all actions are available at every decision stage. The available action set may depend the current environment state, domain-specinn other (potentially stochastic) factors outside the agent's control. To address these realistic scenar- ios, we introduce a novel paradigm called Sleep- ing Reinforcement Learning. where the available action set varies during the interaction with the environment. We start with the simpler scenario in which the available action sets are revealed at the beginning of each episode. We show that a modification of UCBVI achieves regret of order Õ(H V SAT), where is the horizon, S and are the cardinalities of the state and action spaces, respectively, and T is the learning horizon. Next, we address the more challenging and realistic sce- nario in which the available actions are disclosed only at each decision stage. By leveraging novel construction, we establish a minimax lower bound of order 22 22VT22//2) when the availability of ac- tions is governed by Markovian process, estab- lishing a statistical barrier of the problem. Focus- ing the statistically tractable case where action availability depends only on the current state and stage, we propose a new optimistic algorithm that achieves regret guarantees of order Õ(H ((HVVAT)) AT)) showing that the problem shares the same com- plexity of standard RI..
constraints, or
Motivation. Consider the scenario depicted in Figure 1a, in which we want to control physical system (e.g., robot) characterized by given action space A made of all the actions the agent can perform. At every stage h, the RL agent observes the state of the environment s/1 and decides the action On E A to play. Then, such an action is usually validated by a low-level controller (LLC), which checks whether the action is feasible or not (depending, for in- stance, on some physical constraints safety reasons). On the one hand, if feasible, the action is executed as is. On the other hand, if the action is not feasible, the low-level controller overrides it with another action, ăj e A. such as one suggested by baseline policy or the "closest" feasible action (according to some domain -specifc metric). From the agent's perspective, the LLC can be considered as a part of the environment. However, when the agent unaware that certain actions are infeasible (and may only realize it after the LLC intervenes), the performance of the learned policy can be significantly harmed (see Example 1). If the agent is instead aware of the available actions, we ideally want it to select an action among those deemed feasible by the LLC. This scenario can be addressed by adopting a solu- tion in which a low-level filter makes the RL agent aware of which actions An S A are available before actually making decision (Figure lb).
1. Introduction
In recent years, Reinforcement Learning (RL, Sutton & Barto, 2018) has demonstrated remarkable success in solv-
This problem of learning in scenarios with varying action availability is widely studied and discussed for Multi-Armed Bandits (MABs, Lattimore & Szepesvári, 2020) under the name of "Sleeping" MABs. This research line comprises stochastic and adversarial choices for both rewards and action availability (Kleinberg et al., 2008; Kanade al.,
'qqual contribution 'Politecnico di Milano, Milan, Italy, Correspondence to: Simone Drago cemmone.drago it>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Sleeping Reinforcement Learning
Equivalent System
diately before the agent selects an action. We address the general scenario in which the action availabilities governed by Markovian process and illustrate how the problem can be framed as solving an augmented MDP in which the available action set is incorporated the state. Based on this transformation, we define the value function, optimality, and regret. Then, through a novel construc- tion (Figure 3), we demonstrate a statistical barrier of this setting, showing that exponential dependence on the number of actions A is unavoidable in the regret, proving lower bound of order S HV S S/T24/2) (Theorem 4.2). In Section 5, we turn to the tractable case of independent per-stage disclosure, where the action availabilities are sampled independently every stage. We propose a novel optimistic algorithm, Sleeping UCBVI (S-UCBVI), that extends the classical UCBVI with the estimate of the action availability probabilities and appropriately defined new bonuses. We show that S-UCBVI enjoys a regret bound of order Ö(H SAT) for sufficiently large 'I' (The- orem 5.2), matching the lower bound, up to logarithmic factors.
Physical System
Sh+1
BA
Fh
Low-level Controller
RI. Agent
8h.
(a) Classic Reinforcement Learning.
Physicul System
Sh+l1
E (s.))
Th
Sleeping RL Agent
Low-level Filter
(n(s)) E
(b) Sleeping Reinforvement Learning.
Figure I. Example of possible interaction protocol for Classic and Sleeping Reinforcement Learning.
2009; Saha et al., 2020; Nguyen & Mehta, 2024) and sev- eral notions of regret (Gaillard et al., 2023). In RL, instead, this problem remains unaddressed despite its practical rele- vance. This work aims to fill such a gap in the literature.
Related works are discussed in Appendix B. Omitted proofs are provided in Appendices C and D. A numerical validation of the work is provided in Appendix E.
Original Contributions. In this paper, we propose the novel paradigm of Sleeping Reinforcement Learning (SleRL) and study it from a theoretical perspective. The contributions of this work summarized as follows:
2. The Sleeping MDPs Setting
In this section, we first introduce the notation and the stan- dard episodic finite-horizon MDP setting, and then we present the novel Sleeping MDPs (SleMDPs) framework.
In Section 2, we formally introduce the framework of the episodic finite-horizon Sleeping Markov Decision Pro- cesses (SleMDPs) setting, generalization of MDPs in which the available action set changes throughout the in- teraction. Then, we introduce the two types of action set disclosure, namely per-episode and per-stage disclosures. Finally, we present two stochastic models governing the action availability, namely Markovian and independent. In Section 3, consider the simpler case of per- episode disclosure, where the agent is informed of the available action sets at the beginning of each episode. We introduce the definitions of value func- tion, optimality, and regret. Furthermore, we present Action Restrictes gorithm based on UCBVI (Azar et al.. 2017) and analyze its regret, showing that matches the lower bound stan- dard RL up to logarithmic factors for sufficiently large T
Notation. Given o, b E N with a b, we define [a, b] :- {a, a L,.... b) and [a] == [1, al]. Given finite set X, we denote as A(X) the probability simplex over X, with | its cardinality and with P(X) its power set. Let g A(X), we denote its support as supp(g) = {x E X q(x)) > 0}.
Markov Decision Processes. We define a horizoh undiscounted MDP as a tuple M == (S, P. R, H, 3), where and AA are the state and action spaces, respectively, H is the horizon of the episode, p S x Ax [#] A(S) is the stage-dependent transition probability distribution, R S x A x [H] function, assumed to be known, 2 and 3 E S is the initial state. We assume the state space and the action space are finite sets, and we denote their cardinalities as |S| =: < +00 and |AA =: < +00. The agent's behavior is modeled with a Markovian policy π S x [H] (AA). The agent interacts with the environment for K episodes of length H, and we denote with T K the total number of decisions.
[] is the deterministic reward
UCBVI (AR- UCBVI), an al-
(Theorem 3.2).
In Section 4, we address the more realistic and challeng- ing setting of per-stage disclosure, where the available action set is revealed for the current stage only, imme-
Sleeping Markov Decision Processes. A SleMDPs is
'The scenario in which not all the actions are available for every state in a deterministic manner is discussed under the name of action masking (Huang& Ontañón, 2022), see Appendix B.
"This is mild assumption that can be removed with no addi- tional complexity learning the transition probability P is challenging than learning the reward function R.
2

---

Sleeping Reinforcement Learning
Algorithm 1: Interaction Protocol Per-episode.
Se fr
(ED(A)
1 for A E [K] do
P ((
B
0))
0.5
(G(A)
Agent observes (s), s for / E [[]] do
-1
Sy (1
2)
Agent observes state 8k.h
-1.5
Agent plays ag.A E (5,,())
A
-2
Environment returns F and 8k,4+1
(r-r-22
0
0.2
0.4
0.6
0.8
end 8 end
(a) Illustrative Sleeping MDP. (b) Optimal value functions as a
function of
Algorithm 2: Interaction Protocol Per-stage,
Figure Illustrative example.
for k E [] do
for E [H] do
PE and PS disclosure fnr (see Appendix A for a complete discussion):
Agent observes state $
Agent observes AE,A
Agent plays dx.A E Ak,s
PE disclosure. Since we know whether action F is avail- able in state B at the beginning of the episode, we play F in state A if action F is available in state B in stages h E {2, 3] getting either reward O or -1 (playing Se in stage h = 2); otherwise we play Fs getting -2 as reward. PS disclosure. Here, we do not know if action F will be available state B. we play F in state A we may wait several stages in B playing action S, until F becomes available and getting - -(1 (1-p)/p /p as expected total reward. Instead, if we play F, in state A, we get -2 as reward.
Environment returns A and 8k,6+1
7 end
end
defined as tuple M (S, where (S, A, P. R. H, s) is standard MDP as defined above, and C' is the action availability model, that will be character- ized later. Formally, for every episode k E [K]. at every stage h [H]], for the current state $E.6 E S, the avail- able action set (s, = A is an element of the power set P(A), selected according to the model C. We as- sume that at least one action can always be played (i.c., (skA() # (, Vk [K], E [H],ss,A E S).
LLC. Here, when we are in state B, we do not observe if action F is available. Since the LLC overrides F with S, when F is not available, if we decide to go through state B, we will get 22(1-p()))))))) p as expected total reward; otherwise, by playing F, in state A, we get -2 as reward.
Action Disclosure. The available actions can be revealed to the agent either at the beginning of the current episode for every stage and state, i.e., per-episode disclosure, or when the agent is asked to choose an action in the current stage and state, i.e., per-stage disclosure. The two interaction protocols are presented in Algorithms and 2, respectively.
As expected, the value functions are sorted as: Vpe(A) > VPs(A) > Viic(A), where Vpg(A), (p)(A), and V (i) represent the optimal state value function in state A in the PE, PS, and LLC cases, respectively (see also Section 6).
Action Availability Models. We admit the available action sets to be chosen in stochastic way as follows:
Example 1. To illustrate the effect of the per-episode (PE) and per-stage (PS) disclosures of action availability and
the effect of a low-level controller (LLC), we consider the MDP in Figure 2a, whose goal is to go from initial state A to the absorbing state C. We have two paths to do so. First, we can play action F, (i.e., forward safe) in state A, which deterministically leads to C with a reward of -2. Second, we can play action F (i.e.. forward) in state A and deterministically reach B without costs (r = 0). Then, in state for all subsequent stages, action is available with probability p E [o, 1]. If F is not available, we can volun- tarily stay in B and wait (i.e., play action Se), obtaining a reward of -1. In state B, there is also another action S (i.e., stay forced), that makes the agent remain in state B and receive a reward of Action Sy is employed by the LLC to override forbidden actions (i.e., the attempt to play F when it is not available). We now compute and plot as a function of p (Figure 2h) the optimal value functions for
Independent (referred as ind) action availabilities: we define C Cind SS [H] A(P(A)). For every action subset B A. state S, and stage h E [/]]. Pr(AAc,
B)sk,n s) represents the probability that B is the available action set in state at stage h. Notably, the availability of an action does not depend on whether it was available in the past.
Cjnd
Markovian (referred as Markov) action availabilities: we define C Markov S2 A x [A]] x P(A) A ((P())). For every action subsets B,B' S A. states s' E S, action
Ath and stage h [M]] C MMarkov s, = Pr(AcA B' SK,A s', Sk = s, a = A = B) represents the probability that B is the available action set observed in state at stage h, conditioned to the fact that B was the available action set, 8 the state, and a the played action at
3

---

Sleeping Reinforcement Learning
stage/ h- 1, respectively.
Algorithm 3: Acticn-Restricted Value
Iteration (AR-VI) for episode k.
3. Per-episode Disclosure
MDP M A.
Available actions (s, vh [H],sES
In this section, we face the simpler case in which the avail- able actions are revealed at the beginning of the episode for every state and stage. We start by discussing the notions of policy, value function, optimality, and regret. Then, we present algorithm matching the regret of standard RL. We highlight that the per-episode disclosure can be seen generalization of action masking (see Appendix B).
V *xHH+115) [s) =
for h E (H, H - I.... ... 1) do
Q (8. a) (s Ev- a0) (h (d') Va E (s,) eS
(i,(() = (a (x, a), V
end
return
(),(() arg max QR,((,,), Vs S, aEA2,(())
Policies, Value Functions, and Optimality. The action availabilities (s) are revealed at the beginning of each episode k E [K]] for every state & E S and stage h [+]]-
for SleMDPs with per-episode disclosure.
Thus, we restrict the policy space the policies that play available actions only, i.e., I == { 8 [M] ((A) s.t. v(s,h) S x [H] supp( (-]s)) S (s)) For episode l: and policy E II, we denote with Vř (s) the value function in state s at stage h following policy t and with (s.a)) a) the state-action value function, re- stricted to the available actions a E (s), For episode k, we denote as optimal policy any policy fulfilling o e arg malx V (8) and the optimal value functions as (s) = Vi" (s) and (s, = 0, (s, a). An op- timal policy z can be retrieved as the greedy policy w.r.t. Q% restricting to the available actions using a variation of value iteration, namely Action-Rest r cted Va Vulue Iteration (AR-VI, Algorithm 3).4
Theorem 3.1 (Lower Bound - Per-episode Disclosure). For any algorithm 2, there exists an instance of Sleeping MDP such that, for T 3 (A), the per-episode disclosure regret satisfies:
[ 2 T) 2 (HVSAT).
Proof. The proof directly follows from that of (Domingues et al., 2021, Theorem 9).5 We have to lower bound the regret on the worst instance of SleMDPs with per-episode disclosure. Since the SleMDPs per-episode disclosure are generalization of MDPs (an MDP is a SleMDP where (s, A, Vs E S, E [M]] k [K], the regret lower bound for MDPs holds for SleMDPs too.
Regret. We evaluate the performance of an algorithm 2 in terms of cumulative regret over the K E N episodes against the optimal policy n of each episode.
Algorithm. To learn in the per-episode scenario, we modify UCBVI (Azar et al., 2017) to handle the action availabilities. We design Act in - Restriicter UCBVI AUBU,, Algorithm 4), the optimistic counterpart of the AR-VI (AI- gorithm 3). From a high-level perspective, besides the fact that the maximization in Bellman's equation is computed over the available actions An,x (s) only, AR-UCBVI has to carefully handle the optimism to guarantee a monotonicity property of the sequence of estimated state-action value functions. The algorithm starts by initializing the visitation counters (line 1). Then, for every episode k E [K]. the algorithm observes the action availabilities Ag, (line 3) and estimates the transition model (s', a) (line 4):
Definition 3.1 (Per-episode Disclosure Regret). Let 2 be algorithm playing sequence of policies (Tx) X k=1 llg we define the per-episode (PE) disclosure regret as:
K
RpE(21, (2, T) = Σ (3) KE [K]
(1)
Since we know which actions are available at every stage and for every state in advance, we can afford to compete against the best policy oे in every episode. Indeed, re- gardless of the fact that the action availabilities (s) are chosen in a stochastic or adversarial way, we are able to tackle the problem as if we were in different MDP (defined in terms of the available actions) in each episode k.
Pr,(('(ss, Nan(s,,,s))
(2)
Ne, a)
where Ne,A.., a) is the number of times action a was played in state s in stage h, and NE, a, s') is the number of times the next state was s'. Then, AR-UCBVI runs opti- mistic value iteration to obtain optimistic estimates of the op- timal cetion-valuee function Q (s, a). As mentioned above, this step requires more attention w.r.t. that of (Azar et al.,
Lower Bound. We now present a minimax lower bound
*With little abuse, we are using the same symbol even for stage h- = 1, where 1t ai- and Ae, are not defined. In such case, we consider Caarroon (13' 8') = Pr(Ac,1 = B'|ax,1 = 8') as the initial-action availability distribution.
"This is totally equivalent solving an MDP with action sets that depend on the state and stage.
"This result differs from the one of (Domingues al., 2021) due to the different notation adopted.
4

---

Sleeping Reinforcement Learning
Algorithm 4: AatiinnRessricced UCBVI
refined analysis of UCBVI (Drago et al., 2025) and is defined as:
(AR-UCBVI).
Initialize: (8, = 0, (s.
4L (.
7HL (N,
(s) V(s, a, s h) e x A x 8 [H]
9 (8, a)
N5,(8,a)
for k E [K] do
3 Agent observes (t), Vh [
Q. 8E e' P P..((18,)) N,,n(s,a)
Estimate (r.,(6'|s,,0 a) as Eq. (2)
5
//Compute V2, Qx. (1-)) for episode k
(8, = - 1,
where V J.A = Var yarr-Paa(lssa) [VK [5') is the empirical variance of the next-state value estimate, Q. ( = min S2 AL/N AL ( H²) is the ad- ditional bonus, and T. - In(5H Then, we compute the value estimate
for j E [K]
Initialize A # (8) VsES
for (H,
1..... do
10
for s E S do
Compute (s, a), Va E (s,)(s) as in Eq. (3)
11
y, (s) = ma Q),, a). Finally, the algorithm plays action greedily w.r.t. the optimistic estimate ( a) (lines 17-22).
Compute 1/ (s)) aE (6)
max ())))
12
13
end end
14
The following result provides the regret of AR-UCBVI, showing that learning in a SleMDP with per-episode disclo- sure does not increase the regret w.r.t. standard RL.
15
end
16.
//Play opt cimmmtiicalll for episode k
17
Agent observes state 82.1
18
for & E [H] do
Theorem 3.2 (Upper Bound - Per-episode Disclosure). For 6, the per-episode disclosure regret of AR-UCBVI is bounded by:
19
Agent plays dRAA arg max (sk,,,) (CEE,)
any 8 E (0, 1), with probubility
20
Environment returns Tk.h and 8k,4+1 Increment counters
21
RRE(AR (CBBI,, < 34H SAT + 2500H 52 ALL where T, = ln(5HSAT/0)) For T > S3 A), selecting
22
end
end
8 = 1/T, we have:
2017). Indeed, the original UCBVI, to ensure a monotoni- cally non non-increen con-increasing sequence of the estimates Qe,,(s, a). limits the current estimate Qu, (s, a) (computed with all samples up to episode k- - 1) to the previous episode esti- mate (,-,, a) (computed with all samples up to episode 2) This operation makes no sense in a SleMPD since the action availabilities AR,A (s) and (x-1,((s) may change be- tween consecutive episodes, making Q a) no longer an optimistic estimate of the true Q a). For this rea- son, we have to compute the sequence of optimistic value functions 1),n( a) for the action availabilities (s) of episode using the estimates PI of all episodes with j [K]] This way, make use of all the samples collected so far (even in episodes j with action availabilities different from the current ones (s)) Furthermore, this ensures that the sequence of estimates Q),, (s,a) a) is monotonically non-increasing in j. As shown in Algorithm 4 (lines 6- 65), AR-UCBVI starts from h = H and goes backward comput- ing the optimistic Q (s. a) for every a E (s):
E E[RPg(AR-UCBVI,T)) & Ô (HVSAT))
where the expectation is taken w.r.f. the stochasticity of the environment.
Proof. The proof of this theorem follows the one of (Azar et al., 2017, Theorem 2). The key challenge is the com- putation of the bonus b,,0 Indeed, Lemma 17 of (Azar et al., 2017) heavily relies on the fact that the sequence VR, (8) - (s) is monotonically non-increasing in k. This is not the case for our sequence ( - Vi,, (s) since, as already explained, the action availabilities As, (s) change across episodes. For this reason, resort to the sequence V (s) V (s) for fixed k which is monotonically non- increasing in j. This allows us to apply Lemma 16 of (Azar et al., 2017) pretending to have played in the MDP with ac- tion availabilities of episode k i.e., Ak, (s), ) for all episodes j E [b] and, ultimately, getting the bonus as in Lemma 17. Notice that we apply the pigeonhole principle considering (s, A which represents the worst case.
(s)) (s.a). inh (), ()) (s,a),
4. Per-stage Disclosure: Markovian Case
Ra(s,a)+ + Σ V, (5') ()')) 18 JES
We now analyze the realistic scenario where the set of available actions is revealed for the current stage only with no knowledge of future availabilities. In this sec-
where 62.4(s. a) is the exploration bonus obtained from
5

---

Sleeping Reinforcement Learning
tion, we focus on Markovian availabilities i.e., Ak,k CMarroo (-1sk,,, Sk,A-1, AR,
the optimal policy #* constant throughout the episodes.
Definition 4.2 (Per-stage Disclosure Regret), Let 2 be an algorithm playing sequence of policies (mx) e I1 we define the per-stage disclosure (PS) policy regret as:
Augmented MDP, Policies, Value Functions, and Opti- mality. To address this scenario, we can map the SleMDP with an augmented MDP in which we encode action avail- ability sets in the state representation.
Rps(A. (2. T) = (V
Σ (3) kE[K]
Definition 4.1 (Augmented MDP). Let M (S, P, H) be a SleMDP, we define the augmented MDP M (S.A.P. R. H, Po), with:
Differently from the per-episode case (Definition 3.1) where comparator मे changes over episodes, in the per-stage case (Definition 4.2), we consider constant comparator Ø*.
augmented state space S S==S P(A);
Algorithm. Given the mapping to the augmented MDP, we can resort to the original UCBVI (Azar et al., 2017) to learn in the SleMDP with the following regret guarantees.
augmented transition probability, defined for every 3= (s, (s', E S. a A, and h E [M]] as: P1(3313,a) a) = (s'ls, a) a) Markov reward function, defined for every 3 = (s, B) E S and a as: R(3, a) R(s.at) a):
(B')soorBBBsss (B')s',,, 1,,,00. a, B);
Theorem 4.1 (Upper Bound - Per-stage Disclosure: Marko- vian). For any ā E (0, 1), with probability 1 1 8, the per- stage disclosure regret of UCBVI with Fernstei-FFreedmee bonuses (Azar et al., 2017, bonus-2) on the augmented MDP is bounded by:
initial augmented-state distribution, defined for every 3 Sa Bs, E S as P3(3) Markov (B = 3).
Note that the augmented MDP has a state space with car- dinality |S| S2A, exponential in A. The policy space in the augmented MDP is defined as î == { S [H]] ((A) s.t. v3- = (s. B) E S supp ( B)) C B}, to en- sure that only available actions are played. 6 For a policy म. augmented state 3 = Bs, available action e B, and stage h E [H]]. we denote with (3) = ((s, and 2 a) O ((s, B), a) the value and state-action value functions, respectively, in the augmented MDP, the latter restricted to the available actions a E B. An opti- mal policy for the augmented MDP is any policy such that * E arg xexx T and the optimal value functions as
+ RPS(UCBVI, & +2000' S² A22
where L. = 1og(5HH=22ATT/00 In particular, for T 2(H 53 A322A)) and selecting 6 = 24//T /T, we have:
E [RPS(UCCB T)] & Ô ( (HVSATZA)
Proof. The proof is an application of (Azar et al., 2017, Theorem 2), where consider the state space cardinality S24 of the augmented MDP and the stage-dependent tran- sition probabilities (equivalent to increasing the state space cardinality by a multiplicative factor of H)).
(B) 77** * (3) and (7, a) 0%* (3, a). An optimal policy 7 can be obtained as greedy w.r.t. Q+. The optimal value functions can be computed using value iteration on the augmented MDP (see Algorithm 5).
The regret guarantees of Theorem 4.1 are clearly unsatisfac- tory due to the presence of the exponential dependence on the cardinality of the action space A. the following, we show that such an exponential dependence is unavoidable when the action availability follows a Markovian process.
Considering the protocol of Algorithm 2, we define the
value function for the original SleMDP v/=(() (3) in the initial state 8 E S as the expectation of that of the augmented MDP V ((3, B)) over the available action sets B P(A):
Lower Bound. The following theorem presents the lower bound on the Markovian per-stage disclosure regret.
Theorem 4.2 (Lower Bound Per-stage Disclosure: Marko- vian). For any algorithm 2, there exists an instance of Sleeping MDP with per-stage disclosure and Markovian action availability such that, for T 3 Q(HHS and b I2AA), the per-stage disclosure policy regret satisfies:
V (3) B--MMan (-12)
E
((3, B))]
(4)
Similarly, for the optimal value function, we have: (T) == [ [V) ((,,
Regret. We evaluate the performance of an algorithm in terms of cumulative regret over the K E N episodes against
E [Rps (21, [T, > Ω (HVVSAT24N)
"Note the fundamental difference w.n.t the per-episode case, where the policy space was different for every episode while here the per-stage case, the policy space the same for episodes, hut the policy is conditioned to the actual available actions set B. "As usual, we in an MDP and, therefore, there exists policy * optimal from every state T.
Proof Sketch. The instances are made of two parts (see Fig- ure 3). First, every instance has an A-ary tree MDP as in (Domingues et al., 2021), where all actions are available. Then, we attach partial sleeping lattice to every leaf, in which the state 8; does not change, and whenever an action
6

---

Sleeping Reinforcement Learning
Ya y ou
Algorithm 5: Sleeping VI for = Marrron
Imput:Sleepingg MDP M (S, A, M P. H,
V ((, = 0, As E S,B P(A) B3)
1///////
for h [H, H - 1, .............................. 13 do
3
(1s B), = R),
A-ary Tree (Domingues et al.. 2021)
(x Fa M A B, P(A), a
Vit (i
Vi (1s, B)) max 0% ((s, B),a), AS S,E
P2/314
P1:214
PL/ara
end
returr 2 (x. E arg max Of ()s,B)..) a). e S, BE P(A), h [H]
P2/4
12:3
Pay2
Algorithm 6: Sleeping VI for C Cind
Sloeping Lattice (ours)
Input: :Seepping MDP M - (S. Cind , H. 11++(s) = O, E
for E [H, H -....,, do
( a) = Rs (s, + Bg Pa (1 [/-=
Figure 3. Instances used in the proof of Theorem 4.2, Available actions are reported next to the nodes.
3
Va E A, E
V (g-ck((1+)) (11+) [max.es (+ ()) V
an is played, it gets removed from the next set of available actions, i.e., (s,) = (s,), Man) This happens for A/2 times, until we reach the largest layer of the lattice, i.e.,
end
retuur "h (s.B) E arg max (s) V S, BE P(A), He [H]
the one with (1/2)= R 24/2 nodes. At this point, whatever action played, the next action availability set will be a singleton either containing t or a with equal probability. at (resp. a ) leads to an absorbing state with reward +1 constructed by electing a leaf state s* an action a², a stage h* and an availability set 8*
Equation (4), it convenient to introduce the value function V (s) = Eg- (-(s) IV,"* B)]. Given these quantities, to solve a SleMDP with independent availabilities, we resort to a simpler value iteration approach (Algorithm 6).
(resp. - 1). Hard instances
(with |B*| A/2) that increase by > 0 the probability of getting singleton {a in the next stage.
Lower Bound. The following theorem provides a regret lower bound, by reducing the considered scenario to an MDP in which all actions are always available.
This lower bound, using novel construction (i.e., the sleep- ing lattice, Figure 3), shows that an exponential dependence on A is unavoidable when there is temporal correlation among the sets of available actions. Given this statistical barrier, we next discuss tractable scenario in which the action availability is sampled independently at each stage.
Theorem 5.1 (Lower Bound Per-stage Disclosure: Inde- pendent). For any algorithm 21 there exists an instance of SleMDPs with independent action availability with per- stage disclosure such that, for T > ((H2 the per- stage disclosure regret satisfies:
E [[Rps(21, (1, T)} Ω (HVSAT)
5. Per-Stage Disclosure: Independent Case
Proof Sketch. The formal proof provided in Appendix C. Similarly to Theorem 3.1, the proof directly follows from that of (Domingues et al., 2021, Theorem 9). We have to lower bound the regret on the worst instance of SleMDPs with independent per-stage disclosure action availability. Since the SleMDPs with independent per-stage action avail- ability are a generalization of MDPs (an MDP is a SleMDP where Ciid (Alss 1, Vs E S.h [H],, the regret lower bound for MDPs holds for SleMDPs too.
We now discuss the scenario in which, at every stage, the available action set Ae, is sampled independently from the past, i.e., Ar, ~ Cird (-Isk.)). The lack of tempo- ral structure allows removing the dependence of the value functions on the available action sets, differently from the augmented MDP of Section 4. Indeed, looking at the Bell- man's equation in the augmented MDP (line 3 of Algo- rithm 5), we realize that (l does not depend on B, removing such a dependence from the state-action value function Q ((s, B). a), that, from now on, we will denote as (s, a). Moreover, similarly to what has been done in
Algorithm. To efficiently learn in this setting, we propose an algorithm that extends UCBVI (Azar et al., 2017) with the
7

---

Sleeping Reinforcement Learning
Algorithm 7: S Sleeping UCBVI (S (S-UCEVI).
2 [ 48 A Pa (l))
1 Initialize: No. a, 6 = 0, (s. = O,
+
Nu, ())
(s) = 0, (s, =0, (( s h B) e Ax [M] x P(A)
3
where VE, Var s - [VE,++1 is the empir- ical variance of the next-state estimated value function, 12 ( min 11 10 A2 13/Ne,x+1(5)) H13 is the additional bonus term, and L log( (8 A2*T/6). Then, we compute the optimistic value function (s) as:
4 (s,a) = H +++ 1, V(s,a,)) e x Ax [M]
5 for A E [K] do
//Compute V2. (+) kR. (+-)) for episodo k
7
Estimate (s.s(''|s, a) as in Eq. (2)
Estimate C.. (B]s) as in Eq. (5)
Initialize V2, (s) - 0. V
(x)
Σ
Gind (B(x) (005s)maxx2 maxQu
(7)
for (H, H 1, 13 do
aEB
BEP(A)
11
for
do
Compute Qu,n a), Va E A. as in Eq. (6) Compute (s) in Eq. (7)
where b a bonus accounting for the uncertainty on the action set availability defined as:
14
end
15
end
bk (s) =
4LQu,
7HL NMA(s) 3(N - 1)
16
//Play optimistic for opisode l
17
Agent observes state S4,1
18
for h E [M] do
4E BB EAA (11) La (8, (s, BR,n
19
Agents observes action AR, (8
20
Agent plays ax,A arg max (8K,())
Nk.((s)
(SE,),
21
Environment returns T and 8k,++1 Increment counters
where (s. Var B- (12 TR. A B))] and (s, = m H L2 a), H²) is an additional bonus. Finally, the algorithm plays an action greedily w.r.t. (s, (lines 17-23).
22
end
24 end
estimation of the action availabilities Cird(11s) Sl Sleeping UCBVI (s UCBBI,, Algorithm 7) is an optimistic algorithm where the key innovation is using two bonuses, one for the state-action value functions (u, (s, a) (as for UCBVI, to handle uncertainty on P) and one for the state value functions V (s) (to handle uncertainty on C). We estimate the transition model as in Equation (2) (line 7) and we keep an estimate of the action availability as follows (line 8):
We provide the regret upper bound of S-UCBVI for per- stage disclosure and independent availabilities.
Theorem 5.2 (Regret Upper Bound S SCUCBVI with in- dependent availability and per-stage disclosure). For any 8 (0, 1), with probability 1-5, 8, the per-stage disclosure re- gret of S -CUBBII on any SleMDP with str-stage disclosure independent action availabilities is bounded by:
$512HVSATIC
Gidd (B|s) = (s, (8)
(5)
+ 19821"5 S L2G,
where (s) ) is the number of times state s is visited at stage and Nr.1. (s, B3) is the number of times we observe ac-
where = log(80HS - and G = log HSAT). In particular, for T S5 AA and selecting ó
tion availability B. Then, we perform an optimistic value it- eration (lines 9-15) obtain the optimistic estimate (s) and (s, a) by means of two additive optimistic bonuses. Going backward from h H. we compute Qk, a) as:
2 /T, we have:
E E|Rpg(S-UCBVI, & Ô (HVSAT)
(s, a) = min (Q,,L)(s,a))
Proof Sketch. The proof is provided in Appendix and extends (Azar et al., 2017, Theorem 2). The key differ- ence is the use of two bonus terms to ensure the optimism of both Ve,n and QR,6 due to the estimation of the action availabilities Ōind and of the transition model Pk.k- Given k Vi V and AR = Q Q7, we notice re- cursive dependence, that we unfold since A can be derived from A and A is obtained by upper-bounding A as:
(6)
a)(s,a) + 0 as) + Σ (e stES
where (s, a) is the exploration bonus to account for the
uncertainty the transition model estimate P.
ALV
7HL
(s,a) V (,)((s,))
3(N,, a) - 1)
AV EDV DK + + + 44H M/NK, A k.h.
8

---

Sleeping Reinforcement Learning
Per-stage Disclosure
Per-episode Disclosure
Lower Bound
Upper Bound
Lower Bound
Upper Bound
a HVSSA
δ (HVSAT
Independent
T (AH Theorem 5.1
T 5M 5 A
2 HVSAT
Ô (HVSAT
Theorem 5.2
3 ((H Theorem 3.1
T 2 ( Theorem 3.2
Ö (HVSATZA
Markovian
T ((HSA24)
T 2(H (AA21)))) Theorem 4.1
Theorem 4.2
Table 1. Summary of the results.
where & is martingale difference sequence that leads to lower-order term. As such, we upper bound the two quantities as done in Lemma 3 of (Azar et al., 2017) at the cost of multiplicative e constant, avoiding any exponential dependency on A in the higher-order terms. Then, extending the rationale of (Azar et al., 2017), via backwards induction, we show that the empirical variance small enough that the additional bonuses by,n and D2,A guarantee that VELA and Qk.k are indeed optimistic. This is done by deriving an upper bound on ( Q% (8,a) in the order of:
Per-episode e Per-stage. We restrict to stochastic avail- abilities sampled independently at every stage, i.e., via Clndd
Indeed, in this case, to be pre-sampled for every k E [K] and (s, h) E S x [H]. In the per-episode disclosure, (s))(s) is revealed at the beginning of episode k. while in the per-stage disclosure (s, is revealed only when, at episode k. we reach state s at stage h. This observation allows concluding that the expected optimal performance in the per-episode disclosure is superior that of the per-stage disclosure:
imagine availabilities (k,)(s)
(s, (M(( (O A2" Then, we use the latter result to derive an upper bound to (s) (s) in the order of:
E LVVE = E
max FRell&
B max (T = (3)
well
Per-episodee
Per Per-stage
where the expectation is taken w.r.t the randomness of (s), and where I. and IT are defined in Sections 3 and 4, respectively, and the inequality follows from Jensen's 's.
(s) V (s) (' (NN,a))))))
Subsequently, we use these inequalities to show that Q Q7 and VR V hold, thus, demonstrating the optimism. Finally, we derive the regret bound by combining the terms in the upper bound of AY observing that, when applying the pigeonhole principle, we consider all the actions in A as available, as this provides the worst-case allocation.
Per-stage > LLC. The LLC can be regarded as a (possibility stochastic) function that, given an un- available action assA & Ar, sampled from pol- iey (n(',,,,)), overrides with an available action dn E Akt sampled according
some strategy p (-Is,,, (1 As,n). Thus, the overall effect of the LLC is equivalent to playing a policy (-Is As,.) = LeEA ph: ( (g.h. a, Ak,h) m. (al sk,h)) that belongs to the policy space II on which we optimize in the per-stage dis- closure case. Thus, the performance of the LLC cannot be larger than that of the optimal policy of the per-stage case (i.c., V
This result shows that for a large enough T, the regret suffered by S-UCBVI is of the same order as that of UCRVT-BF (Azar al., 2017, Theorem 2), matching the lower bound for standard RL, up to logarithmic terms. Thus, the need for estimating the action availability Crind that is distribution over ((A), results in minimum value that scales exponentially with A. Nevertheless, no exponential dependence on is present in the leading term.
& max VT²(3) Vi+(3))
Future Works. Interesting future research directions in- clude investigating action availability structures that are more general than the independent case while preserving statistical tractability. Moreover, it is of interest to devise instance-dependen features to characterize the complexity of an instance the regret bounds based on the characteris- ties of action availability.
6. Discussion and Conclusions
We summarize the results presented in this paper in Table 1. We motivated the introduction of approaches aware of the action availability in opposition to an LLC since they allow learning better-performing behaviors. We illustrated this in Example 1. Now, we formally prove that this is the case.

---

Sleeping Reinforcement Learning
Acknowledgments
Drago, S., Mussi, M., and Metelli, A. M. A refined analysis of ucbvi. arXiv preprint arXiv:2502.1337) 2025.
Funded by the European Union - Next Generation EU within the project NRPP M4C2. Investment 1.3 DD. 341 15 March 2022 FAIR Future Artificial Intelligence Research Spoke 4 PE00000013- DS3C22002380066.
Gaillard, P., Saha, A., and Dan, S. One arrow, two kills: A unified framework for achieving optimal regret guaran- tees in sleeping bandits. In Proceedings of the Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), volume 206 of Proceedings of Machine Learn- ing Research, pp. 7755-7773, 2023.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Huang, S. and Ontañón, S. A closer look at invalid action masking in policy gradient algorithms. In Proceedings of the International Florida Artificial Intelligence Research Society Conference (FLAIRS), 2022.
References
Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. In Advances in Neural Information Processing Systems (NeurlPS), pp. 89-96, 2008.
Kanade, V. and Steinke, T. Learning hurdles for sleeping experts. ACM Transactions on Computation Theory, 6 (3):11:1-11:16, 2014.
Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Reseurch, pp. 263-272, 2017.
Kanade, V., McMahan, H. B., and Bryan, B. Sleeping ex- perts and bandits with stochastic action availability and adversarial rewards. In Proceedings of the International Conference Artificial Intelligence and Statistics (AIS- TATS), volume 5 of JMLR Proceedings, pp. 272-279. JMLR.org, 2009.
Bartlett, L. and Tewari, A. REGAL: regularization based algorithm for reinforcement learning in weakly communicating mdps. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp. 35-42. AUAI Press, 2009.
Kleinberg, R. D., Niculescu-Miine A., and Sharma, Y. Re- gret bounds for sleeping experts and bandits. Pro- ceedings of the Annual Conference on Learning Theory (COLT), pp. 425-436. Omnipress, 2008
Blitzstein, J. K. and Hwang. J. Introduction to Probability Second Edition. Chapman and Hall/CRC, 2019.
Kleinberg, R. D., Niculescu-Mizil, A., and Sharma, Y. Re- gret bounds for sleeping experts and bandits. Machine Learning, 80(2-3): 2010.
Cesa-Bianche N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University Press, 2006.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Chatterjee, A., Ghalme, G., Jain, S., Vaish, R., and Narahari, Y. Analysis of thompson sampling for stochastic sleeping bandits. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAT). AUAI Press, 2017.
Maurer, A. and Pontil, M. Empirical bernstein bounds and sumple-varianee penalization. In Proceedings of the Anmual Conference on Learning Theory (COLT), 2009,
Cortes, C., DeSalvo, G., Gentile, C., Mohri, M., and Yang. S. Online learning with sleeping experts and feedback graphs. In Proceedings of the International Conference Machine Learning (ICMI.), volume 97 of Proceedings of Machine Learning Research, pp. 1370-1378. PMLR, 2019.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. A. Playing atari with deep reinforcement learning. CORR, abs/1312.5602, 2013.
Nguyen, Q. M. and Mehta, N. Near-optimal per-action regret bounds for sleeping bandits. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 238 of Proceedings of Machine Learning Research, pp. 2827-2835. 2835. PMLR, 2024.
Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M. Episodic reinforcement learning in finite mdps: Min- imax lower bounds revisited. In Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pp. 578. PMLR, 2021.
10

---

Sleeping Reinforcement Learning
Osband, I. and Van Roy, B. On lower bounds for regret in reinforcement learning. CoRR, abs/1608.022) 000322 2016.
Saha, A., Gaillard, P., and Valko, M. Improved sleeping ban- dits with stochastic action sets and adversarial rewards, In Machine
Proceedings of the International Conference Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 8357-8366. PMLR, 2020.
Sutton, R. and Barto, G. Reinforcement learning: An introduction. MIT press, 2018.
Vinyals, O., Ewalds, T., Bartunov, S., Georgiev, P., Vezhn- evets, A. S., Yeo, M., Makhzani, A., Küttler, H., Agapiou, P., Schrittwieser, J., Quan, J., Gaffney, S., Petersen, S., Simonyan, K., Schaul, T., van Hasselt, H., Silver, D., Lillicrap, T. P., Calderone, K., Keet, P., Brunasso, A., Lawrence, D., Ekermo, A., Repp. J., and Tsing, R. Starcraft II: new challenge for reinforcement learning. CoRR, abs/ 777.00887. 2017.
Weissman, T., Ordentlich, E., Seroussi, G., Verdu, S., and Weinberger, M. J. Inequalities for the 11 deviation of the empirical distribution. Hewlett-Puckard Labs, Tech. Rep, pp. 125, 2003.
Zhang, Z. Chen, Y., Lee, J. D., and Du, S. S. Settling the sample complexity of online reinforcement learning. In Proceedings of the Annual Conference Learning Theory (COLT), volume 247 of Proceedings of Machine Learning Research, pp. 5213-5219. PMLR, 2024.

---

Sleeping Reinforcement Learning
A. Example
Se (r=-1)
F 0r=
F (r=00 0)
B
Sj (r=
A
Fs (-=
Figure 4. Illustrative Sleeping MDP.
In this appendix, we discuss an example of Sleeping MDP, analyze the two disclosure scenarios described in the paper (i.c., per-episode and per-stage disclosure, indicated with PE and PS, respectively), and the case in which we do not have information about the available actions, making use of a low-level controller (LLC) to correct taken actions that are not available, generating an equivalent MDP as depicted in Figure la.
Consider the Sleeping MDP depicted in Figure where the goal is to go from initial state A to the absorbing state C. To reach this goal, we have paths, the first (the one below) is safe but costly, the second one is unsafe and may be not always available, but has cost. More formally, consider an undiscounted finite-horizon Sleeping MDP with initial state A, and absorbing state is C (we assume infinite horizon here since there is probability 1 of reaching state C). To reach the absorbing state, we have two possible paths, which can be chosen using deterministic actions. The first one is the one following action F, (i.e., forward safe), which deterministically leads to the final state with total reward 22 The second path, instead, leads to the final state through state We assume we can always take action F (i.e., forward) in state A and deterministically reach B without costs (r 0). Then, when we are in B, the next forward action may be available or not, and we assume it is available with probability p (formally Pr(F An (B) p, for every stage h). If F is available, we can voluntarily stay in B and wait (i.c., play action S.). obtaining a reward of - 1, try to go anyway. In state B, there is also another action Sy (i.e., stay forced), that makes the agent remain in state B and receive a reward of 2. This latter action will be employed by the LLC to override forbidden actions (i.e., the attempt to play F' in state B when it is not available).
We now compute the value functions of this Sleeping MDP for the three scenarios under analysis.
Sleeping MDP with per-episode disclosure. We first analyze the optimal value function VPE(A) in state A for the per-episode disclosure scenario. We recall that in this case, we knew the action was available at the beginning of the episode. is easy to observe that, considering convenient if h can choose the safe path).* 8 Knowing that such action will be available with probability p. the probability
as the moment in which the first decision is made, the path through B will be h the action F will be available in state B (if action F will be available for the first time in
h 4 or later, that it will be available at time h = 2 is indeed while the probability that will be not available in h = 2 but will be available in I = 3 (1 - p)p. Given that, the value function for state A is:
VPPE, (A) = 0.
P available in h-2
-1. (p(1- p)) -2 (p p)))
available in h-3 and hm=
Otherwise
Sleeping MDP with per-stage disclosure. We now analyze the optimal value function (As. in state A for the per-stage disclosure scenario, where we do not know the actual action availability in advance. Given the simplicity of the problem, we
For the sake of precision, it is relevant if action F is available in state B when h because we in such state and we cannot play it.
12

---

Sleeping Reinforcement Learning
V (A)
(D)
0..
(A)
V.
-1
-1.5
-2
0
0.2
0.4
0.6
0.8
Figure Optimal value functions V (A) for (PE, PS, LLC).
analyze value functions from the final state backward. We first observe how, for absorbing state C, we have Vps,A (C)
for every & N. Then, we move to state B, and we trivially observe that the optimal policy is to go to state C if possible (i.c., if action is available), and use action S. otherwise. The value function for state B is:
V (B) p(0 + V P (C)) (1 p) P (B)).
Since VPS. (B)
V 1 (B), by solving for VPs (B), get:
1-p
Vs (B)
p
Given that, state the optimal policy will choose the best path in expectation, its value function will be:
(A) max - 222 1-
-2
Sleeping MDP as and MDP with LLC. We finally suppose that we want to handle this Sleeping MDP as it were standard MDP with stochastic actions and rewards depending also the landing state. We start before by observing that
Vita (C) 0. Then, can reason about state B. It is clearly visible that we have try go state C; otherwise,
will
continue to pay the cost of staying in B (for sufficiently large horizon). Given that, the expected value of this state is 0 if we play action F and it is available, -2 if we play it when it is not available. Formally:
Vitc, (B) p(0 + VLtc (C)) + (1 - (- 2 + Vitc (B))
Since, Vit. ViLc. (B) we get:
Vi = -2 p
As before, in state A, we can select the best action, leading to:
Vicc (A) = max -2, (1 (1pp)
p
Comparison of the Results. Figure 5 shows the value functions for the three cases for all the values of p [o, 1]. We observe how, as supported by the intuition, for every [0, 1]. it is always better to know the action availability in advance (VPE( (A) > V (A)), as we have more information and we can take better decisions. This implies that the two notions of regret must differ (given that the two optimal value functions will be different), in particular in terms the comparator we use, which should appropriate and reachable. Finally, we observe that the performance of the equivalent MDP integrating the low-level controller the worst, as expected.
13

---

Sleeping Reinforcement Learning
B. Related Works
In this appendix, we summarize the relevant literature for this work. We start by presenting an overview of the fundamental works in the sleeping MAB literature, as this problem has never been faced in the RL scenario. Then, we introduce works on invalid action masking in RL. Finally, we summarize the main results on regret bounds for standard RL.
Sleeping MAB. (Kleinberg et al., 2008; 2010) are the seminal works for the Sleeping MAB setting, In their work, the authors study both the full and partial information settings, considering both the stochastic and adversarial reward models and adversarially chosen action sets. (Kanade et al., 2009) presents the first polynomial time algorithm for MAB with adversarial rewards and stochastic action sets. In the same scenario, (Saha et al., 2020) improves the performance, keeping the computational complexity polynomial. (Kanade & Steinke, 2014) presents the first polynomial time algorithm bandits with both adversarial rewards and action sets, and (Nguyen & Mehta, 2024) achieves near-optimal regret bounds this scenario. (Chatterjee et al., 2017) studies the setting with adversarial action sets and Bernoulli rewards. (Cortes al., 2019) extends the Sleeping framework to consider graph feedback. (Gaillard et al., 2023) studies different notions of regret in the sleeping MAB setting, and discusses their relation.
Invalid Action Masking for RL. Several works consider the possibility of having not all actions available in all the states (Vinyals et al., 2017). This deterministic masking operation can be done over several types of algorithms such as policy gradient solutions (Huang Ontañón, 2022) and state-of-the deep RI. algorithms such as DQN (Mnih al., 2013). However, in all these works, given a state s, we have a deterministic mapping to the action availability (i.e., C: - P(A)). consider way more challenging scenarios, as we have, given a state, probability distribution over the
In this work, instead, available action sets (i.c., C' S A(P(A))), also in the per-episode disclosure scenario, that can be seen stochastic generalization of action masking.
Minimax Regret Bounds for RL. (Auer et al., 2008; Jaksch et al., 2010) present the first minimax lower bound in the order of AT) for average reward MDPs with stationary transition probabilities where D is the diameter of the MDP. 90 (Domingues et al., 2021) generalize this result by providing a standard proof framework for episodic MDPs and demonstrate a lower bound in the order of (SAT) with stage-dependent transitions and (SV)STT) with stage-independent ones. From the algorithmic perspective, (Jaksch et al., 2010) propose JCRL2, which enjoys O(DSVAT) regret with stage-independent transition. (Azar et al., 2017) propose UCBVI, which enjoys transitions and Ö Ō(HVSAR with stage-dependent ones." (Zhang et al., 2024) theoretically improves the result of (Azar et al., 2017), even if preserving the same (optimal, up to logarithmic factors) rate, by reducing the requirement for the minimum T' needed in order to match the lower bound.
regret with inge-independent
C. Omitted Proofs of the Lower Bounds
C.1. Proof of Theorem 5.1
Theorem 5.1 (Lower Bound Hound-Peree Per-stage Disclosure: Independent). For any algorithm A. there exists an instance of SleMDPs with independent action availability with per-stage disclosure such that, for T i ((H2SA), the per-stage disclosure regret satisfies:
E [Rps( 21, TT] 2 (HVSAT).
Proof. This proof closely follows the one of (Domingues et al., 2021, Theorem 9). In order to demonstrate the lower bound for Sleeping MDPs with per-stage disclosure in the case of independent action availabilit,, first modify the class of hard MDP instances provided in (Domingues et al., 2021, Section 3.1), and then we follow similar derivations to the original proof, thus reporting only the relevant modifications.
Definition of the Sleeping MDPs class. We start by modifying the class Cr.e' provided in (Domingues et al., 2021) to transform it into a specific class of Sleeping MDPs. As in the original proof, the SleMDPs all have three special states: a
Thhis result considers different setting w.r.t. the one of finite-horizon MDPs considered in this work. However, we can generalize this result by observing that H7 = ((D), see (Domingues al., 2021).
10 (Bartlet & Tewari, 2009) present a variant of the lower bound which does not hold in general, see (Jaksch et al., 2010; Oshand Van Roy, 2016) for a detailed discussion.
'The result of (Azar et al., 2017) is derived with stage-independent transition. However, we derive the result by considering a fictitious MDP with augmented state space S x [.]].
14

---

Sleeping Reinforcement Learning
waiting state Swn a good state Sg. and bad state 86. The remaining S states are arranged in A-ary tree of depth d 1. The agent starts each episode in Sus and can select remain in Sw by playing action Our up stage H, after which it is forced to transition to state Broot, which is the root of the A-ary tree. For every triplet:
(h a²) E {1 +1+ d..... H + d C M(ww),
we define a Sleeping MDP Ms.(uu a*) as follows. The action availabilities in sw are defined as:
Cind (Alsw) = 1, vh E [
meaning that all actions are available in the waiting state, and the transition probabilities from 8n are defined as:
(1 = Sw: OKih aw) 1[ < H)
Ph (srootlss = Swi OK,h = aw) Pn = Sw: ak,h = aw),
(S Sws agah 0) 1, Va # aw h E [H].
Let I = 3 u u [b]) } be the set of internal nodes of the A-ary tree, then the action availabilities inside the tree are defined as:
Cind (Als) 1, I.
The transition probabilities for any state in the tree deterministic: playing the a-th action leads deterministically to the a-th child node of the current node. For every leaf node 81 E L, we define the action availabilities such that:
Pr(aw E As)((s)) = 1, Vs C, k E [K], h [M]. Cind(B)s) = ce [o, 11. Vs E a. Afaal, ke [K] e [H].
Pr(a E Ak,)(s))
Σ
(EP(A)sM s.t. aE
As such, at least one action is guaranteed to be available at every stage of every episode, and every action (except a. is available with probability The leaf nodes are the only nodes which can transition to Sn and 8b, and they do so according to the following transition probabilities:
1
Pa (s a) = + Au 2 Pa (s a) = 1 ())
where A 1 .x)) (h, $i, a) = e(1 a) = (h*, ",,,t'",," .²)). Finally, we also define a reference Seeping MDP Ms,o which has the same structure as the SleMDPs defined above, but with Ao s,, a) = 0. The rewards are defined as:
R(s, a h) 1(s sg. H d 1),Ya A.
Regret of an algorithm 21 in MMs,h+. +)- Following the same reasoning as in (Domingues et al., 2021), it is clear to see that the learner is required to learn the optimal trajectory, which enables it to play action a* in leaf node Sę at stage h². However, this trajectory is only achievable with probability c, due to the availability of action a* in node 81x Notice that, the optimal trajectory not available an episode, then the learner does not incur in any regret, as neither the agent nor the optimal policy can achieve it. We now follow the proof of Th. of (Domingues al., 2021), adapting to the Sleeping MDP setting. We report only the relevant modifications. Let Sk,b and Ag, be the random variables that represent, respectively, the state occupied and the action selected at stage h of episode k. We start by observing that the average reward gathered by an algorithm 21 is again defined as:
K
H
K
F _ ,,*)
Σ
Ak, hi) - -H (H-H- d) R(Sk,
Pr(S = kg)-
k=1
For any stage he E [1 + d, H + +d] we can rewrite Eq. (7) of (Domingues et al., 2021) as:
Pr (Sk 8z)
Pr (sk.h (h* ,0*)
(g)
Pr (Sk, L)+ (1* 19,4)
1h
Pr
(St. spt, Ak, a aa Ak.h))
(hH,18 .a+)
Pr
(Sk. = 8g) +
Pr (1.,18,a*)
(Sk, L)+
(13 f (a,))
15

---

Sleeping Reinforcement Learning
1 Pr (Sk. S/0, st Ak, a²),
(8)
c
(1+ (1*,1*,0*))
where (8) is obtained by applying Bayes' rule and observing that 1a Acc,lSKKh Ak,h a²) = Following the proof, we obtain that the optimal value any the SleMDPs is p² = (H d(1/2 + e))/c. We can then rewrite the suffered regret as:
(1-
1 K
(2( = K(H - -H - -2- d)E
(1-
E Ees, |
where (1, Σx 11SK, sp4, A aa E A Observe that:
K
1
K 1000,
Bi [+ [11 314, Ak, = a*1a* e AR
=
K
1
Σ
Pr
(Sk sp4, Av, aa1aa & Ak,
K
(h+ .at)
k-1k
1
Pr
(S Sp4, Ak = a²)
K
C (h+,14
a a [N
ck
where (k., .a) is defined as in (Domingues et al., 2021). We can then bound the maximum regret over all possible instances as:
max (2) K(H H -dj (he 1 )
Σ
HLAK
(h#,18 1,*)
H
1
Σ
HLAKe (h+ (8.))
Following the derivation, we finally obtain:
1 HLAc HLAc
V2EV HLAK
(2) K(H H d)e
(h* _ .a*)
Clearly, as appears only at the denominator of negative terms, and e [o, 1] by definition, the value of that maximizes the regret is 1. Intuitively, given a finite number of episodes, and given that the agent does not pay any regret if the optimal trajectory is not available, the case in which the agent can pay the maximum regret that which the optimal trajectory available in every episode, Finally, we conclude proof by plugging in the same optimal values for e and H, obtaining a lower bound of S2 (ST)..
C.2. Proof of Theorem 4.2
Theorem 4.2 (Lower Bound Per-stage Disclosure: Markovian). For any algorithm there exists an instance of Sleeping MDP with per-stage disclosure and Markovian action availability such that, for T ((HSA22)) and H > ((A). the per-stage disclosure policy regret satisfies:
E Rps 21, []] Ω SITVAA))
Proof. We start the proof by describing the instance. The goal of this proof is to show that exponential component in the regret is not avoidable if we consider Markovian action availability and per-stage disclosure.
Construction of the Instances
To build the "hard instances" of SleMDPs we need in order to get the lower bound exponential in the number of actions, we
consider two building blocks, as depicted in Figure In these instances, we consider > + + log S, we consider
16

---

Sleeping Reinforcement Learning
A-ary Tree
(Domingues et al., 2021)
Va +
Fr
11//3344
e3
1/2233/4
11/2/3/4
01/2/3/4
d1/2/3/4
41
42
0.4
Instance used Theorem 4.2
1/2/3/4
11/2/3/4
11//3//4
12/3//4
82
03
6.4
Sleeping Lattice
22/3/4
01/3/4
2//2/4
01/2/3
0.4
83
41
43
92
#3/4
02/4
02/3
01 /4
01/3
G1/2
-
51 +
Figure Instance used the lower bound construction C Mariov with per-stage disclosure.
17

---

Sleeping Reinforcement Learning
the state set to be composed of S states and 3 additional states: Swx st, and s which we will define later. Moreover, we consider the action set be composed by A 2 action, with A even, where have 2 special actions at and a we will define later.
A-ary Tree. The first building block is the tree structure instance proposed by (Domingues et al., 2021), depicted in the grey area in Figure 6. In this structure, we have a starting state 8w from which we have to exit at the proper moment, which is designed to get the proper dependency on the horizon H. Then, we have a A-ary tree structure that we consider in the same way as (Domingues et al., 2021). For this part, we consider that all the actions are available in all the states. Moreover, we consider deterministic transitions. We refer the reader to (Domingues et al., 2021) for further details. This construction gives us lower bound in the order of Ω ( HV/SA SAT) and, given that we consider full action availability, we are in the same scenario as for the original paper, so we avoid to report all the derivation, and we refer the reader to (Domingues et al., 2021, Theorem 9) for the analysis.
Sleeping MDP Lattice. The second building block is a lattice structure to generate the hard instance in terms of Markovian action availability sets. every leaf of the A-ary tree, we add a lattice of depth A/2 designed as follows. We start, as depicted in Figure 6, in a generic leaf state s; where we will have all the actions available to build the lattice. In the example, the available actions are reported next to the state. When we are in the lattice and we make an action ag, such an action will be more available in the next stage, while we remain in the same 8; E S, so the only evolution trigger is deterministic evolution of the available action set B which will become B [a.)- We stop the construction of the lattice when we are in the layer of the lattice with the maximum extension. It is simple to verify that in such a layer, we have = A different availability combinations. Then, at step 2 + 1 in the lattice, we have that the different instances become distinguishable, and we will have an action set i* e [m] which is the optimal one. We call m,s the instance in which j is the optimum. Now, if we are in the optimal action availability set, we have probability 1/2 + E remain in 8 and have the chance of playing action E to remain in 8; and having available only action a=. Then, if we play a in 8; in the proper stage h E [H]]. we get reward I; otherwise we get O. if E [n]], i * 1 we have the same probability of going to good and bad action set, i.e., 2-
at, and we have probability
Given that, an instance is characterized by a tuple (s*, h", ,B*). While the first 3 terms are the same of (Domingues et al., 2021),, the last term is the optimal available action set, i.e., the one allowing us, if properly triggered, to play a + and get reward 1. 8 is the set corresponding to j* E [n]]
Analysis
Given that we already know the result of the first building block (i.e., the A-ary tree), we dedicate our efforts to getting the exponential dependency on A, then combining the results together just requires some straightforward algebra.
Fix i* e [n]. We call (K) the number of times we observed i over K episodes. We define i e [r]]] the ones such that:
arg min Er [N:( ie[n]|[(+)
Given that, since we are in a loop-free structure, we know that:
Emg [N{(K]] < K,
ie (e]])
for the so-called "averaging hammer" we have:
K n n
E Em [N-- (K)
&
We now consider instance mi-, which is defined similarly to i but this time the best available action set, i.e., the one with a probability of activating at equal to + 2s, is We highlight that in this instance we have multiplicative term 2 before
We can now compute the regret and optimize the value of e. We use the notation (m(m) to indicate the regret after T interactions on instance m:
1
max (Rr()))) (r }} }}>}
(Rr(m)+) + Rr(mm-)))
AK
Pr
(x)(K)
&
K) K)
)
+ Pr
(K)(K)
K K) >
2 ))
4
m
2
m,
18

---

Sleeping Reinforcement Learning
AK
exp
E
[N,(
DKI. [ + 28, =+t))
(9)
8
m,
AK
K
exp
(10)
where A is the value function we will compute later, line (9) the Bretagnolle Huuber inequality (see Lattimore Szepesvári, 2020, Theorem 14.2), and line (10) holds for sufficiently small e.
We can now compute A:
V
ma*
+
E
1 +
2 - 8
0 = e
V*
28
11
2E
0
2
m,
we have A
Now we have to choose and we choose
V K
and we get:
EK
( Ks²
max (Rr(m,)); Re(m)-))
exp
8
12 12-1
-
v [((n-1)
Ω v K2A/2
where the last inequality is derived after having observed that:
A
A
>> 2//2
n =
A/2
A/2
Now, applying the same reasoning as (Domingues et al., 2021) we can retrieve the multiplicative factor Ω leading to bound in the order of Q [HV (HVSAT24/2) ) This concludes the proof.
D. Proof of Theorem 5.2
In this appendix, provide the formal proof of Theorem 5.2. The proof follows the of (Azar et al., 2017, Theorem 2) and as such, some of the original lemmas which are used as is are reported to increase the readability of the proof.
D.1. Notation
We now collect the notation necessary for the understanding of the proof of Theorem 5.2.
Symbol
Meaning
State space
A
Action space
P C R H
Transition distribution
Action set availability distribution
Reward function
Length of the episode
K
Total number of episodes
Total number of steps
T
Total number of steps up to episode i
S
Cardinality of the state space
A
Cardinality of the action space
19

---

Sleeping Reinforcement Learning
Sk, xz(B)
State occupied at stage hi of episode k
Action played at stage of episode &o under policy Te with action set available
N)(s,a)
Number visits to state-action pair (s, a) up to episode k
Na(8,a,8')
Number of transitions to state s' from state after playing action a, up to episode k
NE,h(s)
Number of visits state 8 at stage h up to episode k
NN,A(5,0) a)
Number of visits state-action pair (s, a) at stage up episode kt
Ps
Estimated transition distribution
Estimated action set availability distribution State-action value function exploration bonus min 2900 n 5a A2 v
(+)
H!2)
(x)
State value function exploration bonus
(s)
min s" 12
113}
Ny (s.,.,,, (1,5))
Tk
Policy played during episode kt
**
Optimal policy
Qf
State-action value function of the optimal policy
Q%
State-action value function following policy π
QuA
Optimistic state-action value function Value function of the optimal policy stage h Value function under policy at stage h
b V
VR
Optimistic estimator of the optimal value function stage of episode k
(K,(s)
Regret in state s, stage h of episode ki following policy my.
(s)))
Pseudo-regret in state 8, at stage h of episode k; following policy Ti.
A (8,
(h(s, - QT (s,a)
(8,00
(u,((s,) - QThh (s,0)
E Pknh
Concentration inequalities event
Optimism event
eV,E" ,V, E" Ee,Ez
Martingale differences sequences Sets of typical episodes
[k]tss [k]yn [tyn.s.
Ha,
History of the interactions up to, and including, stage of episode not including the observed available action set BES
H
History of the interactions up to, and including, stage h of episode k including the observed available action set BR.h
L
Logarithmic term log( S T/2 Logarithmic term log( AT)
G
Next-state variance of V
Next-state variance of V*
Empirical next-state variance of V
Vi
Empirical next-state variance of *** Variance of Q**
Q
Of
Variance of Q*
OLA
Empirical variance of Q Empirical variance of Q*
KEA
Table 2: Table of notation
We now restate the definitions of the Martingale Difference Sequences:
eV,, (PāK (SK, Oghh
(Ba,))))) & (8k,
20

---

Sleeping Reinforcement Learning
K Σ
sa, me(Ba.l)) Skh
11ss E [
AV Ak (s))
(Bain)) P(s' (sk, akah
s'eS
1(SK [s]ann]
(s
P((") akh
E =
Cind(B)sk.N)
Σ
P(s ss Orh
(x(1))
) Akmn1166)
A A (Sk,41))
(AA(A)
6'ES
Σ
(BIssN))
Σ
P(s' ss Rkh (T)1))
115' [s]k,n))
ĀV Aknvi(67)
Ne akhh ( P(s"|sk,h 2x ml(1))
(EP(A)
s'eS
1SSA+1 E [s]k,h] (B
AV. (SE,Nt))
V NE(SK, Ok (cind
P(s'| (k,, kkh
Ta(8))
) (SK.N- Σ2 k.N (5k, Ok.h
xe(Bk.N)
1iBE E [ k
Σ (iIsaN))) (EP(A)
(sk akih ( (B)
( Cind (k.h))
I|BRA E [ (snd (Bn
(sk (B(BB)))
and of the variance terms:
(s, = Var (VTT(ss)), d>P((s))
()(,,))= = Var d-P((ssa)
(V)('')),,
(s, = Var (V),, -PP((()s.))
(s, = Var
(s'),
(x) = Var
10 (s, (s,
(-C((())s)) 8)
(+(s) = Var
[Qh(s, TH B))]
B-C s))
(x))())= = Var
[Qu, ( B)]],
(-
(z)(s)= = Var B- (-()))
1Q%(s, (s, B))]-
For ease of notation, will employ the following notation throughout the appendix. Let F: X A(Y) be a probability distribution over a set Y conditioned to set X. Let P: x AYY be an estimator of F, and let G : X R be real-valued function. Then the define the following notations:
(FG) = Σ F(yl))
yEY
(fF (z) (z) Σ (F(ulz)=F(ylz)) G(a.g). g).
-
yeY
Similarly, let F: X F(Z),F:XX -A))) and G 7 - IR. be defined with the same meaning as above, then
21

---

Sleeping Reinforcement Learning
define the following notations:
(FG) (2, = Σ ([2lx,v)G(2)
2EZ
(F-F)G) (2,0) = Σ
(F(s|z,)) - F(ulz,u) G(z).
2EZ
D.2. High Probability Events
In this section, we state the high probability events 2a and &. For ease of reference, we employ the same notation as (Azar et al., 2017).
Let R be the set of events:
Pk == 2 a (is(s,a) > ()(s,)), V(i,j) e [k. hist. 8 S, A).
for k [K] and h [H], where:
[k. huist ((i,s): :iE : [K].j [H] At) (1 k 1)),
under which optimism holds.
Event & is the event defined as:
E == Ep
Egd n
n
D Fa H, Eua(F (Fa k.h, H, L) n Eaa FV k.h,,aa H, L)
[E[K]
RE[H]
a
asd
(AA)
n EanlFas Av AMN VI L) n EanlF' Ean A.h. VL L) n Fn Arahaa Vi L)
(a N. H, L.) Ene FF H.L) Euz Fa H.
n Fa VT. Ean(F
A.B.'' VT. L) Enel E Fs VT. L)
1
D H. Exel Fa H.
Eaal ( H.L)
DELLF D BRAM VT. L) EnclF FR VT."
1
L) Exe(F) ( AR VT." L)
1
NK... H3 L) n En Th. H L) Et H
n (Gv. H NR. Hº L) n (G H H L)
Et (G H NE H3 L) n Etr Hº NK.n. H L)
n Eaz (FoV H² ...) n Eng Faai Ha, H.I..
n Eaz (Foy. H22 L)n Eag (1?
Enz (Frrnn Ha, (P,D) Eng (Fo9 H1?
22

---

Sleeping Reinforcement Learning
The proof that event & holds with probability least 1 ô directly follows from Lemma of (Azar et al., 2017).
We now state the definitions of the events that compose E. Events Ep and Exu concern the estimation of the transition probability and of the action availability distributions:
Ep = (Po(6lss E P(k, h, a), VK [K], h e [M], 5S Ax S),
Exn (i (B]s) C(k, (&) s, B), vk E [K] h [H]] E S, P(A)).
p(k, n, a, s') is the subset of the set of all transition probability distributions Z such that:
SL P() E (P:1)((1,,a) P(-bs,)) & 2
n,,,,,,
(11)
n
Σ SEES
P(5)
2 (3,
7HL
24 (s,
1 L
2HL
& min
+
3(n - 1)'
3n
(12)
- &
P()'ss,a) a()lls,
25''' a) - s(
2L
(13)
n
3n
and C(k. h, NN((s), s, B3 the subset of all the action availability distributions e such that:
Erid (118) E C: (-Iss Crind (-1s)11 =22 2
(14)
Σ (AP(A)
(Gind (Bis))B)s) Crind (B)ss) a (B))
20 (8)
7HL
(0) 2HL
& min
3(n 1
(15)
3n
Eiidd (B]s) - Cind (B|s)
2nind (B)
(ind((3) (B}s))
2T
(16)
n
3n
where Eq, (11) and Eq. (14) follows by applying Lemma 2.1 of (Weissman et al., 2003), Eq. (12) and Eq. (15) follows by applying both the Bernstein inequality (see, e.g., Cesa-Bianchh & Lugosi, 2006) and the Empirical Bernstein inequality (Maurer & Pontil, 2009), and Eq. (13) and Eq. (16) derive from the application of the Bernstein inequality for Bernoulli random variables.
The remaining events concern the summation of Martingale difference sequences. For ease of reading, let us introduce the following shorthand notation:
Ig := 119iih 5}, T := Issih 8, a,a
(B,.)) a),
where ll represents the indicator function.
23

---

Sleeping Reinforcement Learning
k H-1 Fa H,L)= ==)=
H-1
Σ
Σ
( 4i (B))))))
Σ Σ
A
& 2 k(H - HL
k
H-1
H-1
Fa BV s. H.L)= :-
(BBB))))
T, Σ
A
Ag+i (81++1)
Ozd
j-h
j-h
< v (o) h)
A
H-1
H-1
Exe(F M.h.e H.L)= ==
Issa
(P (H
Σ
I,,a
Σ
AY (
j=h
< 2 (H
Exe Av ' vL
1
L) ==
k H-1
Σ
P(s'|st.s on (BB))))
(.(Baa) P( P(ol18ess ais (g. (.(B,))) Ay (
110' E [t]cc]
No(Si.j Hzs
j=h e'ES
H-1
Σ Σ
A (851(()))11)
( (B.s)
(B.))) ) P(sifti Rig
(,(B,s))
=1 j=h
< 2v <2/k( 2/H -1) h1)
Exel Av '. VI L) ==
1
Σ
k
11g Σ
H
Σ
P(s/|sss. ..
1155 [8]
=:(1B..)) AV (k't)(s
Ne(8i,; 4i
(B..)))) P(s P(s'(015 Oi.
j-h
SEES s'E
1 H-1
18i.+11 E [lig))
AV (1t1((11+11
Ne(Sas (.08.))
P(sistiloug 0,
$ 2 NH m
Ear(Fas h.saa VI" L) :=
1
Σ
k
111
Σ
Σ
(.(B,a)) 18.5 and
I| E [s]ast
AV (6)))(66 x,(,,))) (1542(11541)
Ni Ou. P(sl(sa. 9is
(B(B..))
j-h S'ES
111
1[ E [s]en]
Σ Le,
Σ
V (:(B1s))
V
Ni(sis:
(B.))))
P(s 11 ai,
j-h
$ 2 (H - -m)
k #-1
Ex k H.L)= :=
Σ (i)(()))))))
Σ P(o' (.) ( "..
(EP(A)
xts
Σ (
< 22 1H)
24

---

Sleeping Reinforcement Learning
k
H
EsalFav A...B..... H) ==
11
Crind (B)sts))
Σ
P(dliss.. (1(00) )0 (()))
2 h (EP(A)
6'E8
H- 1
1
$ v NEA -H)
(F BV A.K.BBB...a H, ==
Σ
Σ
(B)(
Σ
P(olloss
(1(1)) ) (1)2((0
i-1
j-h h (EP(AA
R18
Is.0
Σ
(
j=h
< 2 NEM( - h)H
-
Ese (Fa Ar VL
L) L)=
1
Σ
4: H-1
Σ
E3 (idded
11s E [5],s]
N Mi(s...
T.
) P(s)|sh.) o,. (1))
jーh
s'
H-1
1ss,+11 E [slast
Σ
Σ
AV
No($1)) (B) P(s 18g a.5 (1))))
j-h
2v k(H hh)
Ene '. VL
1
T.)
Σ
4:
T
H-1
Σ
E
B B-C
VV No(O a.j
BB P( P(8'|5,,. anj (1)181) A (o0+1(00)
If E [s]cst
j-h
d'
11 E
[8] [s]
Av (3541)))11)
Ne(sa.s R2j
(B))
J-h
$ 2 Ne. (s) - h)
1
I.) :=
Σ
4
Tssa
H-1
Σ E
1 E [1]cn)
Ay. (8))
VL
LV Ni(5n.). (81) P(d' a.
(B)
j-h
H-1
19 [s]
Ni(sis, (.(B)
P(s 0,3 01((8)
a-h
$ 2 (s) - m).
#-1
k H-1
Eacl FaulFaR :-
Σ Σ (Cind (2
Σ
Σ A (si.
and
(B..)))
s=1
< 22 WVH((-h)HH2)
k
n-
k
H-1
Eae(Fi0 H.L) ==
Σ
1
Σ
(ind [ (SL5) ( -
Σ
1 Σ A ($i.5
(515, (55 x((Baa))
b=h
1=1
j=h
25

---

Sleeping Reinforcement Learning
< 2/
-
k
H-1
H-1 1
EmalF Fn H.L)= ==
Σ
Js,a
Σ
iidd (
Σ
3 by
j-h
j-h
$ 2 (N) - H)H
FullFaa vT.
1
L)
A H-1
Cind (i)(())))))
( (B)ss)) A 1 (1110)
T E [B]b]]
j=h (AP
#-1
Cind) Crind (s.,, (1,())))))
IBBL [Bkb)
22 k(11 -h) h)
ExelF Ex Bu.kh,s'
1
L) ==
Σ
1. Σ
H-1
Σ
Crind (ind(B1ssss) (BIssa))
IiBE E [5 b3g
Aog (S6.) Di,5 (8,2) (1)
VL
Ni(si.) Cind (B(sis)
j-h h (EA(A)
IlBLJ E [B]
A9, (86.) 0z,5 (B,())))))
N (B (1st,)
< 2 Nen(s)(H- h))
1 EF Aa vL.
L) =
Is,a
H-1
Σ
Σ
Clnd (i((s)))))))
IIBE E [B b
A (B1.5, (8))
) ind (ind(B(s.))
j=h P(A(
H-1
IBB E [Bir
N((sis) Cind (B]skd) (B,( aij (7.(BB.)))
< 2/ (E,( -H) h))
(G HT H L) ==
E
j+l (5h.5) Ujj
(B. (1m)))))
Σ
V (
R,j
(..B..)
$ 2 H.T.L + 4 H
k
Ø-1
k
H 1-1
Etr (Gv..,n HD No, H HDD)= ==
T
Va, j+z (Bi
5, (.(B8.))) Hlin
T
(8i.) 023 (BBa))
jt
j-h
< 2 HoN
+ 3 H
k
H-1
H-1
EG H NE,, HJ, I.D) =
L
E
Σ (ist
(B 17r.h
I Σ
w
(
j-h
4 3 11P2
< 2 HHNN.b(s,0)) a)
26

---

Sleeping Reinforcement Learning
k
R (8he)) Hihh
Cn Th, 11, .)) ==
E
Σ
h
4 2 HAT
+
k
H-1
(G H. Ne,,, H H)L)= ==
LE
Σ
17 (o1))1
Σ
I. Σ
Q
(81.)
$ 2
H Ne + H
3
k
H-1
H-1
Etr Et H NE,,, H&A, L.) :=
Σ
T E
(815))
Σ a
Σ (sig)
j-h
1 1
2
H (s. a) +
3
A H-1
k H 1
Eax F
H 1) ==
Σ Σ
pD 2 (Sags
Rid (B
5 (BLJ+1))
j=
- < 2 -VKKHH-hiHH h)HH
k
H
k
H-1
Eae (Fr.nos H) ==
Ig
(P52 (5 (B)B))))
ais
- Σ 11, Σ
6
($1)+1)
J=h
1=1
< 2 -
111
1 Σ
Exe (n ==
Σ (Pb
(iBB (sss) oj
Loa
b (313+1)
j-ht
j=h
$ 2 (H - - -
k H-1
k H-1
Ere
=
Σ Σ (CT' (oWr))
Σ
Σ
Dy
( (55 (,,0
< 2 kcHH-
k
H-1
h:
H-1
Eax (Fo...no:.PP.
H2 2.) ;=
Σ T, Σ 10 (ois)
Σ
Σ
(8 Rij
(((Bis))
j-h
1-1
j-h
E 2 (H - h)HA4
H-1
*
H H-1
Eae (Fr'nhaa:Hf H..L) =
I Is,a
Σ (Cb" ((L))
>
Isaa
byd
(sij.
(BBB))))
5=h
5=h
< / (HH
27

---

Sleeping Reinforcement Learning
The choice of L derives from union bound over the 40 events, for every episode k e [K], stage h [M] state e S, action a A, and action subset B P(AA), noting that each event holds with at least probability 1 6.
D.3. Technical Lemmas
Lemma D.I (Regret decomposition upper bound A Let k E [K] and h [H]] Assume events & and Sg.h hold. Then, the regret from stage h onward of all episodes up k. in terms of state value function, can be upper bounded follows:
Y. $
A (8i..)
H-1
2
(81 + -BB (1)
(1(B))] ]
H by (s a.(Bi.))
+ < + H HeV + V2LE. v +
1
V2L zV + 22
HI
1.
i.j
(SL.), 43 T.(B)) [|
H - ((v--P)13+t) (sL,,
aij (1(B1a))
+ (B-cid((3ss))
8H2ST.
8HST.
+ (BBoC
+ 3N.(s 0i (B.))))))
3Ni(8i.j:
x.(B))
2
L
2Q (8i
2HL
Ni((1s)
3N(()
+1
3N((815)
Proof. Considering single value of ke E [K]. we first observe that, under 2k.k:
(Ka,))))) (*k.N) - V/ (sx,a)
< (en(s V (sk
As such, we can then bound the pseudo-regret AY (sk.
YV (SE.A) = (s,.)) - VT (sk,b)
(sk,)))))) (Gird (skWh) -Crind (sk,t)
(K ((Cind cind (inn)Quih)) (SK.N) +B 12, (8k,h ak
(a)
+ EB-Cod( (PaPettt)) (Sk,n, (T((8)) (PV (SK akh ( TT(13)
=(a) by (sk.h) EBB (o 4 (1))]
+ -EB.Cw(()aa)) ((Ps pP) (SH ak xB) )
AK [k
+ E
B (-( s' P(lenaa (0()))
=(a) + bbb EB-crd((laa))) bb agh
TT(
E
((lee,) a/> (2)
AV (K
+ (BB.Cm((eaa))
28

---

Sleeping Reinforcement Learning
+ EBd [ - P)(Vnnt1 Vitta) (sk,h: kghh
= =aa) ok (skan) EB-crortlsn (sk.n aas (x(81)] + A (8k
+ SKA + BBmcem((eenN) [ -P)V (111) ( akkh ax )
+ EB (PA P)(Vn,+1 - (Sk, OR ==(1))
(17)
(6)
We now bound term (b) following the procedure of (Azar et al., 2017, Lemma 3), obtaining the following bound:
(b) V2LEE v 1
+ A ( + (B-CC")))ss))))
SH
(.N KK,h
(B)
To bound term (a) we first derive that:
(a) ((0ige (iind) (iid)) (sk,h)
Ciid (iid))(Q..n -0++) (sk.h) ((Oked (iind (sk
( (s(sk,))
2HL
(c) +c)+V
(18)
(Nk,)),))
where Eq. (18) obtained by applying Bernstein's inequality. We now bound term (c):
(c) Σ
(cind (Bid((B)ss.)) Cind (13) (s...)
(T)))
k.N
(AP(A)
Σ
2Cind sk.h)(1 Cind (8..))))
2L
Q A ax
(19)
(a(5k,))
(sk.h)
(AP(A)
(B))
2L
IQ AQ (R. (2((1)
Nu(su,h)
(AP
Cind
2H2 + 3NN(sk.
2L
(1( k. (sk,h, ag
(20)
Na(SH,h)
(EP(A)
(d)
where Eq. (19) is obtained by applying Bernstein's inequality for Bernoulli Random Variables, and Eq. (20) follows by upper bounding Ag, (sR,6, ag,h (B)) with H. Let kB] {B P(4)) Cind > LJ. To bound term (d), we first rewrite it as:
(B)d(B)) T
(i)d(B)
(d)
Σ [e[B))a.
No(Sk.)
k. (SK,,h, deh
Tv(B)
Σ
Ne(5k,))
TL(B) k. (sk,h,
aghh
(21)
By (8)ah
(e)
29

---

Sleeping Reinforcement Learning
can then bound term (f) as:
v A Blsk.h)
Σ
R.N (8k, 4k
(8)
B
H22AV2L
Na(ou,))
by applying the condition of k. and term (e) as:
(Bi sk.h)
(e)
Σ
(SK, 02 ( (1)
(a(OK.))
k.N
BE|BIE,A
IBB E [K (BOEAllNN)
3 (s akh (B(B),
V
(22)
Q K.A
A R.N (Sk Ta(BkN)))
(23)
2H2
where Eq. (22) is obtained by applying the definition of Q k.h. Eq. (23) follows from the definition of [B] Plugging the bounds of terms (e) and (f) into Eq. (21), get:
1122A/2L
(d) E kk.
1 k.A (5R, aksh
(e(Ba.))
V2H2L
N1((KE,))
We can then bound Q k.
(Sk.
(BB,.)))) Rkh
as in Lemma 3 of (Azar et al., 2017) and plug the bound of term (d) into Eq. (20),
thus obtaining:
(c) & V2LER +
H 1 b (sk OK
TA(BENN)
1
1
k 1 (SK,N+1)
AV
H
1
+ H ( PIVitt))) (KR,A, (e(Baa))
1
+
V
+
V22 v
kk
H
H
SHSL
(B((B + 2/122AL Na(SK.))
2H2AL
( ag. AgA
3.
Finally, putting together, the bounds of terms (a), (b), and (c), and plugging them into Eq. (17), we obtain:
(K & bY (sk.h) + BB--Ci sm. 16 (Sk,A, 4kh
(B( 11+ +
1
(Sk.h, (sk,n, ak,h
(B((B,)))
H
1 +
2
A (K + EKn +
H c/h
1
H
H
V2T.
2L +
Ekhn 22L
H
(B-CC(()))))
-PVVEt))
(Sk Cg
(L(8)))
1
( P)Vittt)
(Sk dk.h
H
8H2ST.
8HSL.
(N aghh (B))
3N Ok (Bu.)))
30

---

Sleeping Reinforcement Learning
2H22AL
2
(skA))
2HL (NN()),))
(a(
3NN(SE,A)
Na((R,n)
By applying the same inductive argument of (Azar al., 2017, Lemma 3), we can isolate the term E.A. and rewrite:
H-1 & o²
(kskh) Σ
by (Kg() + (B- 12, (8k.j. 0k,) [1(l11]] +
2 "s
1
(Bes))
H
j-h
V2L
+ Sn + Heka + V21EE, +
kdd + V2L
k.j
H
(PNV-)))) (SH.) akd
TT(1)) )
1
( - P))
+ (
H
8H2SL
8HSL
+ (BB.om((H1
+ (N Kki
3Na(Ok.
(B)
(1x.)))))
OK.
+ 2H22AL
L
0077(19.33 Nu(sk))
2HL
(24)
Na(sk.))
(.k)))k.)
3.Nx)
observing that our multiplicative constant e² instead of due to the (1 2/H + 1/H²) coefficient of the recursive term. Finally, recalling the definition of Og.h:
PEAh == (V > ())())>))())))))))))))))) A (i)(s,
> (s),,)), v(i,j) e [ke, hhin. SE SE S, A].
where [k, htlnstt == {(i,5) : E [K].jE [H] (i < k) v (i= k,j j > h)}, we observe that Ωu holds then also the events Dr for (i.j) e [kr, hisst hold. As such, we can sum up the bound of Eq. (24) over all the episodes [*:]. thus concluding the proof.
Lemma D.2 (Regret decomposition upper bound 2 Let E [K] and h [H] Assume events E and S2.h hold. Then, the regret from stage onward of all episodes up to k in terms of state-action value function, can be upper bounded as follows:
A
R. (8i (i
(B,.a)) Oih
Q (si, LiA
(((B)aa)
(1+
1 ((0-1(81511)
+ VeLeY, + eY.s + 1 H Eis+1
+ (Ip: -P)V)++))))) (Ni.j. Aid (B.())))
8H2SL
+ (1+
2
2H1
N((sis 0,3 (Bs))
H
No(011+1)
Proof. Considering a single value of e [K], we first observe that, under sk
(i, ag
(e(Baa)
Q (Sk,bs (alBeeh)) (Sk (sk, ann The ne(Be.h))
< (n. SQ ((B.n)))) Q% (sk, aghh
(Bma))
31

---

Sleeping Reinforcement Learning 2 (sk Ok
(1(8))))
As such, we can bound the pseudo-regret A 2,,, (sk,,, ak. akn
Tu(Be,n))
2x (SkAaa HKih
-R (Sp,n aksh
(Br,))
+ (Px (PaPniatt) (sh ma(Ben)) - (PV (sk,ns 4k (a(Bei))
(b(B),))) + (PPs- (BVAPa) ( (.(Bmm)))
+P(PuatiI - Virtt) (SK,A, RK, (L)B))
b (R, akhh aoh (u(Bmii))) + ((P - PDV(P - Viiti)) (sk (c(BBe))
akib
(P(Vi.nt1 - Vitti) (Sk, au(Be.)) + ((Pa -P)V (suih, 4kd Akd aalBes))
0g (Sk,,, "kh (b(Ba.))) + V2Tek,n + + + (1+ 1
TV. 1
H
8H2SL
(IPe- PIV (Sk, aEh
(25)
Nu (a Rghh (((B)))))
where Eq. (25) is obtained by bounding (Px- - P)(V - V according to the procedure of (Azar et al., 2017, Lemma 3). Observing that:
( (CmrlQunnt)) (sk,ttt) (Cind (sk,h+1)
- ((Oind -Cind Qm.h-) (SK,h1) + (Cind (din(@u,h+11Q - - (skA411)
2 +
Q < vV (S + kkh+1 + 2H
(26)
Na(Sk,n+1)
where Eq. (26) is obtained by applying the definition of 6kh and by bounding (Gimd gind Qiad)Quatt using Thr. 2.1 of (Weissman et al., 2003), then we can rewrite:
ne(Br.na) & (Sk.h, akhh A (Sk,h, akhh
(BaN)) + V2TEK + EY + 8H2ST.
Ne(Kk, 2k,b
((Pa- (P))-))
(SK,h, agh
Tu(Be
[1+
1
1 Q ( (1+
H) k
H
1+
1
2H
2
(1+
32 (88,
(((Baa)))) 0KA+1
H
Ne(sk,tt1)
H
By applying the same inductive argument of (Azar et al., 2017, Lemma 3), we can isolate the term 3o and rewrite:
salBee)) se e
H-1
Σ
(ons)
(a(Bea)) + 1+
1
6% (1
H
1=h
+ V2LEK + +KY + (1+ H Ekj+1
32

---

Sleeping Reinforcement Learning
+ (IPs - P)) (SK.s aka
mu((B..))
SH
1 1+
2
+
2H
(27)
nx (Bail) No
H
NN(sk+++1)
Finally, recalling the definition of 9k,h:
PE = (Vi](s) > (8) A Qiy(s,a) > (s) V(,,)) e [k, Ahia S S, a A).
where [k; heistst == [(i,5) : E [K],je e [i], < k) (i= k.j > h)). we observe that if S4 n holds then also the events R for (i [ks, hiist hold. As such, can sum up the bound of Eq. (27) over all the episodes i [[]]] thus concluding the proof.
Lemma D.3. Let & [K] and h [H]] Let events & and Ok, hold. Then the following bounds hold:
H-1
c/ 2V HTT&L,
H-1
Ch 22 HTTLL
- HTTL
2/3 $ Tr:
En. $ Th:
Σ
1 & Tx.
hーh
(28)
Moreover, for every S E S and a E A, the following bounds also hold:
H-1
188. 8)
Σ
e < 2 (+)
j-h
8-1
HALA 8)
Σ
EY, < 2 H3Neu(s)LL
j-h
&
#-1
Σ 1A = $)
Σ
8.0 < 21 Hz)
j-h
Σ
188A $)
Σ EY, <\ (HNu,As))
j-h
H-1
I(siAA = s) Σ
Σ
Ees & v (H).
j-h
33

---

Sleeping Reinforcement Learning
k
H-1
1/8 = of
Σ
< V HNNk((s)
h
H-1
[[1 9, 0igh
(.(B.,)
a}
Σ
2 HSNuM(s,O)LL
/=h
H-1
1(5t = s, ii
(B,,),
= }}
Σ
<Xg
< 2/ H9NnA(s,a)L,
=
H-1
[[5 s, 0i
T((Ba))
a}
Σ
Q
2 H&Ne,(s,O)L,
j=h
H-1
I[ = 8, 4
(B,.a))
= }
E
$ HN
/=
H-1
[[ 8, a,h
(Bi,))) a}
Σ
St.
(N,,,(s..),
j=h
H-1
Σ
I[si = 8, 4i
(B,,),)) = }}
Σ
Q
$ HN,.A(s.o).
b=h
Proof. The proof follows similar reasoning as that of Lemma 5 of (Azar et al., 2017), observing that under and Skgh the following events hold:
(F AV.KK K. H, Eaz kn. H. H, L), a H, H)L,,
(a Av K. H, L), (n F
R.s. H, L), Eaz(F 3v B.s. H, L),,
Excl (F K H, L), Exg (J H. (F H, L.)
Esd Ex IV &V.K" R.K' VL 1
L), End M, VI L), Ene
AV Av..hha,,' VL L),
1
En B,h,B' VL
L), Ena Fs VL" L), SV vL" L),
A.H.B.s,,a
Ene B9,E VL
L), Ean(F
30.K,b.' VI b), L)) Enl VL L))
L).
Remark D.1. With a slight abuse of notation, but to benefit the ease of reading, we will refer to the following lemmas also for the summations in which the action set not fixed but is taken expectation over Cind, an example, we will refer to Lemma D.4 when upper bounding the summation:
(Sii a (1)1))
Eg Cade (Heag)
(29)
Considering the summations of the random variables that define the events (see Lemma I of Azar et al., 2017) and changing the conditioning from mathcal Hg.h. to Ha.h (i.e,, removing from the history) we see that the quantities in play retain the properties that make them Martingale difference sequences. As such, we can apply the same derivations, obtaining the same bounds.
Lemma D.4 (Lemma 8 of Azar et al. (2017)). Let e [K] and h [H]. Let Fy be the policy followed during episode Under the events & and Dg the following holds for every 8 E S:
34

---

Sleeping Reinforcement Learning
k H
Σ
Vir
j+l (Sig)
0/ (.(BBu)) & HTx + 2 HTTaL+ L
4
3
1
(.(B..o)) & 112 (2, + 2/ (1NN + 4 1112L1 0i
188hh = 8)
Σ
Vit (S
h-h
1-1
M 8, aiAh
(B..))
a}
Σ
0ij (
(
(B,)) & 11 a) + 2 11 (N) + L
Proof. The proof of this Lemma directly derives from the one of Lemma of (Azar al., 2017), observing that under event E, the following events hold:
(Gv HT H², L), (GV. H Nr. H L), E (Gv.R,,.s H$ No, H3, L.,
and by taking the expectation over both the states and the action availabilities. Eq. (43) and Eq. (44) of (Azar et al., 2017) hold under this modified expectation since the cumulative reward is bounded with H.
Lemma D.5 (Lemma 9 of Azar et al. (2017)). Let E [K] and h [H] Let my be the policy followed during episode k. Under the events & and Da the following holds for every (s,a) E A:
- ( Ojj (i(Bis)))
k H-1
< 4v H + 2H
Σ Σ
1=1 j=h
H-1 Σ 118, $)
Σ
1/2 j+1 ( Ojj
(.(B))))
Vitz (8h. Onj (.(BBs)))
h-h
H-1
x 4 (5) 2H Σ T(8ihh = $]
Σ
[Y,((()))
#-1
1(8ih 8, 0i
[((B.t)
a}
Σ
Vitz (S azjj
(((BBs)))
H-1
& W ()) 2H
T(8in = 8, Gih. = a)
(BB...
Σ (sis).
j-h
Proof. The proof directly follows from the proof of Lemma 9 of (Azar et al., 2017), observing that events Ean(F J. H, L), (Fa k.h, H, L), and Ead k.h, H, L) hold under E, and Ua, holds.
Lemma D.6 (Lemma 10 of Azar et al. (2017)). Let k E [K] and h E [H]. Let ni be the policy followed during episode k. Under the events & and St the following holds for every s S:
k 1
(oos+((si) 0, (i(BB1))- - (8i.s aij x.(B.a))
35

---

Sleeping Reinforcement Learning
H Σ Σ
< AHPS + 2H
A (96
A
H-1 Mstn $} Σ
Σ
1 0,. (B)B))))
W (رig] ojj
(,(B)))))
z
H-1
< S HA) + 2H Σ 1f = =s}
Σ 1=h
Ay
8-1
I|sthh 8, (B..),
a}
Σ
(15-1(81s.075 (1(Ba)))) -V (8 (1(B)))))
/=h
H-1
< S HAN 2H
2 1( = 4,6
(B..))
a}
Σ j=h
(1
Proof. The proof directly follows that of Lemma 10 of (Azar et al., 2017), observing that under 2E and &, the following events hold:
&V k.b,,,"" H, L). E Fx (v. k.:: H, E Ean Av k,,, H, E) E BV
Lemma D.7. Let l E [K] and h [H]. Let ma be the policy followed during episode k. Under the events & and Qs the following holds for every E S:
k H-1
Σ
((.)))
HT 2 HTT,L H
3
(NN + 2 HSN 4 H Σ (81s)
188hh
4-1
(B,a) (ALA 8, 4gh
a}
Σ
27 (8ig) & N + 2 HO, H8L 3
Proof. This proof follows derivation similar to that of Lemma 8 of (Azar et al., 2017). Let us first recall the definition of 07 (s,g):
(sis))
Var (-
Qt ($1.1, (1111)
Under event E, the following events hold:
E (G H H Et, NK.n. H)),, and Er CG H NN. H L).
Event Err (9 HT,, H3,,, I.) implies that:
Σ #-1 (StJ)
k
#
ΣΣ
(st.))
+ 2v H - H3.
x((B,s) since there no variance on the reward at stage j. we can then recursively apply the Law of Total Variance (see e.g., Thr. 9.5.5 of Blitzstein Hwang, 2019) as done in (Azar al., 2017, Eq. 26) to obtain the following bound:
Observing that, conditioned to Ha 2 W ( L.j
36

---

Sleeping Reinforcement Learning
H-1
H=1 Σ Li-h++
Σ
E
Σ
Th (si
(Hah)
Ha,n
Var (et. bea))
R (sisi aij (sisi (((l))))
HT..
Putting everything together, we obtain the following bound:
H-1 29t (st)) & HT& + 2x H + L
ΣΣ
In a similar manner, from events Ensl (F (an k. H, L) and Fan(F29 H, H) we can derive the bounds for the two remaining summations, thus concluding the proof.
Lemma D.S. Let le E [K] and h E [H] Let Thk be the policy followed during episode k. Under the events & and Sk the following holds for every 8 S:
k H-1
SP 4H*
H-1
H
+ 2H
Σ
8 (5 (1 + 2H
(:(B:,))
Σ Σ
(
j=h
k
#-1
Σ
Issihh = $)
Σ
(1.())))) (81s)
V15S24 NH. + 7v AN SLG
H-1
2H
Ifsi. = s}
Σ
b (s15, (1135)
(..))))
j=h
#-1
+ 2H
I(si, = 8)
Σ
A ($a.ftt)))
j=h
H-1 Σ
1181. 5,
(Bin)) = a}
( (5.s)
v H2 Ne. - (N) 4 SIG
H-1
+ 2H Σ Ifssi, = s, s,
(.BB..))
a}
Σ
b
b.j
si.j.
Ozj
(B.sss))
j=h
H-1
2H
> I(siih s, a,a, (B....))
a}
Σ
A
(
j=h
Proof. We first provide an upper bound to (.,(().)) - Q99 (8i5), and we then bound its summation over episodes and stages.
@us(Sis) (si))
(pd [ (1)
E Oyd
[ (Sis (S55,
". (B) 1
EB (B) [0: (SLg, 4
7: [8))3]
+ Egg (m(lee)))))))) [07 (8i,), (B))) }]
37

---

Sleeping Reinforcement Learning
& Eg B- (1o())))))
(s
935 2
( Oij
Q (B..) (8))
2
2 (BE 4ij 1- (88)
(Bo )
(30)
( (1
EBd
2 ($1.5 and
(1)))
+ (BB.cd((((s)))
Qio 4n
(8)1))
E BB-cnd(
Q7 (Ri. 4.j
(1
+ +HH ((Crnd- - -2, ($1.)
Oz (1)
aid (3))))
< EB BB- (145))))
- 33
+ BBB-o (iss( (0)) - EB (
H 4H (i(ss.))
(31)
where Eq. (30) follows from observing that, under Sag Qr, > 03 > Q7, ES A, and Eq. (31) is obtained via Hoeffding's 's inequality. Putting this bound in the double summation, we get:
k H-1
H-1 Σ
ΣΣ Q
(BB-
[ 0i. (1)1)
Eg-c ( and (1))))
(a)
EB (B- [Oas Cie (1)6)) - 10,0-0755.00 ($i.j U3 (81,),0755 (31))))1)
h
4H H (((s)))
(32)
(e)
We can bound term (a) with H² / S2^T;L by bounding Qi, with H and applying Thr. 2.1 of (Weissman et al., 2003), and term (c) with SLG by applying a pigeonhole argument. We now bound term (b) as follows:
& H (b) =
indd (Blss))) ((Qis(t ais (.(1)) + (81.j aij x. (11 (iiss - -2, (.y (.(1))))
i=1 j h (AP(
H 1
< 2H Σ Σ
Σ
Gind (B) (is) o.. (1( - 27 (8L.j: 0, ( (1)
j-h BEP(A)
1-1
H-1
< 2H Σ Σ
2H
Σ
Σ
(
(Sigs oi
(.((Baa))
i=1
j
+ 2H
Σ Σ
E
d 7,8,)) (es41(5')- BB BB (( v27)(69))
p(
2H Σ Æ-1
#-1
H-1
C 2/1
Σ
( 0
(B.o)))
+ 2H
Σ ΣΣ + 2H
Σ
Ay
38

---

Sleeping Reinforcement Learning
+ -1112
Σ
[PP(-||a.j Oij
x.(B..))) (.(B,,))) P((-|86.)) O4,
(33)
k H
J H
< V + 2H
Σ
b Σ
0i3 (B(B H1S A AII. + 2H (s.)
Σ
A
i ( (34)
where Eq. (33) is obtained by adding and subtracting 2H E Σラー (PVis ( (1) (st.)
(B()))))) and
Ris
2/1 Σ - Y (5++((11+4))) and Eq. (34) is obtained since event en FF HI, L) holds under &. Plugging the bounds of terms (a). (b), and (c) into Eq. (32), we finally obtain:
#-1
k H-1
Σ
( & S2A/T2 + 2112 TTL + 2H
Σ
1g (51.) ai
aig
(B.1)))
sー
+ 11S ATL 4H2 TTL + 2H
Σ
Σ
A
1.jt (
SLG
f=h
h R-1
< /22 S2^TTL + AT&L+ + 2H
Σ
Σ
6
(5
(5i.
(1(BBs))
+ 2H Σ
A V i (81 + SLG
In a similar manner, and observing that events Eaz (a (F kk, H, L) and (Fa H, hold under E, we can derive the bounds to the remaining summations, thus concluding the proof.
Lemma D.9 (Summation over typical episodes of state-action wise model errors, see Lemma 11 of Azar et al. (2017)), Let k e [K] and e [H]. Let ne be the policy followed during episode Under events & and Dg the following inequalities hold for every (8, (5,a) E S x A:
H-1 > (PP (P:-PP)i+T)) (5
Ii [k]tpp}
==h
k H-1
$ VOHSATLI 3
HSALG + 2, HSALG
Σ
Σ
AV
(815), (35)
bi
j=h
11-1
Σ Ile [kleyp,e, Si,1 =
Σ (P.- (s [((Baa))
(H) + HSALG
3
H-1
HSALG V I1si = =s Σ (Y,ss)))
+
5=h
H-1 o}
Ifi [k]eyp.e.a: Sihb = 0, (B..))
Σ ( (P,-P));H1) (S1.), =((B..))
j-h
2 HSALG 3
< v @HP'SNNA
39

---

Sleeping Reinforcement Learning
1-1
+ +2
HSALG Σ
1isth = 4,,4
(B,,),))))
Ayg(s1g).
z=h
where:
kkypp == E [k]] (8i,hr Oih
(.(B.aa) E [[8, Ja, is 11600// A2 L2G, [m]]
[k] [yypp = E [A]] (St,h
(B.a)))
E aks (s) > 11600 S A2" L'G, wh E [H]].
4
x.(B.aa) [llypssa := e [A]] (8i,h 4ih
E [(8,a)} (s, > 11600 A2 G, vh [M]]
[(8, a))a == ((8,a) E A: Na(,,a) > H, (.,( > H, e [H]].
Proof. We adapt the proof of (Azar et al., 2017, Lemma 11). We begin by demonstrating the bound of Eq. (35);
H-1
Ifie e [klppp
Σ
(P. - P)V}t) (SE.,
aij (su)) (B))))
/=h
H-1
2V8 (Bi Ogj
2HL
lii E [kyppp}
Σ
(36)
Ni(8i.j, Oid
(.(8,1))
3N Uz
(B..))
V2L
H-1
Ve ( Aij
T:(Brs)
T(i E [bypp)
1-1
Σ
2
HSALG, (37)
N1(8i,,, aij
(B())))
(a)
where Eq. (36) follows from the application of Bernstein's 's inequality and Eq. (37) follows from the application of Cauchy- Schwarz's ' inequality together with pigeonhole argument.
Using another pigeonhole argument, we can bound term (b) with SAG. By adding and subtracting V (8i. a.j term (a), we rewrite it as:
x.(B..))
Æ-1 V J+1 (8t.)
H
(a)
Fnd
(((Bo)))
Vi+
(((B)))) - (8ig) 4i3
0i ( (BL)))
(d)
As events and Danh hold, we can apply Lemma D.4 and Lemma D.5 to bound terms (c) and (d), respectively, thus obtaining:
H-1
(a) & HT + 6v 6. HTT,L +
4 H + 2H
Σ Σ AY
1 5ー
k H-1
3HT + 2H
Σ Σ (8,g))
(38)
where Eq. (38) holds under the condition of (yp Plugging the bounds of terms (a) and (b) into Eq. (37), rearranging the terms, and applying the subadditivity of the square root, we finally get:
40

---

Sleeping Reinforcement Learning
8-1 Σ Mii e [k]mnd Σ (B--)) (01.) Oij (y(Bu)))
2
VGHSATLLG HSALG
Ø-1 Σ Σ (s.g))))
+ HSALG
=1
In similar manner, can demonstrate the bound the remaining summations, thus concluding the proof.
Lemma D.10 (Summation over typical episodes of state-action value function bonus term). Let E [K] and [H]] Th be the policy followed during episode k. Let the UCB bonus for the stale-action value function be defined as:
Let
4L Var s ( [ [En+1167]]
7HL 3(N
62, (8.
(s(
1)
4 s' P2(1 [min|
10 H2]]
1()))(0))
Na(s,
Under the events & and Dg the following inequalities hold for every (
H-1
Mii [kbppp
Σ
b (51g.
I 22 1 !ISALG+ 5 5000
H-1 SHSALG Σ
Σ (
1=
111
Σ lli [k]eyp.e: 81,1 8LA = 8)
Σ
1 (01,,, a.j
(.((B.))
28H ~ HSALG + 5800 L
H-1
SHSALG Σ 11s. = 3) Σ
AV
(
b=h
8-1
E [k]typ.e, 91,b = 3, = a}
(B..))))
Σ
big ($t.j, dij
(.(B))))
j-h
v
HSALG + 5800v A L
3
SHSALG Σ 11ssh s, 0,
m.(B.,)) a} Σ
(
b=
where:
[k == i [k]] (8i,h; aih
(((Baa)) E ((8,a)]a+ 11600H1 A2 G, [m]]

---

Sleeping Reinforcement Learning
(..B))) E [(s, Na.(s) > 11600 A2 wh [m1]. Kkyyp = E [A]] (St,t ai
Kklyp,s,a = i [K]] (Sa,t Oih
(.(B.a) [(s, (s,a) > 11600 A2 L3, vh [4]]
[(8,a]]: := ((8, a) E S x A: (a(s,a) > H. NE,(s) > H, [H]].
Proof. The proof of this lemma closely follows that of (Azar et al., 2017, Lem. 12). We can rewrite the summation as:
Σ Ifd E [k]] kyp
H-1
Σ
o ($r...
Oij
(((Brs))
I[ E [1] typ
H-1
4L Var
P.(o,,,,,
(1(5 (4) (1(B,,))
7,(8,,)
100na,,,,, [
5
(a)
7HL
Mi E [kpppt
T: (B:.))))
3 [2 si (gd
1)
5,0 Do Disti(s) Dis
k
H-1
4E
8' Pulillas.
+
T(i E [1] [klypp]
(39)
No(8i.j 01.3
(B(.))))
where (s") min 2900 11 3 12 (6))
H2). First of all, we bound term (b) with 3 HSALG by applying pigeonhole argument. To bound term (a), we apply Cauchy-Schwarg inequality to obtain:
1
H
(a) & VLL
(BBs)))) V Vig- (86.) Ozd
lii E [kyp))
(40)
(B..))
(1 Ui
i=1 h
(d)
(e)
By applying pigeonhole argument, we bound term (e) with SAG, and we rewrite term (d) as follows:
H
(d)
Σ
(
(B:()))
Σ
(iisi1lsssa dij
milB.s)) - V 44i (si5, (. (B.)))
(8)
By applying Lemma D.4 and Lemma D.6 to bound terms (f) and (g), respectively, we obtain the following bound:
(d) & HTg + 2. H +
4 T 2H
Σ
Ay bijt
(81g41))
jーh
k H-1
& 4HT, + 2H
Σ Σ
AV
(41)
where Eq. (41) holds under the condition of [k]ppp Combining the bounds terms (d) and (e) into Eq. (40) and applying the subadditivity of the square root, we obtain:
42

---

Sleeping Reinforcement Learning
H-1 (a) LIGHSAT,L + SHSALG Σ Σ (
To bound term (c), we first apply Schwarz's inequality, obtaining:
H-1
(c) 2
2
Σ
E
Σ Tie [k)tpp]
Σ
(42)
N (1 Lijj
(B(B))))
j-h
Similar to term (e), we bound term (1) with SAG. To bound term (h), we first rewrite it as:
H-1
(h) = Σ
Σ
(Pbbist) (BL.) 4i3
(BBs)))))
1=1 カー
H
Σ
Σ
(P:: P)bistt) (Sh. Oisj
(B
(obstt) (siji Ozg (.(Br.s))
(5)
(5) +
Σ Σ
((
(Pbh)=1)
(Si,, Oi
(((B.o))
(81g+1)
b ($
(43)
1=1 j=h
T By bounding +ij+1 with 2 and combining the application of (Weissman et al., 2003, Theorem 2.1) and of a pigeonhole argument, we can upper bound term (j) as:
H2S AT&L.
To bound term (k), we first observe that it is Martingale difference sequence, and such we can bound via the event Eaz (Fr9 H2, H2,L), L.). which holds under E, thus obtaining:
(k) < VTLL
By applying the definition of
Q b1 together with pigeonhole argument, we can bound term (7) as:
(I) & 2900 A2
By applying the bounds of terms (j), (k), and (I) into Eq. (43), obtain:
(h) < HPS AT + 2112 2 TTL + 2900 5 A2
By applying the bounds of terms (h) and (i) to Eq. (42), applying the definition of [k] and applying the subadditivity of the square root, we get:
43

---

Sleeping Reinforcement Learning
(c) < 2 CEN/HHATTLL 13890
Finally, we can combine the bounds of terms (a), (b), and (c) into Eq. (39), obtaining the following bound:
H-1 (si.
k H-1
Ifce [k]opp
Σ 8 2,
4,
(1,B),)) & V 16HSAT,LG
SHSAL Σ
Σ
A (1
==h
j=h
+ HSALG + 2/3HSATLL + 5800 A22 L3
v 28HSATTLG 8HSALG Σ H-1
AY (
+ HSALG + 5800
H L.
In similar manner, observing that events Eax (Fre H², IP.L.. and Ens M.n. H L. also hold under E, we can derive the bounds for the remaining summations, thus concluding the proof.
Lemma D.11 (Summation over typical episodes of state value function bonus term). Let l: [K] and h E [H]. Let ne be the policy followed during episode k. Let the UCB bonus for the state value function be defined as:
4L Var B~ ((e) ( (e)
(s, B))
7HL
(s)
Na(s)
((N( -1
4E BBBd-dd (11a)
m 1350
Ny(s)
Under the events & and Da the following inequalities hold for every E S:
H
Σ M e [kyp
Σ
b
(s.g) & v 45HSAT
HSLG + 2700v 2700V 2 A22
3
5=
k H-1
ALG2 Σ
(
lii E [k]ttp.s 84,6 s) 3}
H-1
Σ (9.,)
(SH) JISLG + 2700 H
7
3
H-1
31 Σ I[SEA = Σ
Av
j=h
H
Σ Ifie E [klopps,a St.1 s, a.
(B....))
= a}
Σ
bY, ($L.)
j-h
4SEPSANNA((s, HSLG 2700
44

---

Sleeping Reinforcement Learning
H-1
31 Σ
MSsL =,
(.(Bu,a) = =a} Σ b=h
-1
where:
kkyp == E [k]] (8i,h Oih
(((B.a)) E [[s, Jx, i > A2 L2G, [m]]]
[k] byypp = E [A]] (St,h 4
(B.a)))
E aks Na. > 11600 S A2" L'G, wh E [H]].
[ylypssa := e [A]] (8i,h: Oih
E [(s,a)]a (s, 3 11600 A2 12 [(8, ([s,a)]: := ((8, a) E S x A: a)) > H. (a,( > H, e [H]].
x.(B..))
wh [M]]
Proof. We can rewrite the summation as:
H-1
h
4L Var H- (iis aij (0))
uii [k)b Σ
Σ
li e [k
Ni(oEJ)
(a)
k
H
7HT.
I[i e typp)
((V 1)
j=h
(6)
H
4TE ABBB--C (110.)))))))))))))))))))))))))) ( B)
I[
[1] hyp
(44)
Ni(81.)
where D (s.j) B) = minf ss A2
2H First of all, we can bound term (b) by applying pigeonhole argument
Ny (e
as:
(b) HSLG.
3
We now focus on bounding term (a). By applying Cauchy-Schwarz's 's inequality, we obtain:
k H 1
H-1 1
(a) & V4L
Σ
Σ
(sss)
lli E
[klppt jーh
Σ
(45)
No(81a)
(d)
Using the pigeonhole argument, we bound term (e) with SG. We can rewrite term (d) as follows:
k
サ- 1
Ø-1
(d) Σ Σ (5t,))
+
(Q,() - (3.s))
(46)
(0)
45

---

Sleeping Reinforcement Learning
We bound term (ʃ) by using Lemma D.7 as:
(f) Σ Σ (st.)
4 L H +
HT, + 2v
and term (g) by using Lemma D.8 as:
(0) Σ -
& H² VSAATAL 7H AT ST.
2H
Σ Σ
T. (B.55) + 2H (8.g.
Σ Σ
Ay (
1=1 j-h
By plugging the bounds of terms (f) and (g) into Eq. (46) we get:
4 H 1
(d) HTg + 2 H
k 1-1
1111
2H Σ
(B.))) + 2H Σ Σ
AV
1 (86.+1)
< HT, + 2/ HTT& + + 11 2 S2 + 7H1 S A SH3
H-1
+ LG + 2H
8HSALG Σ Σ
AY (8..t1)))
f=h
14 3
S2 + 116000 H L3 AP + 2H
Σ
H-1
Σ
A (
(47)
4: Ø-1
H-1
8HT, 2H
Σ Σ
AV (1
32H'SALG Σ
Σ
(48)
where Eq. (47) follows by applying Lemma D.10 and Eq. (48) holds under [k]tpp By plugging the bounds of terms (d) and (e) into Eq. (45), rearranging the terms, and applying the subadditivity of the square root, we obtain:
H-1 Av
(a) < v 33HHSTLG + ALG2
(
(49)
The derivation of the bound of term (c) is similar to the derivation in Lemma D.10 from Eq. (42) onward. First apply Cauchy-Schwarz 's inequality, rewriting the term as:
46

---

Sleeping Reinforcement Learning
k
H
k
H カ-1
(c)
<
B
V G- (151))
D ()
Σ
Lif E (byp)
(50)
Ni(ses)
(h)
(4)
With a pigeonhole argument, we bound term (i) with SG. We now rewrite term (h) as:
k H-1 (h)
Gi (BLS)
H-1
H-1
Σ
(Cind ) ($i
TV
Σ
( (85.g)
+
1=1 5=h
(1)
k H
k H 1
5 +
Σ
Σ
((cinab)s) (81.) - (
+
Σ
b
(51)
j- h
(R)
(1)
V By bounding fij+1 with 2 and combining the application of (Weissman al., 2003, Theorem 2.1) and of pigeonhole argument, we can upper bound term (j) as:
(1) < H V LL.
To bound term (k), we first observe that it is Martingale difference sequence, and as such we can bound it via the event Eax (F, k.h' H2, L), which holds under E, thus obtaining:
(k) < 2112 TTLL
By applying the definition of bi together with pigeonhole argument, can bound term (1) as:
(I) $ 1350 S* A22
By putting together the bounds of terms (f), (k), and (I) into Eq. (51), we get:
(h) & H2 S24T&L V + 2H V T H3 A
(52)
By applying the bounds of terms (h) and (i) to Eq. (50), applying the definition of [k]eyp- and applying the subadditivity of the square root, we get:
(c) & LHSAT,LG + 2700 H
(53)
Finally, we can combine the bounds of terms (a), (b), and (c) into Eq. (44), obtaining the following bound:
47

---

Sleeping Reinforcement Learning
H-1
H 1-1
Σ
eie [kypp
Σ (1.s)) & 3 5=h
ALGZ
(541(
7
HSLG + HSAT,LG + 2700v 3 L3
45HSAT
ALG Σ Σ 1
7 HSLG + 2700v H3 A22A
In a similar manner, observing that events End FF h.h.s 2 L) and (F k.h. H², L) also hold under e, we can derive the bounds for the remaining summations, thus concluding the proof.
Lemma D.12 (Upper bound of acteonction value function estimation error). Let E [K] and [H]. Let m be the policy followed during episode k. Under & and & the following holds for every (8, a) S A:
a) min
1350
H1
Na,1 a)
Proof. We begin the proof by observing that, under aa Qn,((s,)) > (7 a) for every s S and A. We can rewrite:
Qun(s, -(,()))
1
1issh 5, aih
a.(B.,n) a} (Qun(sin, Lsh (.(Bun)) (s,,b, aih (((Ban))
1
T.(Bi,n) =a} (Sth
aihh (.((B11)) - 17 2i (((B)))))
(54)
(s,
(.(B.,)) a) a) 1. (si aghb (((B))))
1sss 8, aih
(55)
where Eq. (54) follows from the fact that Qu, is monotonically decreasing in & by definition and by observing that O7 Q
Recalling the upper bound of E M[8i = aiA
(Bi.)))) a} 09 (si,h, 4,h
T.(Br.)):
188th 8, 0j,h
(B.B).))
= 2
22 (8i,,,
Nc(Braa)
#-1
$ e
Ifsi, = 8, aia
(.(B.,a)
a}
Σ
(8i
Ozj
=:(B:s)) + 2b (8(5+11)
8-h
8H2ST.
2
+ - ((P--PIViE))
(:(Bis))
N.(sig:0 (B.))))) 4H,
Ni((1)+1)
2ex/ H3 + H HNK,(s, + 4ey (H,N,,((,
we can apply two pigeonhole arguments, obtaining the following upper bound:
48

---

Sleeping Reinforcement Learning
I(si 5, 5,
(.(B.,)) a k.
(8i,h; ath
(B(B)))
k
Ø-1
1ss s, 0iA
o}
Σ
Dig (i aid
n,(Brs)) 2015+1((h5++)
5=h
+ (P:-P)Vj+1)) (BE.s Add (11((111)))
+ +8H25² ATG + AN H852ANN,
2e (HNN,,(8,a)L + 4ey HNa, + 4ey H&Nea(s,a)L
(56)
= Uk.h.s..
We now bound the summations over episodes and stages of the different terms. By applying Lemma D.11, we can bound the summation over typical episodes of the state value function bonus term as:
H-1
lie [kjppp 9i,A s, 5,aih
(B,...
a}
Σ
by (91.)
h
7 451/"SAAN.. BALLI++HSSA HISG 2
111
31 ALG²
1181 = s, 3,4, = a} Σ
(B.
Av
(1tt((11511) (57)
5-h
(a)
By applying the same procedure as in Eq. (26), we can bound term (a) as:
H-1 1
(a)
Ili E [klppp 81, = s, 0,
(B..))
a}
V
j+t
(81541)
j=h
H-1
+
>
Mii E klypp: s, ain
T((Bi,))
a}
+1
Q
1=1
j=h
#-1
2
+ 2H
Ifi E [k]typ 81.h s, 0,K >
x.(Ben)
Σ
Ne(si.411
1-1
j=h
k I[ie E [kleyp. s, a
H-1
T((Bi,)
a} Σ
1 0 (B(
j=h
4SHPSANN... 7 HSLG H AP + ALG
+ 2/ 2 HHNNe 2 H NT a) + HUKh.aa
(58)
where Eq. (58) follows from the application of Lemma D.3 and Lemma D.11, the application of a pigeonhole argument, and (B.))))) with HUR.h.s.
by bounding Σ Ifsi,h = s, aihh
(B. a} ΣØー ( 9,++1
By applying the bound of term (a) into Eq. (57). applying the condition of [k]s and rearranging terms, we obtain:
49

---

Sleeping Reinforcement Learning
H-1 a}
Σ lii [k]opp 9i,4 = 4,h
(B(b.,n)
Σ
by (s6g)
< 4v 45
31/1 k,k,,,
3014v H A22AT3G2.
By applying Lemma D010, can bound the summation over typical episodes of the state-action value function bonus term as:
11
Ifae e [kleyp, Si,h
a,
(B.)..))
a}
Σ
b (Si.j Oz,
(B.B))))
h
V ANH,,,AN + HSAL?
#
SHSALG 2 11, = 8, aih
T((B.N)
a 3)
(59)
(a)
By applying the bound of term (a), as computed in Eq. (58), and plugging it into Eq. (59), we get:
k
H-1
Tie (kyp 8i,1 8,
(B,..,
a)
Σ
Q
(ig.
Rij
j-h
$ 28H
/ k,b,
+ 59
By applying Lemma D.9 can bound the summation typical episodes of the Mcte-action wise model errors as:
#-1
{i E [1]] hyp: Si,h = 0,0,,
(B..aa))
a} j=h
Σ
(P,- (PV-P)V (si,) (81)) ((Bss)))
6H HSALG 2 H
2
H2SALGU R.
By applying two pigeonhole arguments, combining the bounds, and accounting for the regret of non-typical episodes, we can then upper bound Eq. (56) as:
Unhaa & /2eN/
16e H= ALG + 11996cv A2AA3A22 + 11600
Letting:
a =
92
11996v 119
50

---

Sleeping Reinforcement Learning
8 16ev ALG
can solve for Ukias Un & 2a + 8 and obtain the following bound:
Ukh.ss,a & 1
2 + 23200H' A2
LA + 256e H
ALG?
1350 H353 A2 N2.
(60)
where Eq. (60) follows from the application of the [k]typ condition. Plugging this result into Eq. (55), and observing that the error cannot be greater than H, we get the following bound to the estimation error of the state-action value function due to the optimistic approach:
A
(x, - (x, & min 1350
.H
thus concluding the proof.
Lemma D.13 (Upper bound of state value function estimation error). Let k E [K] and h E [H]. Let Te be the policy followed during episode k. Under & and Pg the the following holds for every (a, a) E S x A:
H3S3 A2
(s) (s) & min 2900
11
(x,
Proof.
We begin the proof by observing that, under aa QR, > (*(s,,) a) for every s S and A. We can
rewrite:
-v)(())V(((s)
- (+)
Ilsi 5} (Pan()La)-V (8(.a)))
(8)
1
llfsi tf (Prn(siN) - V/ (sEn))
(61)
(s)
I[ o)
(62)
(8)
where Eq. (61) follows from the fact that Ve, monotonically decreasing in & by definition and by observing that V V
Recalling the upper bound of E M8 = 8) (o..)))
k H-1
M(sh (
2
Σ
Σ
(51,)))) ( dij
x(BBs)) + - ($t an (n (((B,a))
SHRSL
SHSL
T.(B.,)) + 2H22AL
2H2
+ E (B
3Ni(si.j azj (B)
3.N Oij
Ni(sis)
3N((81g)
2 No(81.))
+ + (3) 662 (NN, 402 (S),
51

---

Sleeping Reinforcement Learning
by applying several pigeonhole arguments, can derive the following upper bound:
Σ [as = ( & e Σ Σ
by (51.)) + +26%, (s1,, ai T.(Bra)) + + ( -PP)-))) (si.) and (1,))))))
1
+ 86 8E 22 LG + e² (2HSSN V 462 (S) 10e², HN),
(63)
Uk.,,
where Eq. (63) is obtained observing that, when applying the pigeonhole argument over a summation which the argument depends on the expectation over B, the worst-case allocation of summation terms the one which actions are available. We now bound the summations over the typical episodes of the different terms.
By applying Lemma D.10, can bound the summation over typical episodes of the state-action value function bonus term as:
H- $} b=h
li [k]tps SLn
8 Σ
(s
ais
x.(B.s)
< 28H SMPSALGU...
HSALG + 5800 A
By applying Lemma D.11, we can bound the summation over typical episodes of the state value function bonus term as:
H-1
Ilie [K] hyy: 8in st
Σ
by (sa)) &
j=h
7 HISGG + 2
By applying Lemma D.9 we can bound the summation over typical episodes of the state-action wise model errors as:
H-1
[k]ypp S1,6 s}
Σ
(PV--)V;;t1) 0/ a.
(1(BB,))) (st.g,
1=h
v (HHSAAN,.)))GGG HSALG + 2 H2SALGUR.. k..
By combining the bounds into Eq. (63), get:
UKA. 38c² / /1 16e2 I
+ H431772 + $ 12
(64)
Letting:
a 38e2
N + 14 11 10
3 = 16e HB8
(65)
52

---

Sleeping Reinforcement Learning
can solve for Uks &k,,, & 2ax Be, and obtain the following bound:
Uk,h,s 76e2
[I,SA2AN,,(S)A 2 23200H1S 256e $
< 2
1155 A2A NM.
(66)
where Eq. (66) holds if (s) 3 VI1600H"5* Plugging this result into Eq. (62), and observing that the error cannot greater than H, we get the following bound to the estimation error the state-action value function due to the optimistic approach:
H A2AL2G
(s) (s) min 2900
Nx,
thus concluding the proof.
Lemma D.14 (Optimism), Let the optimistic bonuses be defined as:
AL Var & Pe(1e, P [V,)+
7HL 3(Na(s, a) 1)
K. (s)
()(s,a)
41 s' (11,,) min 2900 435
H231
Nhati(d)
Na(8,a)
4L V Var Varg (rd( (s, (s. B))
7HL
(8)
(s)))
3(Nx(8) 1)
4E B (rd(()))))))))) min) 52 H
(6.n(
(a)s)
Then, under event E, the following set of events hold:
Dg.h (in())> (b) ^ (i)(s, 2 (s, v(i,)) [k, Nhist S, A
for k [K] and h e [H], where:
[k, hbiitt = ((i.g) :ie [K].j e [H] (i < k) k.j- h)).
Proof. We demonstrate this result by induction. We begin by observing that (x,H+1(s) (s) and
(1,,+ (s, 0 for every & E [K]. S, and a E A. To prove the induction, we need to prove that, if 2R, holds, then also Sa.. holds. We prove this result for a generic k e [K]. and we observe that we can then apply this procedure recursively for all values k starting from 1.
We begin by demonstrating that (s, > (s, a). Let us recall the definition of Q (8,
53

---

Sleeping Reinforcement Learning
Qun(s,a) R(s,a) + (s, + (PaVan))) (s,a),
observing that if ak)( 3 H h, the optimism holds trivially. We can write:
= as, (PaVe)ett) (s, (s,a)- (s,
(s) (Px - virt)) (s, + (iPp-PJVit)) (8,
as, (P&e - -P))) ())
(67)
where Eq. (67) follows from the induction assumption. Under event &, we can apply the empirical Bernstein inequality (Maurer & Pontil, 2009):
2 (
(1Ps- - PIV (s.
7HL
N4(8,a)
aN)
where V+ 1 = Var, v A((oia) [V 1 (s'). As such, we obtain:
24 (8)
7HT. 3(Na(s, 1) 2 (8, Na(s,a)
(s, - (h. (s, V
Na(s,a)
(x(
(a)
4 Eves Pa(s'la, min
2300 H2
(x)
(68)
Na(s,a)
Observing that:
2 k.h (s,a)- ((.a))
V ( & (8, otherwise,
(a)
(a.0)))
we now bound X kb+1 in terms of V 14 from above. Observing that:
Var [ E [X 2[X]]²
E + Y - E[X] + 2[
IE[(- - E|x Y]+ - 2|
$ - - - --1 + 2E Y E 2
2VarXX - var
(69)
we can then write:
54

---

Sleeping Reinforcement Learning
(s & (V) +2 Var
[V'+ Van+i(55)]]
2V a) +2 Σ Pa(s||s,a) (Ventz(ss) - Vit)(
e'ES
By combining this bound with the result of Lemma D.13, we obtain the following bound on term (a):
(a) > Evrss Pa(s'ls,a) min
2000 .1a) (k Nels.a)
if ( & V (s, otherwise.
By plugging this result into Eq. (68), obtain that as, ()) O.
We now demonstrate that (s) 2 Vi (s). Let us recall the definition of (s):
(s) min min( ( (x))) + F B-dr (R) (x )1)
Again, observe that, if (s) = H. the optimism holds trivially. Moreover, (e,((s) = Đ - 1k-1,1188 1,), the opti- mism holds trivially under S4 As such, we only need to demonstrate the case in which (s, = bK, (s) + Bxd ( (8, Jkh (.) We can write:
(s)(s) - (s) = (s) + (Cind Qu.n) (s) (Cind (s)
(s) + (Oimd Qu.h Qh) (s) + -
- Cind (( (s)
(s) + Σ
Giidd (i)ss))s)) (Q (s, (s, 0+ (s,
(AA(A)
+ ((Cipd Crind ) (s)
(70)
(s) + ((Cine - Cridd ) (s),
(71)
where Eq. (70) derives by observing that T. is the greedy policy w.r.t. Ve and Eq. (71) follows from the optimism over the
state-action value function we just demonstrated.
Under event E, we can apply the empirical Bernstein incquality:
2Q (8)L
((Cmme Cind Q ) (8) $
7HL 3(Nc(8) - 1)'
(72)
Ne(s)
where (s) = Varg Grd 12 ag
x*(()) }. As such, we obtain:
2QL. 7HE 3(Nx(s) -1) 1)
(5) (s) > (s)
Na(s)
55

---

Sleeping Reinforcement Learning
4Qm,((8)
2Q (s)
(s(s)
N&(s)
(6)
(BEP(A)
Crndd (B]s) min
13502 A22A1A
H
(B(8))
(73)
(s(s)
Observing that:
26t (x) Nx(
if (s) & (2)(s),
(b) 2
0
otherwise,
now bound Q7 in terms of Qa. from above. By applying the result of Eq. (69), get that:
(+) & (Q),((s) + Var (0x (-
dg,h (L(B)) - Qu,n a agh [1
$ (s) +2
Σ (AP(A)
Q% (n Qu, a (u, ())
(74)
By combining this bound with the result Lemma D.12, we obtain the following bound on term (b):
(b) EserLa) (B)s) mine 1850 w3 oa , (a.n (8))
if (x) & Qan (8),
(x)
otherwise.
By plugging this result into Eq. (73), we finally obtain that (s) > (s), thus demonstrating optimism.
Theorem 5.2 (Regret Upper Bound S-UCBVI with independent availability and per-stage disclosure). For any ô (0, 1). with probability 5, the per-stage disclosure regret of S-UCRVI any SleMDP with per-stage disclosure independent action availabilities is bounded by:
RPS(S-UCBVI,T) 5512H
4988 HD A2 T.2.,
where L = 1og(80/1S* and G log(HSAT)). In particular, for T 55 A122A) and selecting 5 2- 24//T, we have:
E E[Res(S-UCBVI,T]) ( (HVSAAT)
Proof. This proof adapts the result of (Azar et al., 2017, Theorem 2) to the Sleeping MDP setting in the case of i.idd. action set availability and per-stage disclosure. We start by considering Sleeping MDP in which the transition probabilities are stage-independent, as the generalization is straightforward and we consider it at the end of the proof.
Let events and Qg hold. Under these events, Lemma D.14 holds.
As such, we define the regret suffered by an algorithm A after T time steps as:
R 2
(V (s..1) (TT = AYa().)).
56

---

Sleeping Reinforcement Learning
We can define a pseudo-regret suffered by an algorithm 21 as:
R (2)
(Va(( - (82a)) = (o..).
By applying Lemma D.I, we first observe that Σ (o)()))) & E AK (8.2), and we decompose the pseudo-regret as:
K
H-1 Σ Σ
Σ (P,NN))))
by (5.))) + (i ( (3 (1 1+ _ 6 ( a. (1(B))))
11
V2I.
+ EB ((dda))
[
+ H
fig v + (mm
[VLEY 1...8 +
H Eig + V2LEi
+ ((
(B1.), (Pi--))
(1(1))
+ H
((P:- -P)V (st.), ai. (1(B)1)))
8H2SL
SHSL
+ (BBCCd((bbs))
+ 3N, Oi
3Ni(si.s x.((8)
(.(B..))
aij
2 N((ss))
2
22 (BL
2HL
3N(()))) +1 Ni(s1t)
3N(($1s)
By applying several pigeonhole arguments, we obtain:
K
K R-1
(Y.N)))) E
2
Σ Σ
(9h.)) + Ess 16 (sL).
1+ [1)10]
(B
-
1
(3.) (7188)) (.(B.s))
11
+ V2L
+ E Ex Cind (131)))
| + "eiss vv + (p
V2LE! [,5.8]
Ey + 22LE,
H
(P:--P)V;e) (sij) 18)
H (IP, -P'VVtta) (st.j, And (.(BBa))
1
+ E8 (od
+ 207 (
+ A2
(75)
Ni(sis)
(0)
= -K-1-
We can bound the summation of term (a) over typical episodes as follows:
K
H-1
K Σ
H
20 (L
Σ
Mi E [k]tpp]
Σ 1-1
(a)
=
Ifi
E
[
byp
1-1
V2L
K Ø-1
Σ llii (klppp)
1 1
1
(76)
Ne(o1.)
& V2TA HT + 2V HATT. + H3LN SG
(77)
3
& V4HSTLG,
(78)
where Eq. (76) is obtained by applying Cauchy- Schwarz's inequality, Eq. (77) follows from the application of Lemma D.7 and of a pigeonhole argument, and Eq. (78) holds under [k]opp-
57

---

Sleeping Reinforcement Learning
By applying this bound, together with Lemmas D.3, D.9, D.10, D.11, the condition of [k] accounting for the regret of non-typical episodes, and rearranging terms, get that:
UK11 256y LG A / HAS
(79)
By letting:
256v HSA.LG 117392H1 A2 A2A L²G,
3 113v SLG
(80)
we can solve for UK,1 as UK,1 & 2a B², and obtain the following bound:
KK & 512v 51251122TTTI HSATTG + 247533H A2 G,
which we can plug into Eq. (75) to get the following upper bound on the regret:
Rps(S-UCBVA) T) & 512v HSATLG + A2 A2
Considering stage-dependent state transitions, can address this generalization by considering a new Sleeping MDP with state space X' such that | = SH. As such, the regret in this case is upper bounded by:
Rps(S-UCBVI,) & & (VIPSATIG + S A2 =: UBPs(6),
w.p. at least 1 - 8.
To obtain an upper bound for the expected regret in the case of indee-independent transitions, we select å = 24/T. and obtain that, if T > 24, holds that:
E [[Rps(S-UCBBL,
-1gp::/eego--sssss///////de/r/er (o)]]
[= (B)](
UBps( + 78
(81)
< 512 HSAT log (80H Log(H 498 5 A2 log(80H log( (HSA)) 24,
log
(82)
where Equation (81) follows by applying the high probability regret upper bound and by observing that (Sp(SSUUC (S-UCBVI, T. Moving to stage-dependent state transitions, we generalize above and rewrite Equa- tion (82) as:
E [RRRSSS-UCBVI,T]) 512H SAT log (og) HH' 4988211 6 A2 5 log( SAT) + 2
ò (HVSAT 5 A24)
(83)
Finally, we observe that whenever thus concluding the proof.
50 A2221) the upper bound of the expected regret is of order Ö(HVSAT),
58

---

Sleeping Reinforcement Learning
E. Numerical Validation
In this appendix, we propose the StochastticrrozenLakke setting and numerically validate our s UCBVI against UCBVI, showing the efficacy of exploiting the knowledge of action availability. The code reproduce the experiments is available
Setting. The StochasticFrozenl Lake environment is modification of the well-known Frozenl allow holes in the lake to open and close stochastically, effectively limiting the action availability of the agent stochastically during the episode, The probability of cell of the grid being hole at any given stage is denoted via parameter except for the goal cell and the cell in which the agent is located at the beginning of the stage. which cannot be holes. We vary the probability of holes in the lake as E {0, 0.5, 0.75) and the grid size of the lake as G E (2, 3, 4). We consider a horizon H 10 to ensure that the agent can reach the goal. We consider K 10 episodes, and we compare S S-UBBVI and UCBVI terms of instantaneous reward averaged over runs, with 95% confidence interval. We also report the optimum computed apriori for reference.
Results. The results of the experiment are reported in Figure 7. We observe that, when p O, i.e., there holes in the lake, both S SCUBVV and UCEVI manage to achieve the optimum instantaneous reward. As p and G increase, observe that S S-UCBVI manages to achieve the optimum, whereas UCBVI settles to suboptimal value, with the gap between the two algorithms increasing in directly proportional manner w.r.t. the two parameters.
59

---

Sleeping Reinforcement Learning
Instantionnur Rewwrd
Instantamenur Reward
Instomianeso Reward
Optinun
2-
Dpt Lanum B-CCBVI
2-
Cptimun
B-0CBV1
8-UCEVI
UC3V1
DCBVE
UCBV2
0
0
0.5
1.3
0.5
1.5
0.3
Episodes
Ppisodes
Episodes
(a) p =
(b) p 0.5, = 2.
(c) p 0.75, G 2.
Optimmm
3-UCEVI
UCBVI
Instantanenss Keward
Instamaneeous Rewand
Instant Reward
Opt
Pgtt S-DOBVI
S-DCBVI
DCBV1
DCBVT
0-
0-
0.5
1.3
0
0.5
1.5
0
0.5
Episodes
Episodes
Episodes
(d)
0, G 3.
(e)
0.5,
C 3.
(1) p 0.75, G 3.
Pigh
5
Cpt
LCBVE
Instantinouus Roward
Instumtamnus Reward
DORVT
Reward
4
UCRVT
Insenttncous
2
2
B-0CBV1
DCSW3
0-
0
0.5
1.3
0
0.5
1.5
0
0.5
1.5
Episodes
-105
Episodes
-10
Episodes
-10"
(g) 0, G=
(h) 0.5, G
(1 p 0.75, G 4.
Figure 7. Performances in terms of instantaneous reward in the StochasticFrozent environment with horizon H 10, numher of episodes K = 2 10 hole probability {0, 0.5, 0.75) and grid size G e {2, 3, 4) (5 runs, mean + 93% C.I.).
60


Reviews:
[{"review_id": "8jiKqdrxZe", "reviewer": "Reviewer_iuwR", "summary": "This paper studies a new paradigm called Sleeping Reinforcement Learning, where the available action set varies during the interaction with the environment. The authors study several settings, including the per-episode disclosure, in which the available action sets are revealed at the beginning of each episode, and the per-stage disclosure, in which the available actions are disclosed only at each decision stage. The authors provide algorithms, upper and lower bounds for the problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the time spent reviewing our paper and for having appreciated the motivation, clarity and novelty of our work. Below, our answer to the Reviewer's comments.\n\n> It may be better to also provide a lower bound for the setting of independent per-stage disclosure.\n\n> It is possible to also provide a lower bound for the setting of independent per-stage disclosure? I believe this may help better understand the problem.\n\nWe thank the Reviewer for giving us the opportunity to elaborate on this. After careful consideration, we argue that a **tight lower bound for the independent per-stage disclosure case is the same as that of standard MDPs, i.e.,  $\\mathbb{E}[R(T)] \\ge {\\Omega}(H\\sqrt{SAT})$** (see Domingues et al., 2021). Clearly, the lower bound for standard MDPs is a lower bound for the independent per-stage disclosure case, since the latter includes a smaller class of problems in which all actions are always available, i.e., $C^{\\text{ind}}_h(\\mathcal{A}|s) = 1$ for every $(s,h) \\in \\mathcal{S}\\times [H]$. Concerning the tightness, we need to carefully compare it with the upper bound of Theorem 5.1. First of all, the lower bound $\\mathbb{E}[R(T)] \\ge {\\Omega}(H\\sqrt{SAT})$ (Domingues et al., 2021) is for the **expected regret** (as customary in the literature), while our upper bound for the per-stage disclosure case of Theorem 5.1 is for the **regret in high probability**. Thus, we need to convert the latter to the expected regret in order to perform the comparison. To do so, we start from the first regret bound of Theorem 5.1 (disregarding constants and logarithmic terms, but not terms depending on $\\delta$):\n$$\n   R(T) \\le  \\text{UB}(\\delta) := \\widetilde{O} \\left( H \\sqrt{SAT \\log\\left(\\frac{2^A}{\\delta} \\right)} + H^6S^3A 2^A \\log\\left(\\frac{2^A}{\\delta} \\right)^2 \\right), \\qquad \\text{w.p.} \\quad 1-\\delta.\n$$\nNotice that by disregarding the dependence on $\\delta$ and for sufficiently large $T$, we obtain the second regret bound of Theorem 5.1 (still in high probability). To get the upper bound for the expected regret, we make the choice of $\\delta = \\frac{2^A}{T}$, whenever $T \\ge 2^A$, obtaining (since $R(T) \\le T$ always):\n$$\n\\begin{aligned}\n    \\mathbb{E}[R(T)] & = \\mathbb{E}[R(T) \\mathbb{1}\\\\{R(T) \\le \\text{UB}(\\delta) \\\\}] +  \\mathbb{E}[R(T) \\mathbb{1}\\\\{R(T) > \\text{UB}(\\delta) \\\\}] \\\\\\\\\n    & \\le\\text{UB}(\\delta) + T \\delta \\\\\\\\\n    &  \\le \\widetilde{O} \\left( H \\sqrt{SAT \\log\\left(T \\right)} + H^6S^3A 2^A \\log\\left(T \\right)^2 + 2^A\\right) \\\\\\\\\n    & = \\widetilde{O} \\left( H \\sqrt{SAT } + H^6S^3A 2^A \\right).\n    \\end{aligned}\n$$\nThe latter is of order  $\\widetilde{O} \\left( H \\sqrt{SAT }\\right)$ whenever $T \\ge \\Omega(H^{10}S^5A2^{2A})$. We will adjust the presentation of the result in the final version of the paper, clarifying the difference between expected regret and regret with high probability bounds, and, consequently, the discussion on the result and the future works. Thank you for rising this point.\n\n> In Lines 130-132, $V_{ED}^* (A)$, $V_{SD}^*(A)$, $V_{LLC}^*(A)$ are used before definition.\n\nWe agree with the Reviewer that (at least) an informal definition is needed also in this part. It was an oversight, we fixed it. Thank you.\n\n> Typo in Line 195.\n\nThanks, we fixed it.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The work is related to the works on sleeping bandits, where the action sets vary in time. To the best of my knowledge, this is the first theoretical work on sleeping RL.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\n1. This is the first work to theoretically study the important sleeping RL setting. It is well motivated, the authors provide many examples to show the importance of this setting.\n2. The paper is well-written and easy-to-follow.\n3. The authors conduct a complete study in this topic, providing algorithms with regret upper bounds, and proving novel lower bounds. \n\nWeaknesses:\n\n1. It may be better to also provide a lower bound for the setting of independent per-stage disclosure.\n2. In Lines 130-132, $V^*_{ED}(A)$, $V^*_{SD}(A)$, $V^*_{LLC}(A)$ are used before definition.", "other_comments_or_suggestions": "There is a typo in Line 195.", "questions_for_authors": "It is possible to also provide a lower bound for the setting of independent per-stage disclosure? I believe this may help better understand the problem.", "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": "", "extra_scores": {}}, {"review_id": "ZFX5laJGd7", "reviewer": "Reviewer_nkFn", "summary": "The paper introduces Sleeping Reinforcement Learning (SleRL), a new reinforcement learning paradigm where the set of available actions varies over time due to external constraints or stochastic processes.  Two settings are considered: per-episode disclosure where available actions for all states are revealed at the start of each episode and per-stage disclosure where available actions are revealed only at the current step. They show an upper bound and a lower bound for the regret of a modification of UCBVI in each setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the time spent reviewing our work. Below, our answer to the Reviewer's questions and concerns.\n\n> Is it possible to add some numerical results to verify your results?\n\nTo numerically validate the algorithm and show the impact of action availability on performance, we consider a modification of the well-known Frozen Lake environment (https://gymnasium.farama.org/environments/toy_text/frozen_lake/). In the original version, the agent must traverse a frozen lake (i.e., a grid) from a start to a goal position, avoiding holes in the surface (i.e., unavailable positions in the grid). We modify it by letting such holes open and close stochastically (i.e., the unavailability of each position is sampled at each time step from a Bernoulli with parameter $p$).\nWe assume the start and goal to be fixed in the top-left and bottom-right corners of the grid, respectively.\n\nThe agent can move up, down, left, right, or stay. If the agent selects an action that would move it to an unavailable state, it stays in the current position.\nThe reward function is defined as follows: the agent receives reward $1$ for state-action pairs that have the goal as next state, and $0$ otherwise. The episode stops at the end of the time horizon (not when we reach the goal state).\nGiven that all positions (except the start, the goal, and the position occupied by the agent) have the same probability of being frozen at any time step, it is easy to see that the optimal policy tries to move along the diagonal that connects the start to the goal. \nTo compute the value of the optimal policy, we perform a Montecarlo simulation for each evaluated setting.\nWe compare our S-UCBVI (Algorithm 7) with standard UCBVI (Azar et al., 2017), observing that the latter interacts with the environment as shown in Figure 1. We compare them in terms of reward, to highlight that both algorithms converge, yet UCBVI converges to a suboptimal objective.\n\nWe evaluate grids of size $G \\times G$, with $G \\in \\\\{2,3,4\\\\}$, varying the stochasticity parameter as $p \\in \\\\{0,0.5,0.75\\\\}$. We consider a time horizon of $H=10$ for each episode and $K= 2 \\cdot 10^5$ episodes.\n\nThe Reviewer can find the plots of the experiments here: \n\nhttps://drive.google.com/file/d/19WlZpKUHoSoYxx4PgT3jNLqyfmrm9twu/view?usp=sharing\n\nand the code here:\n\nhttps://drive.google.com/file/d/1NBoDjr9P_eaUcO1Na4nyzE71q4zgAKwR/view?usp=sharing\n\nAs expected, when $p=0$, we observe no performance difference. Instead, as the environment stochasticity increases, we observe a greater gap in the performances of the two algorithms, with S-UCBVI (our algorithm) achieving the optimal value (obtained via Montecarlo simulations as described above), represented as an horizontal line, and UCBVI not reaching such optimum. This is due to the fact that UCBVI cannot observe action availabilities, effectively playing in an environment with a lower optimum.\n\n> Is it possible to reduce the bound gaps [...] between Theorem 4.1 and 4.2?\n\nThe lower bound of Theorem 4.2 that shows an exponential dependence in the cardinality of the action set represents a **statistical barrier** in the learning for Sleeping MDPs with **Markovian** per-stage availability. For this reason, as common in the literature (e.g., MDPs with adversarial transitions [1]), the goal is no longer matching such an exponential lower bound, but rather finding **structures** (e.g., independent action availability) that overcome such barriers. The result of Theorem 4.1, indeed, has to be interpreted as just an exemplification of the fact that, when accepting such an exponential dependence, the Sleeping MDPs with Markovian per-stage availability can be addressed through the augmented MDP method. We will clarify this in the paper.\n\n[1] Tian, Y., Wang, Y., Yu, T. and Sra, S. Online Learning in Unknown Markov Games. ICML 2021\n\n> In the definition of three regrets, is there a typo? I guess $T$ and $K$ should be the same thing, the number of episodes.\n\nWe checked and the notation is correct and compliant with (Azar et al., 2017) where $T = KH$ is the total number of interactions (see Section 2), $K$ is the number of episodes and $H$ is the horizon of the single episode.\n\n> Is it possible to reduce the lower bound condition for $T$ with a factor $H^{10}$ in Theorem 5.1?\n\nJust like in (Azar et al., 2017), for the UCBVI algorithm and its analysis, it is challenging to remove such a dependence on the horizon $H$ from the minimum $T$ condition. This is exacerbated, in our case compared to (Azar et al., 2017), since we consider stage-dependent transitions (doubling the exponent of $H$). Nevertheless, there exist works [2] that succeed in mitigating such a condition at the price of more complex (and less effective in practice) algorithms. Importing such techniques to the Sleeping MDP setting can be an interesting future work.\n\n[2] Zhang, Z., Chen, Y., Lee, J. D., and Du, S. S. Settling the sample complexity of online reinforcement learning. COLT 2024.", "claims_and_evidence": "The regret bounds are supported by proofs.", "methods_and_evaluation_criteria": "The algorithm is a modification of a classical algorithm called UCBVI,\nand it makes sense for this problem.", "theoretical_claims": "I have roughly checked the proof of Theorem 3.1 and it looks correct.", "experimental_designs_or_analyses": "No experimental designs.", "relation_to_broader_scientific_literature": "This work is related to Multi-Armed Bandits under the name of “Sleeping”\nMABs and Reinforcement Learning with constrained action spaces.", "essential_references_not_discussed": "This paper has discussed essential references.", "other_strengths_and_weaknesses": "Strengths:\n\n1. This paper is a pure theoretical paper  and offers detailed analysis about the upper bound and lower bound for the algorithm.\n2. This paper uses a novel construction (Figure 3) to show that an exponential dependence on the\nnumber of actions $A$ is unavoidable in the regret and proves a lower bound  (Theorem 4.2).\n\nWeaknesses:\n\n1. This paper lacks numerical analysis to test their theoretical results.\n2. The gap between upper bound and lower bound may be too loose for Markovian Per-stage Disclosure.", "other_comments_or_suggestions": "1. In the definition of three regrets, is there a typo? I guess $T$ and $K$ should be the same thing, the number of episodes.\n2. It would be better to show some numerical results to verify the bounds.", "questions_for_authors": "1. Is it possible to add some numerical results to verify your results?\n2. Is it possible to reduce the bound gaps, i.e. the exponential term $2^{A}$ and $2^{A/2}$, between Theorem 4.1 and 4.2?\n3. Is it possible to reduce the lower bound condition for $T$ with a factor $H^{10}$ in Theorem 5.1?\n\n## update after rebuttal: I raise the score from 2 to 3. Please refer to the comment below for reason.", "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": "", "extra_scores": {}}, {"review_id": "N6se6vdpnD", "reviewer": "Reviewer_EnYm", "summary": "This paper considers a tabular episodic reinforcement learning setting where the set of available actions is not fixed but varying over episodes, states and time steps. The paper studies two different ways the available actions are revealed to the learner: per-episode (available actions are revealed at the beginning of each episode) and per-stage (available actions are revealed only at each time step within an episode). In the per-episode regime, the paper proposes an algorithm that works for both adversarial and stochastic cases, and proves that its sleeping regret is not larger (in big-O notation) than standard RL. In the per-stage regime, the paper proves both lower and upper bounds in this regime for two different types of action distributions - one where the action availability is independent of past states and actions and one where the action availability is dependent on the previous state and action.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the time spent reviewing our work, and for having appreciated the significativeness of our work. We also thank the Reviewer for the comments on the results which we will use to expand the discussion on the results exploiting the additional page. Below, our answer to the Reviewer's questions.\n\n> Could the authors outline any significant technical challenges for the stochastic per-stage regime where the type of the distribution of the action availability is unknown? In particular, why doesn't your current estimation method for $C^{ind}$ works for $C^{markov}$? The distribution does not depend on the episode, so couldn't we simply estimate the conditional probability that an action might be available given the current state, previous state, previous action and previous availability?\n\nWe can adapt the design of the estimator for $C^{ind}$ to handle $C^{markov}$ by incorporating **conditional probabilities**, as the Reviewer correctly suggests. However, we conjecture that the resulting **regret bound** would remain **of the same order (with exponential dependence on $A$)** as in our current approach (Theorem 4.1), which relies on the **augmented MDP** approach.\nThat said, we believe our method allows us to avoid several non-strictly necessary calculations. We will add a comment on that in the paper.\n\n> Going back to the exponential dependency on $A$: the lower bound construction in Theorem 4.2 requires the availability to change based on previous availability $\\mathcal{A}\\_{k,h-1}$. Do you think the exponential dependency on A can be removed if the availability depends only on $s_{k,h}, s_{k,h-1}$ and $a_{k,h-1}$?\n\nYes, this dependency can be removed in the described scenario and the regret bound we would obtain should be **very similar** to the **independent availability** scenario, as the additional complexity in the Markovian case is generated, as the Reviewer properly noticed by looking at the lower bound construction, by the challenge in estimating the transition probabilities over the action sets. We will add a comment on that using the additional page. Thank you for pointing it out.", "claims_and_evidence": "This is a theory paper. All theorems are clearly stated and accompanied by their proofs in the appendix.", "methods_and_evaluation_criteria": "The approach is sound and the results are significant. There are two different notions of regret, one for the per-episode regime (Definition 3.1) and one for the per-stage regime (Definition 4.2). These notions of regret make sense.", "theoretical_claims": "For the upper bounds, I only skimmed their proofs in the appendix. Since the algorithms are based on the standard approach of optimism, all the upper bound proofs seem fine. \n\nFor the lower bounds, I did carefully check the proofs. In particular, I checked the proof of Theorem 4.2, which is the most important lower bound in this paper. I found the proof correct.", "experimental_designs_or_analyses": "The paper has no experiments.", "relation_to_broader_scientific_literature": "The paper extends the existing literature on sleeping bandits to reinforcement learning. Sleeping reinforcement learning is much harder than sleeping bandits, so the contributions of the paper are significant. The paper also make novel technical contributions in deriving optimistic algorithms for sleeping reinforcement learning. I find it interesting that such an optimism-based approach works (in the per-episode regime) even for adversarial action availability, which was not the case for sleeping adversarial bandits (e.g. Nguyen and Mehta, AISTATS 2024).\n\nIn the independent and stochastic per-stage regime, the paper proposes an approach that estimates the distribution of action availability. This approach is similar to existing approaches in sleeping bandits with stochastic availabilities (e.g. Saha et al, ICML 2020).\n\nThe most surprising result to me is that on both independent and Markovian stochastic per-stage regimes, the dependency on the number of actions is exponential. This was not the case in sleeping bandits.", "essential_references_not_discussed": "I am not aware of any missing important references.", "other_strengths_and_weaknesses": "No other comments.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "1. Could the authors outline any significant technical challenges for the stochastic per-stage regime where the *type* of the distribution of the action availability is unknown? In particular, why doesn't your current estimation method for $C^{ind}$ works for $C^{Markov}$? The distribution does *not* depend on the episode, so couldn't we simply estimate the conditional probability that an action might be available given the current state, previous state, previous action and previous availability?\n\n2. Going back to the exponential dependency on $A$: the lower bound construction in Theorem 4.2 requires the availability to change based on previous availability $\\mathcal{A}\\_{k,h-1}$. Do you think the exponential dependency on A can be removed if the availability depends only on $s\\_{k,h}, s\\_{k, h-1}$ and $a\\_{k,h-1}$?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces Sleeping Reinforcement Learning, in which available actions vary over time. It provides a theoretical analysis for this problem, along with algorithms with regret guarantees and matching lower bounds. While minor concerns were raised regarding exponential dependencies and missing lower bounds in specific cases, the rebuttal and added experiments addressed these concerns. Reviewers have converged on the significance of the contribution.
Decision: Accept (poster)