Horizon-Free Reinforcement Learning for Latent Markov Decision Processes
Authors: Runlong Zhou
Ruosong Wang
Simon Shaolei Du
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning theory
markov decision process
latent markov decision process

Abstract: We study regret minimization for reinforcement learning (RL) in Latent Markov Decision Processes (LMDPs) with context in hindsight. We design a novel model-based algorithmic framework which can be instantiated with both a model-optimistic and a value-optimistic solver. We prove an $\widetilde{O}\left(\sqrt{M \Gamma S A K}\right)$ regret bound where $M$ is the number of contexts, $S$ is the number of states, $A$ is the number of actions, $K$ is the number of episodes, and $\Gamma \le S$ is the maximum transition degree of any state-action pair. The regret bound only scales logarithmically with the planning horizon, thus yielding the first (nearly) horizon-free regret bound for LMDP. Key in our proof is an analysis of the total variance of alpha vectors, which is carefully bounded by a recursion-based technique. We complement our positive result with a novel $\Omega\left(\sqrt{M S A K}\right)$ regret lower bound with $\Gamma = 2$, which shows our upper bound minimax optimal when $\Gamma$ is a constant. Our lower bound relies on new constructions of hard instances and an argument based on the symmetrization technique from theoretical computer science, both of which are technically different from existing lower bound proof for MDPs, and thus can be of independent interest.

HORIZON-FREE REINFORCEMENT LEARNING FOR LA- TENT MARKOV DECISION PROCESSES
Anonymous authors Paper under double-blind review
ABSTRACT
We study regret minimization for reinforcement learning (RL) in Latent Markov Decision Processes (LMDPs) with context in hindsight. We design novel model-based algorithmic framework which can be instantiated with both a model- optimistic and a value-optimistic solver. We prove an Ô (VVTSSAK) regret bound where M is the number contexts, is the number of states, A is the number of actions, K is the number of episodes, and I & S is the maximum transition degree of any state-action pair. The regret bound only scales logarith- mically with the planning horizon, thus yielding the first (nearly) horizon-free regret bound for LMDP. Key in our proof is an analysis of the total variance alpha vectors, which carefully bounded by recursion-based technique. We complement our positive result with novel 22 (VMSAA) regret lower bound with 2, which shows our upper bound minimax optimal when is a constant. Our lower bound relies on new constructions of hard instances and an argument based on the symmetrization technique from theoretical computer science, both of which are technically different from existing lower bound proof for MDPs, and thus can be of independent interest.
INTRODUCTION
One of the most popular model for Reinforcement LearningRLL) is Markov Decision Process (MDP), in which the transitions and rewards are dependent only on current state and agent's ac- tion. In standard MDPs, the agent has full observation of the state, so the optimal policy for the agent also only depends on states (called a history-indepennenu policy). There is a line research on MDPs, and the minimax regret and sample complexity guarantees have been derived.
Another popular model is Partially Observable MDPs (POMDPs) in which the agent only has partial observations of states. Even though the underlying transition is still Markovian, the lower bound for sample complexity has been proven to be exponential in state and action sizes. This is in part because the optimal policies for POMDPs are history-dependent.
In this paper we focus on a middle group between MDP and POMDP, namely Latent MDP (LMDP). collection of MDPs sharing the same state and action spaces, but the transitions and rewards may vary across them. Each MDP has a probability to be sampled at the beginning of each episode, and it will not change during the episode. The agent needs find policy which works well on these MDPs in an average sense. Empirically. LMDPs can be used for wide variety of applications eu al. [ lakovleva al. 2020 Finn al. 2018 Ramamoorthy et al., 2013 Doshi Velez & Konidaris| 2016 Yao et al.) 2018). In general, there exists policy that optimally on every single MDP simudtaneously. so this task is definitely harder than MDPs. On the other hand, LMDP is special case of POMDP because for each MDP, the unobserved state is static in each episode and the observable state is just the state MDP.
An LMDP can be viewed
Unfortunately, for generic LMDPs, there exists exponential sample complexity lower bound (won et al. 202T), so additional assumptions are needed to make the problem tractable. In this paper, consider the setting that after each episode ends, the agent will get the context on which MDP it played with. Such information is often available. For example, in a maze navigation task. the location of the goal state can be viewed the context.

---

In this setting, Kwon et al. (2021) obtained MS AMSAAHH AHK) regret upper bound where M is the number of contexts, S is the number of states, A is the number of actions, H is the planning horizon, and K is the number of episodes. They did not study the regret lower bound [ To benchmark this result, the only available bound θ (VSAK) from standard MDP by viewing MDP as special case of LMDP.
Comparing these two bounds, we find significant gaps: Is the dependency on M in LMDP nec- essary? @ The bound for MDP is (nearly) horizon-free (no dependency on H), is the polynomial dependency on H in LMDP necessary? @ The dependency on the number of states is vS for MDP but the bound in Kwon et al. (202T) for LMDP S.
In this paper, we resolve the first two questions and partially answer the third.
1.1 MAIN CNTRIBUTIONS AND TECHNICAL NOVELTIES
We obtain the following new results:
Near-optimal regret guarantee for LMDPs. We present an algorithm framework for LMDPs with context in hindsight. This framework can be instantiated with a plug-in solver for planning problems. We consider two types of solvers, one model-optimistic and one value-optimistic, and prove their regret bound to be Ô (v MTTSAK) where I & S is the maximum transition degree of any state-action pair. Compared with the result in Kwon et al. (202I), ours only requires the total reward to be bounded whereas they required a bounded reward for each step. Furthermore, we improve the H -e-eeendeecee from /H H to logarithmic, making our bound (nearly) horizon-free Lastly, our bound scales with v ST, which is strictly better than S in their bound.
The main technique of our model-optimistic algorithm is to use Bernstein-type confidence set on each position of transition dynamics, leading to a small Bellman error. The main difference between our value-optimistic algorithm and K Koo et al. (202T)'s is that we use a bonus depending on the variance of next-step values according to Bennett's 's inequality, instead of using Bernstein's ' inequality. It helps propagate the optimism from the last step to the first step, avoiding the H- dependency. We analyse these two solvers in a unified way, as their Bellman error are of the same order.
New regret lower bound for LMDPs. We obtain novel Ω (VMSAK) regret lower bound for LMDPs. This regret lower bound shows the dependency M is necessary for LMDPs. Notably the lower bound also implies Ô (v (VMTSAK) upper bound optimal up vT factor. Furthermore, our lower bound holds even for r = 2, which shows our upper bound is minimax optimal for a class of LMDPs with O(1).
Our proof relies on new constructions of hard instances, different from existing ones for MDPs (Domingues et al., 202T). In particular, we use two-phase structure to construct hard in- stances (cf. Figure TT. Furthermore, the previous approaches for proving lower bounds of MDPs do not work on LMDPs. For example, in the MDP instance of Domingues et al.) (202T), the random- ness comes from the algorithm and the last transition step before entering the good state bad state. In an LMDP, the randomness of sampling the MDP from multiple MDPs must also be considered. Such randomness not only dilutes the value function by averaging the pushforward measure (see Page 3 of Domingues et al. (202I) into M parts. As a result, the M 22021) and that Equation (10) cancels out - the final lower bound does not contain M. To overcome this, we adopt the symmetrization technique from theoretical computer science. This novel technique is helps generalize the bounds from a single-party result to a multiple-pane party result, which may give rise to a tighter lower bound.
each MDP, but also divides
terms KL divergence in Equation (2) of Domingues
'Their original bound is DP with the scaling that the reward from each step is bounded by 1. We rescale the reward to be bounded by 1/H in order to make the total reward from each episode bounded
by 1, which is the setting we consider.
2

---

2 RELATED WORK
LMDPs.
As shown by Steimle et al. history dependent and P-SPACE hard to find.
(2021). in the general cases, optimal policies for LMDPs are This is different from standard MDP cases where there
always exists an optimal history-indlpeendent policy. However, even finding the optimal history-
independent policy is NP-hard (Littman 1994 Chades et al. (2012) provided heuristics for finding
the optimal
policy.
Kwon al. (222)) investigated the sample complexity and regret bounds of LMDPs. Specifically, they presented an exponential lower-bound for general LMDPs without context in hindsign, and then they derived an algorithm with polynomial sample complexity and sub-linear regret for two special cases (with context in hindsight, or d-strongly separated MDPs).
LMDP has been studied as a type of multi-task RL Taylor & Stone 2009 Brunskill Li 2013 Liu
et al. 2016 Hallak et al. 2015). It has been applied to model combinatorial optimization problems
(Zhou et al. 2022). There are also some related studies such as model transfer (Lazaric 2012
Zhang & Wang 202I) and contextual decision processes (Jiang et al.) 2017). In empirical works,
LMDP has has wide applications in multi-task RL (Yu et al. (2020), meta [alkollev et al. (2020);
Finn al. (2018), latent-variable MDPs (Ramamoorthy al. (2013) and hidden parameter MDPs
Doshi Velez & Konidaris 2016
Yao et al. 2018).
Regret Analysis for MDPs. LMDPs are generalizations of MDPs, so some previous approaches to solving MDPs can provide insights. There is a long line of work on regret analysis for MDPs (Azar eet al.
2017 Dann et al. 2017 2019: Zanette & Brunskill 2019, Zhang et al., 2021a). In this paper, focus on tome-homog,neous, finite horizon, undiscounted MDPs whose total reward is upper-bounded by 1. Recent work showed in this setting the regret can be (nearly) horizon-free for tabular MDPs Waan et al. (2020); Zhang al. (2022) 202 2020); Ren al. (2021). Importantly these results indicate RL may not be more difficult than bandits in the minimax sense. More recent work generalized the horizon-free free results to other MDP problems (Zhang et al. 2021b] Kim al., 2021 Tarbouriech et al. 202T Zhou & Gu (022). However, all existing work with horizon- free guarantees only considered single-envirommen problems. Ours is the first horizon-free guarantee that goes beyond MDP.
Neu & Bike-Burkepae (2020) summarized up the "optimism in the face of uncertainty" (OFU) principle in RL. They named two types of optimism: @ model-optimistic algorithms construct confidence sets around empirical transitions and rewards, and select the policy with the highest value in the best possible models in these sets. @ value-optimistic algorithms construct upper bounds the optimal value functions, and select the policy which maximizes this optimistic value function. Our paper follows their idea and provide one algorithm for each type of optimism.
PROBLEM SETUP
In this section, we give formal definition of Latent Markov Decision Processes (Latent MDPs)
Notations. For any event E, we use [[ to denote the indicator function, i.e., 1[ if E holds and 1[8] = 0 otherwise. For any set X, we use A(X) to denote the probability sim- plex over X. For any positive integer n, we use [n] denote the set (1. n... For any probability distribution P. we use (P)
|Pl to denote the size of support of P, i.e., 0]. There are three ways to denote a d-dimensional vector (function): sup- pose is any parameter, x(p) (I)(P), x2(p)..... II((p) if the indices are natural numbers, a(-lp) = (x), (()lp)))))) xr(alp)) and a(p) = (a(pi)) a(p2),,
L [[P(x)
(pia)) if the indices are from the set I (21,22...., id). For any number q. we use x to denote the vector (æ 22, 22..... .......... ..2......?)............." =²))- For two d-dimensional vectors x and y. use y Σ. I.8h to denote the inner product. If is probability distribution, use V(z,)) v) E Ir 1/+ empirical variance. We use
y) x (v²)) TT) 2 to denote the as a log term where is the confidence parameter.
21n 2MSAHK 0
3

---

3.1 LATENT MARKOV DECISION PROCESS
Latent MDP Kwon et al. 2021) is collection of finitely many MDPs M = MM,MMM,.....
where M- = M.. All the MDPs share state set S, action set A and horizon H. Each MDP Mm = (S,A, H, mm Pm: Rm) has its own initial state distribution Vmm E ASS), transition model [0, 1]. Let w1, W2,..... WM
P'm SSAA (SS) and a deterministic reward function R. xx A
be the mixing weights of MDPs such that Wm > for any m and Σ m==1 Wm =
Denote S | A |A| and I maXm,e, supp (-fm(1ss,)) a)). I can be interpreted as the maximum degree of each transition, which is a quantity our regret bound depends on. Note we always have r S. In previous work, [attimore & Hutter (2012) assumes T 2, Fruit et al. (2020) also has a regret bound that scales with
In the worst case, the optimal policy of an LMDP is history-dependen and is PSPACE-han to find (Corollary and Proposition 3 in [Steimle et al. (201)). Aside from computational difficulty, storing history-dependent policy needs a space which is exponentially large, so it is generally impractical. In this paper, we seek to provide a result for any fixed policy class II. For example, we can have II to be the set of all previous work (Kwon et al. (22TT) we assume access to oracles for planning and optimization. See Section for the formal definitions.
deterministic policies to alleviate the space issue. Following
We consider an episodic, horizon and undiscounted reinforcement learning problem on LMDPs. In this problem, the agent interacts with the environment for K episodes. At the start of every episode, one MDP Mm E .M is randomly chosen with probability Wm. Throughout the episode, the true context hidden. The agent can only choose actions based on the history infor- mation up until current time. However, the end of each episode (after H steps), the agent gets revealed the true context m. This permits an unbiased model estimation for the LMDP. As in (Chhen et al. (2020), the central difficulty is to estimate the transition, For simplicity, we assume that w, V and R are known to the agent, because they can be estimated easily. The assumption of deterministic rewards is also for simplicity. Our analysis can be extended to unknown and bounded-support reward distributions.
also focus on learning P only.
3.2 VALUE FUNCTIONS, Q-FUNCTIONS AND ALPHA VECTORS
By convention, the expected reward of executing a policy on any MDP can be defined via value function V and Q-function Q. Since for MDPs there is always an optimal policy which is history- independent, V and Q only need the current state and action as parameters.
However, these notations fall short of inseeneindde policies under the LMDP setting. The full information is encoded in the history, so here we use a more generalized definition called alpha vector (following notations in Kwon et al. (2021)) )). For any time /. > 1, let he (s, a, 1:t-18 be the history up until time Define Hi as the set of histories observable at time step 1, and H
off Hr as the set of all possible histories. We define the alpha vectors at (h) for (m, h) E [M] x H as follows:
H Rum (Se (tr)
0 (h) E
Σ
Mm, T,, ln).
a (h, a) =
Rm( :=
Σ
Mm v, (he, ar) (li, a)
The alpha vectors are indeed value functions and Q-functions on each individual MDP.
Next, we introduce the concepts of belief state to show how to do planning in LMDP. Let bm denote the belief state over M MDPs corresponding to a history h, i.e. the probability of the true MDP being Mm conditioned on observing history h. We have the following recursion:
Wm 1/ (8)
(m) Pm (8' 18, I) Rm, (s.a)]
bm (y((s)
and bhaarrs)) Σm= bm (h) Pm (5'18, a) a) (m a))
mm'==1 Win! Pm (8)
The value functions and Q-functions for LMDP is defined via belief states and alpha vectors:
(*( b(h) T (h)) and @*t(h,a) b(h) To T ("((ha))
4

---

Direct computation (see Appendix B.1 gives
M
(h)
Σ x(alh) b(h)TR(s, R(s, + Σ
Σ
b (m) Rmc (s,a)]V* a))rr(hars)))
S'ES,T
(Q"(haa)
So planning in LMDP can viewed as planning belief states. For the optimal history-dependent policy, we can select
M
(h) arg max a
b(h) ((ssa)++ E Σ
bm (s's Re (s, a)] a)))"((arrs)) (1)
SES, mn
using dynamic programming descending order of h's length.
3.3 PERFORMANCE MEASURE.
We use cumulative regret to measure the algorithm's performance. The optimal policy is n arg max V*, which also does know the context when interacting with the LMDP. Suppose the agent interacts with the environment for K episodes, and for each episode k policy r² is played. The regret is defined
Regret ( := KV
v
4 MAIN ALGORITHMS AND RESULTS
In this section, we present two algorithms, show their minimax regret guarantee. The first is to Bernstein confidence set transition probabilities, which was first applied to SSP in Cohen jet al. (2220) to derive a horizon-free regret. This algorithm uses a bi-level optimization oracle: for the inner layer, oracle needed to find the optimal policy inside II under given LMDP; for the outer layer, an oracle finds the best transition inside the confidence set which maximizes the optimal expected reward. The second (Zhang et al. 2021a) to LMDPs. This algorithm requires an oracle to solve an LMDP with dynamic bonus: the bonuses depends the variances of the next-step alpha vector. Both algorithms enjoy the following regret guarantee.
adapt the Monotoic Value Propagation (MVP) algorithm
Theorem 1. For both the Bernstein confidence set for LMDP (Algorithm D combined with Algo- rithm 2 and the Monotonic Value Propagation for LMDP (Algorithm Sonrrihhmmmmmmmneee combined with Algorithm 3
with probability at least 1 5, have that
Regret(K) ( VMTSA
MSAHK 8
AM
MMSAK
8
As we have discussed, our result improves upen Kwon al. (202)) and has only logarithmic depen- dency the planning horizon H. We also have lower order which scales with S We note that even the standard MDP setting, it remains a major open problem how to obtain minimax optimal regret bound with no lower order term (Zhang et al. 2021a).
Below we describe the details of our algorithms.
Algorithm framework. The two algorithms introduced in this section share framework for timating the model. The only difference between them is the solver for the exploration policy. The framework is shown in Algorithm I Our algorithmic framework estimates the model (cf. Line 14 in Algorithm [T and then selects a policy for the next round based on different oracles (cf. Line 18 in Algorithm Tp. Following Zhang al. (002aa). pair in every MDP to update the estimation and exploration policy.
doubling schedule for each state-action
Common notations. Some of the notations have been introduced in Algorithm 1 but for reading convenience we will repeat the notations here. For any notation, we put the episode number the superscript. For any observation. we put the context m in the subscript. The alpha vector and value function for the optimistic model denoted using extra "*"
put the time step t in the subscript. For any model component,

---

Algorithm Algorithmic Framework for Solving LMDPs
1: Input: Number of MDPs M, state space S, action space A, horizon H; policy class II; confi-
dence parameter 8.
2: Set an arbitrary policy x², initialize all N with 0 and set constant 2 In (2MSARK ARK
5
3: for 1,2.... K do
4: for 1, do
5: Observe state 8
6: Choose action at (st).
7: end for
8: Observe state stt and get m hindsight.
9:
for = 1, 1,2..., H. do
Set nm (5) ai N. Ren (sk (sk,at) 2' then
nm (st at) and nm (5t 115t a.)) - am
12:
Set TRIGGERED TRUE.
Set Nm (st, at) Pmnk (s+: a.).
(1 for all s' S. Set ( (s at) (of(a
14:
15:
end
16:
end for
17:
if TRIGGERED then
Set π k+1 Solver () (by Algorithm or Algorithm 3).
19: else
Set π ++1 xt.
21: end if
22:
end for
4.1 BERNSTEIN CONFIDENCE SET OF TRANSITIONS FOR LMDPS
We introduce a model-optimistic approach by using a confidence set transition probability.
Optimistic LMDP construction.
The Bernstein confidence set constructed as below:
ph+1 P.: (P.. (Pmm ph) (d' (d'(s.a) < $2
Ph (s')a, NE (s.
5 NK (x.
s,,,),
[M]] S x AxS
(2)
Notice that do not change the reward function, so we still have the total reward of any trajectory upper-bounded by 1.
The policy solver is Algorithm 2 It solves two-step optimization problem on Line for inner problem, given a transition model P and other known quantities w, v, R, needs planning oracle find the optimal policy: for the outer problem, it needs to find the optimal transition model. For planning, we can use the method presented in Equation (I). For the outer problem, we
Policy solver.
Extended Value Iteration in Auer et al. (2008); Fruit et al. (2020); Filippil et al. (2010): Cohen et al. (2020). For notational convenience, we denote the alpha vectors and value functions calculated by pk and Th as & and V'r
Algorithm 2 Solver----Bernstee
1: Construct pk+1 using Equation
2: Find pk11 arg pa max VB
3: Find k arg max V
4: Return: x 1+1
4.2 MONOTONIC VALUE PROPAGATION FOR LMDP
We introduce a oatiniipiimistic approach by calculating a variance-dependent bonus. This tech- nique was originally used solve standard MDPs (Zhang et al. 2021a).

---

Optimistic LMDP construction. The optimistic model contains bonus function, which is in- ductively defined using the next-step alpha vector. In episode k, or any policy n, assume the alpha vector for any history with length t + 1 is calculated, then for any history h with length t, the bonus defined as follows:
PR (-)s)s, V Pk (-|s,, a), an 0. (har-))
supp
16.t
B (h, = max
(3)
N Nm. (s.
N (s, a)
where r = (s, a). Next, the alpha vector of history h is:
(h) = min (s, + Btt (h, a) + (-1s, a) am (har.), 13. where a = v(h). (4)
Finally, the value function is:
M
Wm (m)mm()) (8)
(5)
75 SES
Policy solver. The policy solver is in Algorithm 3 It finds the policy maximizing the optimistic value, with dynamic bonus function depending on the policy itself. This solver is tractable if we only care about deterministic policies in IT. This restriction is reasonable because for the original LMDP there always exists an optimal policy which is deterministic. Further, according to the proof of Lemma [3 we only need a policy which has optimistic value less than that of the optimal value. Thus, there always exists an exhaustive search algorithm for this solver, which enumerates each action at each history.
Algorithm 3 Solver L------MV MVP
1: Use the optimistic model defined in Equation Equation (4) and Equation (
2: Find x*+ arg max V"
3: Return: ++1
5 REGRET LOWER BOUND
In this section, we present regret lower bound for the unconstrained policy class, i.e., when II contains all possible history-dependent policies.
First, we note that this lower bound cannot be directly reduced to solving M MDPs (with the context revealed at the beginning of each episode). Because simply changing the time of revealing the context results in the change of the optimal policy and its value function.
transform the problem of context in hindsight into problem of essentially context being told beforehand, while not affecting the optimal value function. To achieve this, we can use a small portion states to encode the context at the beginning, then the optimal policy extract information from them and fully determine the context.
At high level, our approach
After the transformation, we can view the LMDP as a set of independent MDPs, so it is natural to leverage results from MDP lower bounds. Intuitively, since the lower bound of MDP is v SAK, and each MDP assigned roughly 3 episodes, the lower bound LMDP is M \ SA
K v MSAK.
M
To formally prove this, we adopt the symmetrization technique from the theoretical computer science community (Phillips al., 2012, Woodruff & Zhang, 2014, Fischer et al.) [017 |Vempala et al.) 2020). When an algorithm interacts with an LMDP, can focus each MDP, while viewing the interactions with other MDPs as irrelevant we hard code the other MDPs into the algorithm, deriving algorithm for MDP. In other words, and they are all symmetric to the algorithm's 's view. So, the regret can be averagely distributed to each MDP.
insert MDP into any of the M positions,
The main theorem shown here, before we introduce the construction of LMDP instances. Its proof placed in Appendix B.4

---

Theorem 2. Assume that > 6, A and M < 1. For any algorithm there exists LMDP Mr such that, for 3 1M(M² + A),,, its expected regret in Mr after K episodes satisfies
R(Mx: n. K) E [v vh) Mn. = (V(VVAA))
Several remarks are in the sequel. ① This is the first regret lower bound for LMDPs with context in hindsight. To the best of our knowledge, the introduction of the symmetrization technique is novel to the construction of lower bounds in the field of RL. @ This lower bound matches the minimax regret upper bound (Theorem [ up to logarithm factors, because in the hard instance construction
T= 2. For general cases, our upper bound is optimal up to a vT factor. There is limitation of M. which could be at most _ I, though an exponentially large M is not practical.
5.1 HARD INSTANCE CONSTRUCTION
Since M < [ we can always find an integer d, such that d1 < and & d₁!. Since S > 6 and d & S. we can always find an integer d2 such that d2 >/ 1 and 2d - 1 & S - d1 2 24+1 1. We construct two-phase structure, each phase containing d, and d2 steps respectively.
The hard instance uses similar components as the MDP instances in Domingues et al. (202T). We construct a collection of LMDPs C := {Mie ax) aa") [ x [A]"), where define L 24:-1 O(S). For fixed pair (E. (f", ,a)) ((Ci, E ..,,.., (n)) (a 02 (m,)) we construct
the LMDP Miee .a)) as follows.
5.1.1 THE LMDP LAYOUT
All MDPs the LMDP share the same logical structure. Each MDP contains two phases: the encoding phase and the guessing phase. The encoding phase contains dj states, sufficient for en- coding the context because M & d,l. The guessing phase contains a number guessing game with C = LA (SSA) choices. If the agent makes correct choice, it receives expected reward slightly larger than 1.8 Otherwise, it receives an an expected reward of 1 3.
5.1.2 THE DETAILED MODEL
Now we give more details about our construction. Figure I shows an example of the model with M 2, S 11, arbitrary A > 2 and H > 6.
States.
The states the encoding phase are cI,..., Cd. The states in the guessing phase are $1,... Sy where N = "n 2' = 24 - 1. There is good state g for reward and terminal state All the unused states can be ignored.
Transitions. The weights are equal, i.e., Wm. M. We assign unique integer in [M] to each MDP as context. Each integer m is uniquely mapped to permutation (m)) (ar (m), o.))..z(())) (2(m)..... oa, oa,(m)) (m)). Then the initial state distribution is pm pm (m)) = 1. The transitions for the first di steps are: for any (m, a) [M] x A.
P (e. Ca,(m), a) 1, V1 <i<idd This means, the encoding phase, whatever the agent does irrelevant to the state sequence observes.
(m Ca (ma) a) 1.
The guessing phase is binary tree which we modify from Section 3.1 Domingues et al. (021) (here equal each action to an integer in [A]: for any (m, a) E [M]] A.
P (S2i (a mod 2) 8; a) 1, V1 < i 24 1.
For the tree leaves L = {st 2d < < 2d - 1} (notice that [C| = L), we construct: for any
(m, [M] L A.
1
(t se, a) = 2
el[e Cr, a and Pmng Se, a) = + =l[E = E a = ainl.
8

---

MDP1
MDP2
62
Encoding phase
Guessing phase
53
$2
9
9
Figure 1: Illustration of the class of hard LMDPs used in the proof of Theorem Solid arrows are deter- ministic transitions, while dashed arrows probabilistic transitions. The probabilities written aside of the transitions. For any of the MDP, the agent first goes through an encoding phase, where observes sequenec states regardless what actions take. state sequence is different for each MDP, so the agent can fully determine which context is in after this phase. When in the guessing phase, the agent needs to travel through binary tree until it gets to some leaf. Exactly one of the leaves are "correct", and only performing exactly one of the actions the correct leaf yields expected higher reward.
Recall that we denote = LA as the effective number of choices. The agent needs to first find the correct leaf by inputting its binary representation correctly, then choose the correct action.
The good state temporary between the guessing phase and the terminal state: if the agent at and makes any action, it enters f. The terminal state is self-absorbing. For any (m, a) [M] A.
Ptn(t a) 1, (m a,a)= =
All the unmentioned probabilities are O. Clearly, this transition model guarantees that (upp(PP..(-ss.aa)) a)) for any pair of (m, s, a) [M] x S A.
The rewards. The only non-zero rewards are (g, a) = 1 for any (m, a) E [M] x A. Since this state-action pair is visited at most once in any episode, this reward guarantees that in single episode the cumulative reward either or 1.
CONCLUSION
In this paper, we present two different RL algorithms (one model-optimistic and one value- optimistic) for LMDPs with context in hindsight, both achieving ((VMTSAK) regret. This is the first (nearly) horizon- free regret bound for LMDP with context in hindsight. We also provide regret lower bound for this setting, which 22( ((VM VMSAK) In this lower bound, r' 2, so the upper bound is minimax optimal for the subclass of LMDPs with constant I'. One future direction obtain a minimax regret bound for LMDPs for the (SS) case. For example, can we derive a regret lower bound of Ω( M AK)? On the other hand, it is also possible to remove the vT in our upper bound. We believe this will require properties beyond the standard Bellman-optimality condition for standard MDPs.
REFERENCES
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances neural information processing systems, 21, 2008.

---

Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In ICML, 2017.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. ArXiv, abs//330.6841 2013.
I. Chades, Josie Carwardine, Tara G. Martin, Sam Nicol, Régis Sabbadin, and Olivier Buffet. Momdps: A solution for modelling adaptive management problems. In AAAI, 2012.
Alon Cohen, Haim Kaplan, Y. Mansour, and Aviv Rosenberg. Near-optimal regret bounds for stochastic shortest path. In ICML, 2020.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In NIPS, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic re- inforcement learning in finite mdps: Minimax lower bounds revisited. In Vitaly Feldman, Ka- trina Ligett, and Sivan Sabato (eds.), Proceedings of the 32nd International Conference on Al- gorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pp. URL
578-598. PMLR, 16-19 Mar 2021.
httprceeedings.....rrrss....... press/v1321
domingues21a: html
Finale Doshi-Velez. and George Konidaris. Hidden parameter markov decision processes: A semi- parametric regression approach for discovering latent task parametrizations. In IJCAI: proceed- ings of the conference, volume 2016, pp. 1432. NIH Public Access, 2016.
Sarah Filippi, Olivier Cappé, and Aurélien Garivier. Optimism in reinforcement learning and kullback-leibler divergence. In 2010 48th Annual Allerton Conference on Communication, Con- trol, and Computing (Allerton), pp. 115-122. IEEE, 2010.
Chelsea Finn, Kelvin Xu, and Sergey Levine. Probabilistic model-agnostic meta-learning. Advances in neural information processing systems, 31, 2018.
Orr Fischer, Shay Gershtein, and Rotem Oshman. On the multiparty communication complexity of testing triangle-freeness. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 111-120, 2017.
Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Improved analysis of ucr12 with empirical bernstein inequality. arXiv preprint 20li::0000.0045566 2020.
Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. ArXiv, abs/1502.02255,, 2015.
Ekaterina lakovleva, Jakob Verbeek, and Karteek Alahari. Meta-learning with shared amortized variational inference. In International Conference on Machine Learning, pp. 4572-4582. PMLR, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire Con- textual decision processes with low bellman rank are pac-leamable. In International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. arXiv preprint arXiv:2111.03289, 2021.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Regret guarantees and lower bound, 2021.
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In International Conference on Algorithmic Learning Theory, pp. 320-334. Springer, 2012.
10

---

Alessandro Lazaric. Transfer in reinforcement learning: A framework and survey. In Reinforce- ment Learning, 2012.
Michael L Littman. Memoryless policies: Theoretical limitations and practical results. In From Animals to Animats Proceedings of the third international conference on simulation of adaptive behavior, volume 3. pp. 238. Cambridge, MA, 1994.
Yao Liu, Zhaohan Daniel Guo, and Emma Brunskill. Pac continuous state online multitask rein- forcement learning with identification. AAMAS, 2016.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample-variance penal- ization. In COLT, 2009.
Gergely Neu and Ciara Pike-Burke. unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33:1392-1403, 2020.
Jeff M Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty commu- nication complexity, made easy. In Proceedings of the twenty-third annual ACM-SIAM symposium Discrete Algorithuss, pp. 486-501. SIAM, 2012.
Subramanian Ramamoorthy, MM Hassan Mahmud, Benjamin Rosman, and Pushmeet Kohli. Latent-variable mdp models for adapting the interaction environment of diverse users, 2013.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. Advances in neural information processing systems, 14:15621-15534, 2021.
Lauren N Steimle, David L Kaufman, and Brian Denton. Multi-model markov decision processes. IISE Transactions,
2021.
Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter-free and towards horizon-free regret. vol- ume 34, 2021.
Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(7), 2009.
Santosh S Vempala, Ruosong Wang, and David P Woodruff. The communication complexity of optimization. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium Discrete Algo- rithms, pp. 1733-1752. SIAM, 2020.
Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade. Is long horizon reinforcement learn- ing more difficult than short horizon reinforcement learning? arXiv preprint urXiv:2005.0052 2020.
David P Woodruff and Qin Zhang. An optimal lower bound for distinct elements in the message passing model. In Proceedings of the twenty-fitth annual ACM-SIAM symposium on Discrete algorithms, pp. 718-733. SIAM, 2014.
Jiayu Yao, Taylor Killian, George Konidaris, and Finale Doshi Velez. Direct policy transfer via hidden parameter markov decision processes. In LLARLA Workshop, FAIM, volume 2018, 2018.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference robot learning, pp. 1094-117 110.. PMLR, 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependeet regret bounds in reinforcement learning without domain knowledge using value function bounds. In ICML, 2019.
Chicheng Zhang and Zhi Wang. Provably efficient multi-task reinforcement learning with model transfer. ArXiv, abs/2107 107.0862,, 2021.
Zihan Zhang, Simon S Du, and Xiangyang Ji. Nearly minimax optimal reward- -feee reinforcement learning. arXiv preprint 1rXiv:2010.05901, 2020.

---

Zihan Zhang, Xiangyang Ji, and Simon Shaolei Du Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In COLT, 2021a.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342-4355, 2021b.
Zihan Zhang, Xiangyang Ji, and Simon Du. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory, pp. 1858-3904. PMLR, 2022.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint arXiv:2205. 1507, 2022.
Runlong Zhou, Yuandong Tian, Yi Wu, and Simon S Du Understanding curriculum learn- ing policy optimization for solving combinatorial optimization problems. arXiv preprint arXiv:2202.05423, 2022.
12

---

A TECHNICAL LEMMAS
Lemma 3 (Anytime Azuma, Theorem D.1 in Cohen al. (020)). Let (X,) be martingale difference sequence with respect to the filtration (Fa)n- such that [X,, & B almost surely. Then with probability al least 5,
X & B n
Bynnn
8 vl 1.
Lemma 4 (Bennett's Inequality, Theorem in Maurer & Pontil 2009)). Let Z, Zi..... Zn be i.i.d. random variables with values in [0, b] and let O. Define have
[ = E E[ Then we
24 Z In(2/0)
b (2(6))
P
E E
Z
& 6.
Lemma 5 (Theorem in Maurer & Pontil (009)). ) Let Z, Zn ....... Zn (n E 2) be i.i.d random
variables with values in [0, b] and let >> 0. Define = Z. and V. 1 1 (2: 2)2. Then we have
1
2v, In(2/0)
(2
P
E
Z
Z
n
3(n 1)
Lemma (Lemma 30 Tarbouriech et al. (2021)). ). Les ( (M)) )o be martingale such that Mn
and MM,- -M,-ll cfror some 0 and any 1. Let Var, _ [[ M2 2 1]
for n. O, where Fu .., Mn). Then for any positive integer n and E (0, (( 1/2n2]. we have that
Mal > 2//Var (loga (nce) + In(2/)) + 2 (og2(nc²) + In(2/8) + 20(logg (nc?) + 1n In(2/6)) $ 6.
Lemma (Lemma 1l Zhang et al. (202 Let Ån A2, 0, As and 1' log2 d1 Let a1 ............................ Og be non-negane non-negative reals such that a; & a and a d2v a/+1 2 As + for any
1 & i & V. Then we have that a₁ & max((22 + /22 + Xa)², A288828888 + >a)-
B SKIPPED PROOFS
B.1 OMITTED CALCULATION
Here we give the details for ommitted calculations.
(*(h) Σ T(a/h)
(())R(sso) Σ
Σ
by (b) asaaa
A
S' m011
M
Σ T(alh)
b(h)TR(s R(s,(s Σ
Σ
by ( Rn (s, a)l
Σ
bm (harsss') )a (hars')
2'E8,r
M
Σ T(ahh)
b(h) (R), o) Σ
(m) Re (s, (harr)))))))))
8'E8,r
B.2 UNIFIED ANALYSES OF ALGORITHM|
[ ALGORITHM AND ALGORITHM 3
In this subsection, we present the proof of Theorem countered with some lemmas, the proofs of lemmas skipped and deferred Appendix B.3
I by showing each step. However, when en-
13

---

Good events. The entire proof depends heavily the good events defined below in Definition g They show that the estimation of transition probability is very close to the true value. We show in Lemma@9thr that they happen with high probability. Definition 8 (Good events). For every episode k, define the following events:
22
v(m, x)m Ax (ph Pm)) (d'1s,a) & 2
Ph: (s'ls, a.)e
+ N (N,(,,))
5c
(6)
(H.
Pm)) (5 (5/1s, 2 &(, [M] 8 A 8 PPn
2Pm((')
(7)
N (s, (8,
Further, define Ω =
K 0k- St and Ω2 = 14
Lemma 9. P[2)] P[22] 3 1 - 8.
Assume that good events hold, then we have the following useful property:
Lemma 10. Conditioned on Ωr we have that for any (m, 8, a, k) e [M] x S x A x [K], and any S-dimensional vector a such that | 1,
supp (Pm((1s. V (P))(1),,)))a))
(P= (1ss 22
5S
N8 Nh(ss,)
N ( a)
Similarly, conditioned on S2z, we have that,
(poz -mnn) (-18,a)
2supp (P Pm a)) V (P (18,
S N No (s. a)
N (s, a)
Trigger property. Let K. be the set of indexes of episodes in which no update is triggered. By the update rule, is obvious that KK & A (HK) + 1) & MSA. Let to(k) be the first time an update is triggered in the k-th episode if there is an update in this episode and otherwise H + 1. E XC) and X' {(k, : & IC lo(k) & H}. We will study quantities multiplied by the trigger indicator 1[[k, L) $ XJ. which we denote using an extra
Define X, (k)))
We will encounter special type of summation, so we state here.
Lemma 11. Let fut 3 (k, t) e [K] x [H] be a group of weights, then
[[ t) $ X] NE (st a
w ([(k,t) $
H
< 3MSA
3MSA
Σ
w [(k,t) t) $ X1.
NE (st of)
B.2.1 OPTIMISM
As a standard approach, we need to show that both Algorithm and Algorithm 3 have optimism in value functions.
For Algorithm 2 is straightforward. For each episode k we choose the optimistic transition ps with the maximum possible value. Lemma 9 shows that with probability at least 1-6 6, P, holds, hence the true transition
inside the confidence set pk for all ie [K]. Therefore, 1 > V
Algorithm 3 relies on an important function introduced by Zhang et al. (2021a), so we cite it here: Lemma 12 (Adapted from Lemma 14 in Zhang et al. (2021a)). For any fixed dimension D and two constants C1, C2 satisfying of & Cz, let f A(DD
R
R R with f(p U, n,
pu max ci
V(p.oh
C2 Thr all p e A(DD)) || 1 and n, 0.
1. f(p,v, u. n, is non-decreasing in v, i.e.
v' such that ||l|| | 1,0 & v', it holds that f(p v, n) f( n,
14

---

Lemma 13 (Optimism of Algorithm Algorithm episode l [K], V& V 2. f(,, n, 2 pu 2
+
Due to the complex structure of LMDP, we cannot prove the strong optimism in Zhang et al. (2021a) This is because in LMDP, the optimal policy cannot maximize all alpha vectors simultaneously. hence the optimal alpha vectors are not unique. As Algorithm 2
we can only show the optimism
the first step, which is stated in Lemma 13
satisfies that: Conditioned on Qz for any
B.2.2 REGRET DECOMPOSITION
We introduce the Bellman error here. It contributes the main order term in the regret.
Lemma 14 (Bellman error). Both Algorithm 2 and Algorithm
3 satisfy the following Bellman error
bound: Conditioned on Q2 and 122, for any (m, h a, k) [M] H A x [K].
Ømm (h. a) Rm (8, a) - Pm a) oe (har.)
s min 5 (h, a). 1).
(8)
@
where r- Rm (s, a) and
TV (P (-1, a), ah Th, (har.))
30S N (s, a)
8h (h, a)
7
TM
Noh (s.a)
Throughout the proof, we denote 3r = B (h, a t(k, $ X1.
Assume that optimism holds, then is more natural to bound F -ー= instead of V*- because the underlying policies are the same for the former case. With simple manipulation, we decompose the regret into X, the Monte Carlo estimation term for the optimistic value, X₂ the Monte Carlo estimation term for the true value, X3 the model estimation error, X, the Bellman error (main order term), and |CC|
the correction term for 1[(k,t) t) $ X1.
K
Regret(K) =
V Vo
7k VT
K
K
H
K
H
Fk 2 (st)
(s
pt
xk
Va
k=1
X,
X₂
K
X,
X2
ao (ht) - xp-
Pmn (11 a&) arn
xx)
K
Pm (-152 at) a (hfatrt.) - a (h
K H
Pont (-1s/, T a (1 X] I[( 1) $)$ x))
K
X1 + X3
X3
Σ
( T an (h:afr
k.(=(((k)
X
X + X, + Xx |c
where (i) is by (k. 1) X (st) at (sf); (ii) follows by Lemma 14 and checking the
difference between 1[ t) & X and [[ t + 1) & X]: (ii) is from the fact that a & 1, and the definition of (k) and I.
15

---

B.2.3 BOUNDING EACH TERM
We start from the easier terms X, and X2.
Lemma 15.
With probability at least 6, we have that X & VK.
Lemma 16. With probability least 1 6, we have that X2 & Vi.
Xg is martingale difference sequence. However, if want to avoid polynomial dependency of cannot apply the Azuma's inequality which scales as /H. Instead, use variance-dependent martingale bound, and this changes X3 into a lower-order term of X4.
Lemma 17. With probability at least 1 - 8, we have that X3 & 2/2Xg + 56.
Here we show the bound for X4 and its proof first, next we prove Theorem we are faced with another quantity Xs, which the summation of variances. do not bound X; explicitly. Instead, we derive relation between X, and X4 (Lemma 19), so finally we solve an inequality X4-
When bounding X4,
Lemma 18. Conditioned on Q4 and Q2 with probability at least we have that XA $ 46v MS? 947M5?A'.
Proof. From Lemma 14 and Lemma we have that
X4 & 13
M
v (Po+ (-1s/ (-15/,a)), ain (htaf L[(k, t) $ X1 + 90M
Applying Lemma using inequality:
x xx+yy- VI+ VV. and loosening the constants, we have the following
X, & 23v MTSAK2 + 209MS Ar + B3MMSAA VX,
Since b implies a & 62 + 2a, we finally have
X, 46v 46 MTSAK. 947MS A...
This completes the proof.
We use the technique of higher-order variance expansion used by (Zhang et al. 2021a) to draw the relation between Xs and X..
Lemma 19. Conditioned on 24 and l2 with probability at least 1 5, have that X5 & 3(K + X,) + 83t.
B.2.4 PROOF OF THEOREM
Finally, we able prove the main theorem.
Proof. From Lemma Lemma 16 Lemma
and property of K,, we have that, with probability
at least 1 35,
(eg < 2 Kt + 2 2x, + 5L + X4 + MSA
Plugging in Lemma 18 using / +
v VJ. finally have
Regret(K) & v8v MSAAK 104LMS
holds with probability at least - 65 (using Lemma 9h. Rescaling 8 completes the proof. 1
16

---

B.3 PROOF OF THE LEMMAS USED IN THE MINIMAX REGRET GUARANTEE
Lemma 9. P[ P[R.] > 1 - 6.
Proof. From Lemma we have that, for any fixed (m, 8, a, s e [M] 8 x Ax x [K] and 2 & N=. (s, a) & HK,
2Pth m (s')s,
7
6
pk m
Pm (5 ($1)s
(s, a) -1 +
3(N
m (8, a) - 1)
M - S A- S- K HKK'
where In
2MS ARKE
L. From + < when x > (N (8,a) a) = is trivial), and
6
applying union bound over all possible events, we have that Pl R Q > 1- 6.
From Lemma 4 we have that, for any fixed (m, s' k) E [M] x S A x [K] and < N (s, & HK,
| 1 (m)
as) + (s) (s,a)
$ M - S. A S K HK
By taking union bound over all possible events, we have that (
K
22 > 1-
Lemma 10. Conditioned on Qr we have that for any (m, a, k) E [M] 8 A [K]. and any S-dimensional vector a such that | < 1,
supp (Pm())),a) V ())
(Bih Pm.) (118, (1),,a) Ta 2
5S
Nk (s.
N (s, a)
Similarly, conditioned S2z, we have that,
(pah - Pmn) a1 &
2supp (Pm (m((1s,00 a)) ( (1)
S1 N (8, a)
N (8,a)
Proof.
We fix the episode number & and omit it for simplicity.
P - Pm)) (-1s,a)Ta
@
Σ (Pm Pm)) (5'1s, (a(6') (m
K'ES
Σ
Pm Pm (5)1s, (a(8 a)
am(s,a) ) |a(t)-PPn (08)-Pm((p -Pn()))a))))
(8)
Σ
2
5e
(8, a)
I
Σ 1 ( (sss)sssa) > 07 (s a(s)) - - (-1s. a +
5.5t
2
(s, a)
Nn,(s, a)
s'ES
Σ (m o] Σ Pm (s a) (a(s) (m)) +
5S
Nm, a)
(s)
supp (Pm(-1s,a) V (m)(-1s,a),
5Sc
21
(m, a)
Nm,
where (i) comes from that P (-|s, a) Ta is constant and P. P are two distributions: (ii) is by the definition of 22 (Equation 6 and |allz < 1; (iii) is from the Cauchy-Schware Schwarz inequality. The second part is similar.
n
17

---

Lemma 11. Let fwt 2 0 (k,t) [K] [H]] be group of weights, then
1kk,t) 21 No mi (8h, a²))
& 3MSA
K
w (
#
3MSA
Σ Σ
H
w [[(k; () $ XJ.
N ma
k-it-1
Proof. From Algorithm I
and the definition of K, we have that for any N, (m, s,a) e [M] x
S x A.
K Σ
Σ
H
[mm st, at) (m, = =
{
2. i= 0.
2 i
So
K
H
[kk, t) X]
Ns. (sf, af)
Boo
(HH) [HK) K
1 [(mm k s(, at) = -m,, 8, (x, = -2 [(Kk () $ x1
E
2'
(m.s.a)E x5xA
k=1t-1
[ogg(HK)]
Σ
2
Σ
1)
(MSX)
3MSAL
Therefore,
K H
[ 1) x] N (st at)
K H
I[(k, t) $ x] N (st at)
1=
K
K H I[(k, $ X1
wi [[k, x1
No ( a²))
K w [[k,, t) x1.
3MSA AL
where (i) is by the property of indicator function; (ii) is by the Cauchy- Cauchy-Schwart Schwarz inequality.
Lemma 13 (Optimism of Algorithm Algorithm satisfies that: Conditioned Q2 for any episode & [K]. V V
Proof. We first argue that for any policy и and any episode k. we have that V > V* Throughout the proof, the episode number 1: is fixed and omitted in any superscript. We proceed the proof for h in the order Hi, Hi 1,.... Hi, using induction. Recall that for any E Hir we define az (h, a) a (h, a) 0. Now suppose for time step f, we already have ă (h', a) 3 a (h', a) for any h E Het1. then & (h') = ae, (h', m(h')) e a (h', ((h)) a (h'), For any h E H.,
0% (h, a)
(8) + ah, + (1s, (har.), 1}
min
supp (P)()1s,a)) V Ve (m (:1,, a), ā. T., (har.))
165t
min
am + max 41
(m,
No (8, a)
+ .pmmm-ps (m((-))))) T (har.),
18

---

m
min
( a) + f (Pm())s, a (har)), N,, 1
Rm)(s,a) + f (-m (har), Nm.
min
min
am( + Pm (-11, "n (har.)
supp (m)()) (mll-s,, a), om (har.))
8 Nm, a)
2
1
(s)
> min { (8, Pm)()s,a) a (har)), 13
a (h. o),
where (i) is by taking r (s, a): (ii) by recognizing e supp (Pm((1s,a)). 16S
in Lemma 12 which satisfy of & o2; (iii) and (iv) come by successively applying the first and
second property in Lemma 12 (v) is an implication of Lemma I0 conditioning on D2 and taking a (har-).
The proof is completed by the fact that n² arg max nell
V hence V
V 3 V*.
3 satisfy the following Bellman error bound: Conditioned on Sh and P2z for any (m, h a, k)) [M] x H x A x [K].
Lemma 14 (Bellman error). Both Algorithm and Algorithm
0 (h, a) Ron (8, a) Pmn(-18 a) Tat (har.)
& min (h, a); 1},
(8)
where r Rm (s, a) and
L (m (-|s, a), a (har.)) Nb. (1,
30S Nh. (s, a)
(h, =7 NN
Proof. Here we decompose the Bellman eπror in a generic way. We use P for the transition and B
for the bonus used in the optimistic model. For Algorithm 2 B O: while for Algorithm 3 P P.
The upper bound of is trivial. Fix any (m, h, a, k)) [M] x A [K]. then
= Rmn a) + Bk (h, a) + Jot (-1s, ott (har.) - Rm (s, a) P.. (-11,,,, a) T a (har-)
Bk Bh (h, a) + Ppt Pm)) (-1s, a) Tak (har.).
Next we proceed in two ways.
For Algorithm we utilize Lemma 20 and similar argument as Lemma gives
supp (P. (-1s,a)) ())
30S
Bernstein < V
Nk (s,0a)
N4 (s,a) a)
For Algorithm we plug in the definition of B and use Lemma 10 gives
supp
Pp (-(s, a)
w
PA m (-1s, a), C. (har.))))
ÜMVP & 4
N (s.a)
2supp
(Pm a))
V (m (-|s, a), T (har.))
17St.
No (8,
N (8,
19

---

Next we bound V (P (-11,, am (har.))
Pa (-1,,,, a), āz (har.))
Σ (6'1111, (s,a) (harss")) - Ps m (-18, a) Ta (har.)) )
Phi (5' (ssssssss) a) (hars)) Pm(-1s,aa a) " (har-))
s'ES
(mc(s'ss, a) + 2P 2
Σ
(aih (hars') ) - Pm,(-ssaa (Tss a (har.))
No (s, (/h(s,a)
Σ
2 Pu (m (s a) + No. (s,
(hars') Pmal:s)))mm(mms..mm (an (har)))
(m(l(s,a)
2St
V (Pm ( (-1s, a), a (har-)) +
N (s)
where (i) is by that 2' = Σ, p:T; minimizes f(z) = Pt(x; - 2)); (ii) is by Q2. Finally, using V + & v V and supp (Mt (-(1,,88) a)
& supp (m (.1( a)), we have
supp (P (1ss V (Pm ãth (har-)) (har-))))))))) +
23St
MMP & 7
Nk (8, a)
N (8, a)
Therefore, setting
TV (m a), (harr)))
30St
3t ah
Nk (s,
NK (K(s,a)
completes the proof.
Lemma 15. With probability least 1 - 6, we have that X1 & VK.
Proof. By definition, V Σ m==1 Eves Wm (m)mmm)aat (s). Thus, - (sf) is random vari- able with mean Vk_ Also, at (s is measurable with respect to Úk Using Lemma and oo (st) Vk 1, have
P
[[x
Kg
&d.
This completes the proof.
Lemma 16. With probubility at least 8, we have that X2 & Vi.
ΣM H r V*r). From Monte Carlo simulation,
Proof.
By definition,
X₂
Σ
H
kk
v= Also,
N.
r is measurable with respect to Ūh-1, Using Lemma and
1-1
1 pu yr
< 1, we have
H
P
Σ
Vi
&d.
This completes the proof.
Lemma 17. With probability least 1 5, we have that Xg 2/2Nxt 5t.
20

---

Proof. Observe that [[ t 1) $ X1 & 1[( $ 21.
H (nnt (+1$/ a T (h ar a (h [[(k; t) XJ.
X3
This is martingale. By taking in Lemma 6 we have
IP X3 > 2 56 E 8.
This completes the proof.
Lemma 19. Conditioned on Sn and Q2 with probability at least 1 ö, we have that X, & 3(K* +
X1) + 83t.
Proof. For any non-negative integer d, define
F(d)= Σ
Σ
Pm (-1s; at) (ath (h(airt))))* - -cmm.(((+))) I[(k.t) t) $ x1,
k=1t-1
K
G(d)= = ΣΣ k=1t-1
V
Pone (115/, at); (o (1 (1(0tr2))) [[(k, () $ x].
Then X5 = G(O). Direct computation gives that
C(d)
K
( at) (oth (h (h(a2r)))) 2011 - (Pm (o (1(h)))))))))))))) 1 [[(k, 1) 21
K
Pm (-1st, ab) (atan (btafr+))) 2 - -(at (1(+1)) (M(+))) [l(k,t) x + (a (1)++=)) 2
K
(a (ht)) 2")
(Por (-15% a (htaar ") I[(k,t) X1 (ath (stn) z4r1
100
F(d+ + 1) + 21+1
max a (1/;,at) at) - P. at) T ath (b/aat)))) 0} D[(k, x
R-1 1
F(d+ + +2+1
max {ā (h+) Pm-(11st T (htaf??)) 03 I[(k,t) $ x
K
& F(d++1) + Σ Σ
(7th + +3)
69 F(d + + 2 (K + Xa):
where (i) is by convexity of function z²"; (ii) is by z² -²² & 2 max{æ y. 0} for x, [0, 1]: (iii) comes from Lemma 14 (iv) is by the assumption that reward within an episode is upper- bounded by 1 and the definiton of X..
For a fixed d, F(d) is a martingale. By taking c = in Lemma 6 we have
P F(F(d) > (HK)
+ ((log, + In(2/0)) < 8.
Taking 8' = 5/(log, HK) + 1), using x: > In(x) + 1 and finally swapping 5 and 8', we have that
5
P F(d) > 2V222 (HK) ln(2/)) + 5(2 log, (HK) + In(2/5)) $ log, (HK) + 1
21

---

Taking union bound over d .,...,, we have that with probability at least 1 6,
F(d) & 4V/(d 1) (K X,))e 10c.
From Lemmal 7 taking Å HK, X2 4V A K + X4, A 10,, have that
F(1) & (4v/ + 261) 8v 2(K + X, + 10c) & K X4 83,,
where (i) uses vay & aiL and max( v, y ج x + for 2, y 2 0. Hence
2
X, G(O) & F(1) 2K X2) 3(K Xx) + 83L.
This completes the proof.
Lemma 20. Conditioned on Sh we have that for any (k, m, 8, 8) [K] [M] x 8x
Pm((sss,a)
30c
Pmll''ss,a)= Ph (s'),,a)
41
N (s
Proof. From Q we have
P (s & 2
Pk (s')s,
5e (s,
+ (s
N*k ( a)
This is quadratic inequality in V Ps (s'ls, a). Using the fact that x² & ar + b implies x & a a vb
5u with - NH(a.a..b [a.a]
(s a), and v y & v V have
(h( & (5 5 (s,
Substituting this into Ω we have
15c
Pn (s'ssa)))) Ph ())1, $21
Nk (s,
N (s,
From the construction of Pk we also have
(ms Nk a)
15c
5 (s'ls, (s < 2
N (8,
Therefore, from triangle inequality we have the desired result.
B.4 PROOF OF THE REGRET LOWER BOUND
Theorem 2. Assume that S 6, and < | For any algorithm æ, there exists an LMDP Mr such that, for K > π(M2 MSA), its expected regret in Mr after K episodes satisfies
R(M=: T, K) = E
Σ (v- vK)
Mn. (VMSAK).
Proof. We need to introduce an alternative regret measure for an MDP based on simulating an LMDP algorithm. Let M(m, [")m,,"",r a²) be MDP which contains encoding phase with permuta- tion a (m). and guessing phase with correct answer (",a"). Given any LMDP algorithm n, target position and a pair of LMDP configuration (E",a") aa),, we construct MDP algorithm T Tm,, L", a²) as in Algorithm 4
This algorithm admits two types of training: @ When K is specified, it returns after K episodes, regardless how many times it interacts with the target MDP; @ When K is specified, it does not return until it interacts with the MDP for K,, times, regardless of how many episodes elapse.
22

---

Algorithm 4 ( L" a"): an algorithm for MDP.
1: Input: an MDP M(m, E* a")); an LMDP algorithm æ, pair LMDP configuration (E" a*); specify exactly one: a simulation episode budget K or a target interaction episode K...
2: Initialize actual interaction counter Km. 0.
3: for = 1, .. do
4: Randomly choose m' (n)
5: if * m then
6: Use interact with the m/th MDP of M(E'aa))
7: else
8:
Use interact with M(m, ,a,a))
9:
Km - -K + 1.
end if
11: if (K is specified and k = K) or (Km is specified and Km = Km) then
Break.
13: end if
14: end for
Let V and V be the optimal value function and the value function of T(m, L" a²), K) under the MDP M(m, e,, aa)) The alternative regret for MDP (corresponding to ①) is:
R(M(m, a'), (m, E, a'), K) K)
Σ
1m m](V' -vh) M(m,f' T(m,
Roughly, this is a regret for Km episodes, though K,, is stochastic.
In our hard instances, the MDPs in the LMDP can be considered separately. So V = where VA is the optimal value function of (which is equal to the value function of the optimal policy applied to) the mth MDP. According to Monte-Carlo sampling,
Em V
R(M(E, a'), T. k) = E
(
Vil.)
M(I',a'),
M
K
E
1mm = m](Vin - Vin.) M(E", ,(E",a"),
m=1
M
R(M(m, En a,)), T(m, l, (a)),
The last step is because the behavior of "focusing on the mtt MDP in the LMDP" and "using the simulator" are the same. Denote Km as the number of episodes spent in the mnth MDP, which is random variable. According to Lemma
K K
In
2MG
In
2MC
8
P
M
M
K
K
MCM
which implies
K
2MC
1MC
PP
K
2K In
+ M
M
8
MC
When K > (6 4v 2.44222222 M In
(MCC)
we have v 22 In 2MC 5
+ M In
2MC
K
By union
2M
bound over all possible hard instances M(E a²) E C and all indices m [M]. the following event happens with probability least 1- 8:
K
for all M(E", a²) C and e (m)]
::
Km 2M
23

---

Now look into Equation (8), (11) and (12) of Domingues al. (2021) For any K' > SA and any fixed encoding number m, we have that
1 1 (
VCK
R(M(m, ", a'), e, a'), Σ
VCK'
C
4
8v/2
when set 2/2 (1-b) V k The desired value of K' is 2M according to
We study the cases when use (m, aa) to solve M(m, en ( with target interaction episode Kn
K K The regret is R(M(m, e and) Tim, l, a²), 2M
(this is the regret of MDPs).
237
K th interaction with the mtth MDP comes before the Kth simulation episode. This The 2M
case happens under & The regret of this part is denoted as lt
Otherwise. This case happens under &. The regret of this part is denoted as R Since the regret of single episode is at most we have that R
2M
Now we study the cases when we use (m, E" a²) to solve M(m, En o,)) with simulation episode budget K. The alternative regret for MDP is R(M(m, lm am);
. T (m, K),
The 2M K th interaction with the mith MDP comes before the Kth simulation episode. This
case happens under E. The regret of this part is denoted R Since the regret of single episode is least and in this case K,, 2
have R Rt.
Otherwise. This case happens under E. The regret of this part is denoted as R > 0.
Using the connection between R and R²- we have:
1
R(M(E, a'),,
CM
8'
M
R(M(m, amm) ( t a'),
CM
oa
Σ R(M(m, (nd) [mm. a')) K)
CM-1
m-11
a
M
Σ
RM Cn. Ond) T(m,
CM-1
m=1
M
Σ R¹ (Mim a"), 2M
K
CM-1
a'm
M
Σ
(R (R- It)
(Mim, Ci), Tm, aa),
K
CM-1
2M
a'.m
Σ
Σ
R (nm)
K
5K
CM-1
2M
2M
M-1
a'
VCK
8K
Σ
CM
16V2M
2M
1=11
E....
VMCK
8K
16v2
24

---

where in (1) a-m to denote the positions other than m in æ; (ii) is by setting K'
R in
Equation 9. Set ò = VMC then we have that
16/2K
max RIM(E, T)) E',
1 C
Σ
VMCK
Ω ( (VMSAK)
32v2
F.a
This holds when K > (6+ 4v2) In 2 and K' > SA. It then reduces to
K > 2 M,, A)) MSA).
This completes the proof.
25


Reviews:
[{"review_id": "yrTP9QuTaQl", "reviewer": "Reviewer_6Gt3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the regret minimization problem of finite horizon Latent MDP with context in hindsight, which assumes the true context of the MDP will be revealed at the end of each episode. It proposes a sample efficient algorithm and proves the polynomial regret bound for the algorithm. The algorithm utilizes the optimistic model-based and value-based planning principle with standard high probability confidence set construction. Based on the horizon-free optimistic planning techniques, the regret of this algorithm is $\\tilde{O}(\\sqrt{MS\\Gamma AK})$, which scales with only $\\log H$. It also provides a corresponding lower bound of regret $\\Omega(\\sqrt{MSAK})$ with a novel symmetrization technique.\n", "summary_of_the_review": "Overall, I think this paper is not good enough. The major drawback is the lack of novelty, since the paper mainly builds its theory based on direct applications of existing results except for the hard instance construction. However, I really appreciate the minimax regret bound for this problem.\n", "strength_and_weaknesses": "There are two key contributions of the paper: an exploration algorithm with provable improved regret bound for LMDP when the context is revealed at the end of each episode, and a novel hard instance construction and the corresponding regret lower bound. The exploration algorithm is mainly built on the model-based and model-free horizon-free techniques proposed by previous works. The construction of the hard instance and proof of the lower bound are new, whose main idea is to split the regret into $M$ parts and show that each part has to be at least $\\Omega(\\sqrt{SAK/M})$. \n\nOn the other hand, I have some concerns regarding to the paper:\n- When the true context is revealed at the end of each episode, one can construct the empirical estimate of the transition and reward using MLE simply, which is in sharp contrast to the partially observable setting. This perhaps leads to a very similar confidence set (both for the model and the optimal value function) as used in previous works studying horizon-free exploration. The extra $\\sqrt{\\Gamma}$ term in the regret seemingly comes from the union bound over any $\\alpha$-vector for the optimism to hold, which is similar to the idea used in UCRL2. It appears to me that this part of the paper is mostly a direct application of existing techniques.\n- I agree that the lower bound construction is novel and the proof of the lower bound requires a delicated manipulation over existing results. The question is the paper claims that it uses the symmetrization technique from TCS, but I cannot find the explanation of this technique in the proof. On the other hand, the hard instance construction seems to be somehow straight forward, by reducing to $M$ independent MDPs since the true MDP can be fully identified in the first phase.  \n- The most interesting story to me for the problem is the minimax regret bound, since I believe the extra $\\sqrt{\\Gamma}$ term comes from the union bound over $\\alpha$-vectors, but we do not need a union bound overall. Could you provide any intuitions or ideas for removing this term? Or you believe the lower bound can be improved.\n\n----------Post rebuttal-----------\n\nThanks for explantionations. However, I still see this work unqualified for a conference paper. The setting is very limited, and many techniques are adapted from previous works. I recommend the authors to study further on the horizon-free setting in LMDPs, for example, the hidden context setting where one has to construct an estimated belief to obtain valid samples.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "vPxwRSxkouW", "reviewer": "Reviewer_jzYm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies regret minimization for reinforcement learning (RL) in Latent Markov Decision Processes (LMDPs) with context in hindsight. Episodic undiscounted case is studied, and regret guarantees are found. The regret bound only scales logarithmically with the planning horizon. Further, the state term dependence is reduced. ", "summary_of_the_review": "This paper studies regret minimization for reinforcement learning (RL) in Latent Markov Decision Processes (LMDPs) with context in hindsight. Episodic undiscounted case is studied, and regret guarantees are found. The regret bound only scales logarithmically with the planning horizon. Further, the state term dependence is reduced. ", "strength_and_weaknesses": "The results seem to improve the state of the art, both for the improvement in terms of H and S. \n\nThe paper assumes stationary MDP which is independent of epoch in the episode. The key aspect of episodic setup is that the transitions and the reward function could depend on h. How do the results extend in this case? I believe that an extra H dependence will come in the result. Extending to this setup can have additional nice results for the paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jIhJXwNCU2Z", "reviewer": "Reviewer_vZUE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies episodic learning algorithms for a variant of POMDP, called LMDP. In such a setting, there are M different MDPs and a new MDP (say m) is drawn at the beginning of each episode. The learner only observes m at the end of the episode and uses to learn. The authors derive both an upper bound and a lower bound for their problem, that are very close.\n", "summary_of_the_review": "This paper is a nice treatment of a purely theoretical problem. I do not find it very original nor applicable.", "strength_and_weaknesses": "This paper is very nicely done but has (too me) limited impact:\n- it is precise, well-done, and contains an upper bound that (almost) matches the lower bound.\n- it contains an algorithm that has no practical application, and that cannot be implemented. It is not very original and (to me) oversold.\n\nTo give more details: \n- even if I did not check the proofs, I do think that the results hold because the techniques are very similar to many classical in the theoretical reinforcement learning literature. They are so close that I cannot really see what is special about latent MDPs in this settign: the confidence bounds are the same as for MDPs (because the latent variable m can be observed at the end of the episode), only the lower bound is different, but is a mere adaptation of the model of Domingues et al (2021).\n- The proposed algorithm is impractical for several reasons, and in particular:\n  - the number of possible values for \"h\" is exponential in H.\n  - the authors claim that one could restrict oneself to a subclass of policies, for instance Markovian policies but:\n    - it is not clear if an optimal policy is easy to compute for LMDP.\n    - the authors sells \"extended value iteration\" but this would not work for many Markovian policies.\n- Some claims are too strong for me:\n  - The authors claim that this \"symmetric technique\" is very new -> having variant of the same problem seems very standards and not very close to the symmetric technique in TCS.\n  - the claim that \"the lower bound matches for \\Gamma=2\" is clearly true but not very informative. It does not mean anything for larger \\Gamma.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject