Learning in Observable POMDPs, without Computationally Intractable Oracles
Authors: Noah Golowich
Ankur Moitra
Dhruv Rohatgi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Partially-observable Markov Decision Processes
barycentric spanner
policy cover

Abstract: Much of reinforcement learning theory is built on top of oracles that are computationally hard to implement. Specifically for learning near-optimal policies in Partially Observable Markov Decision Processes (POMDPs), existing algorithms either need to make strong assumptions about the model dynamics (e.g. deterministic transitions) or assume access to an oracle for solving a hard optimistic planning or estimation problem as a subroutine. In this work we develop the first oracle-free learning algorithm for POMDPs under reasonable assumptions. Specifically, we give a quasipolynomial-time end-to-end algorithm for learning in ``observable'' POMDPs, where observability is the assumption that well-separated distributions over states induce well-separated distributions over observations. Our techniques circumvent the more traditional approach of using the principle of optimism under uncertainty to promote exploration, and instead give a novel application of barycentric spanners to constructing policy covers.

Learning in Observable POMDPs, without Computationally Intractable Oracles
Noah Golowich MIT nzg@mit. edu
Ankur Moitra MIT moitraCmit edu
Dhruv Rohatgi MIT drohatgi @mit edu
Abstract
Much of reinforcement learning theory is built top of oracles that compu- tationally hard to implement. Specifically for learning near-optimal policies Partially Observable Markov Decision Processes (POMDPs), existing algorithms either need to make strong assumptions about the model dynamics (c.g. determinis- tie transitions) assume access an oracle for solving hard optimistic planning or estimation problem as a subroutine, In this work we develop the first oracle-free learning algorithm for POMDPs under reasonable assumptions. Specifically, we give quasipolynomial mimea----me time end-to-end algorithm for learning in "observable" POMDPs, where observability is the assumption that well- sepa-atee distributions over states induce well well-separated distributions over observations. Our techniques circumvent the more traditional approach of using the principle of optimism un- der uncertainty to promote exploration, and instead give novel application of barycentric spanners to constructing policy covers.
Introduction
Markov Decision Processes (MDPs) are a ubiquitous model in reinforcement learning that aim to capture sequential mecksign-making problems in variety of applications spanning robotics to healthcare. However, modelling a problem with an MDP makes the often-unrealistic assumption that the agent has perfect knowledge about the state of the world. Partially Observable Markov Decision Processes (POMDPs) are a broad generalization of MDPs which capture an agent's inherent uncertainty about the state: while there is still underlying state that updates according to the agent's actions, the agent never directly observes the state, but instead receives samples from state- dependent observation distribution. The greater generality afforded by partial observability is crucial to applications in game theory [BS18), healthcare [Hau00, HF00b), market design [WME++2) and robotics [CKK96].
Unfortunately, this greater generality comes with steep statistical and computational costs. There well-known statistical lower bounds [JKKL20, KAL16], which show that in the worst case, is statistically intractable to find near-optimal policy for POMDP given the ability to play policies given unlimited computation. Furthermore, there worst-case
on it (the learning problem), computational lower bounds [PT87, Lit94, BDRS96, LGM01, VLB 12B, which establish that it is computationally intractable to find optrmoptimal policy when given the exact parameters of the model (the substantially simpler planning problem).
Nevertheless there is sizeable literature devoted to overcoming the statistical intractability of the learning problem by restricting to natural subclasses of POMDPs [KAL16, GDB16, ALA 16, JKKL20, XCGZ21, KECM21a, KECM2 LCSJ22). There are far fewer works attempting to overcome computational intractability, and all make severe restrictions on either the model dynamics [JKKL20, KAL16] or the structure of the uncertainty [BDRS96, KECM21a], The standard practice to simply sidestep computational issues by assuming access to strong oracles such as ones that
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

solve Optimistic Planning (given constrained, non-convex set of POMDPs, find the maximum value achievable by any policy on any POMDP in the set) [JKKL20] or Optimistic Maximum Likelihood Estimation (given a set of action/observation sample trajectories. find POMDP which obtains maximum value conditioned on approximately maximizing the likelihood of seeing those trajectories) [LCSI22]. Unsurprisingly, these oracles are computationally intractable to implement. Is there any hope for giving computationally efficient, oracle-free learning algorithms for POMDPs under reasonable assumptions? The naive approach would require exponential time, and thus even quasi-polynomial time algorithm would represent a dramatic improvement.
A necessary first step towards solving the learning problem is having a computationally efficient planning algorithm. Few such algorithms have provable guarantees under reasonable model assump- tions, but recently it was shown [GMR22] that there is quasipolynomial -ime planning algorithm for POMDPs which satisfy an observability assumption. Let H N be the horizon length of the POMDP, and for each state and step h E [H), let (-1s) denote the observation distribution at state 8 and step h. Then observability is defined as follows:
Assumption 1.1 ([EDKM07, GMR22J). Let > O. For h E [H], let Oj be the matrix with columns O% (-Is), indexed by states s. We say that the matrix On satisfies 7-observability for each h, for any distributions 6, b' over states, 1 - 0,,6'l, 2 7 ||6 11 A POMDP satisfies (one-step) 7-observabilityy if all H of its observation matrices do.
Compared to previous assumptions enabling computationally efficient planning. observability much milder because it makes no assumptions about the dynamics of the POMDP, and it allows for natural observation models such as noisy or lossy sensors [GMR22]. is known that statistically efficient learning is possible under somewhat weaker assumptions than observability [JKKL20], however these works rely on solving a planning problem that is computationally intractable. This raises the question: Is observability enough to remedy both the computational and statistical woes of learning POMDPs? In particular, can we get not only efficient planning but efficient learning too?
Overview of results. This work provides affirmative answer to the questions above: we give an algorithm (BaSeCAMP, Algorithm 3) with quasi-polynomial time (and sample) complexity for learning near-optimal policies in observable POMDPs see Theorem 3.1. While this falls just short of polynomial time, it turns out to be optimal in the sense that even for observable POMDPs there is polyimpoly time lower bound for the (simpler) planning problem under standard complexity assumptions [GMR22]. A key innovation of our approach is an alternative technique to encourage exploration: whereas essentially all previous approaches for partially observable RL used the principle of optimism under uncertainty to encourage the algorithm to visit states [J,,00 LCSJ22), we introduce new framework based on the use of barycentric spanners [AK08] and policy covers [DKJ+19], 19]. While each of these tools has previously been used in the broader RL literature to promote exploration (e.g. [LS17, FKQR21, DKJ+ 19, AHKS20, DGZ22, JKSY20, MHKL20]), they have not been used specifically in the study of POMDPs with imperfect observations, and indeed our usage of them differs substantially from past instances.
The starting point for our approach is a result of [GMR22] (restated as Theorem 2.1) which implics that the dynamics of an observable POMDP P may be approximated by those of Markov decision process M with a muuasipoolynomia number of states. If we knew the transitions of M, then we could simply use dynamic programming to find an optimal policy for M, which would be guaranteed to be a near-optimal policy for P. Instead, we must learn the transitions of M, for which it is necessary to explore all (reachable) states of the underlying POMDP P. A naïve approach exploration is to learn the transitions of P via forwards induction on the layer h. using, at each step ht our knowledge of the learned transitions at steps prior to h to find a policy which visits each reachable state at step h. Such an approach would lead to a policy cover, namely a collection of policies which visits all reachable latent states.
encourage
A major problem with this approach is that the latent states are not observed: instead, we only observations. Hence natural approach might be to choose policies which lead to all possible observations at each step h. This approach is clearly insufficient, since, e.g., a single state could emit a uniform distribution over observations. Thus we instead compute the following stronger concept: for each step h, we consider the set X of all possible distributions over observations at
Policy covers have been used in the special case of block MDPs [DKI*19, 19, MHKL20J, namely where different states produce disjoint observations.
2

---

step h under any general policy, and attempt to find barycentric spanner of X' namely small subset X' C X' so that all other distributions in X' can be expressed as a linear combination of elements of X" with bounded coefficients. By playing a policy which realizes each distribution in such a baryeentrie spanner X", we are able to explore all reachable latent states, despite having no knowledge about which states we are exploring. This discussion omits a key technical aspect of the proof, which is the fact that we can only compute a barycentric spanner for a set X corresponding to an empirical estimate M of M. A key innovation in our proof is a technique to dynamically use such barycentric spanners, even when M is inaccurate, to improve the quality of the estimate M. We remark that a similar dynamic usage of barycentric spanners appeared in [FKQR21]; we discuss in the appendix why the approach of [FKQR21], as well as related approaches involving nonstationary MDPs [WL21, WDZ22, WYDW21], cannot be applied here.
Taking a step back, few models in reinforcement learning (beyond tabular or linear MDPs) admit computationally efficient end-to-end learning algorithms indeed, our main contribution is way to circumvent the daunting task of implementing any of the various constrained optimistic planning oracles assumed in previous optimism-based approaches. We hope that our techniques may be useful in other contexts for avoiding computational intractability without resorting to oracles.
2 Preliminaries
For sets T. let Q denote the set of mappings from T -> ->Q. Accordingly, we will identify RT with ITI-dimensional Euclidean space, and let A(T) C R consist of distributions on T. For d E N and a vector v E IRd, we denote its components by v())...., v(d). For integers S b. we abbreviate a sequence (Ia, Teti.......... .b)) by Fa.b. If > b, then we let Fabb denote the empty sequence. Sometimes we refer to negative indices of sequence Zi:n: in such cases the elements with negative indices may be taken to be aribtrary, as they will never affect the value of the expression. See Appendix B. I for clarification. For x E RR we write [x:] max (ar, 0}. and [x]] - min(22, 0}. For sets S, T, the notation S C T allows for the possibility that T
2.1 Background on POMDPs
In this paper we address the problem of learning finite-horizon partially observable Markov decision processes (POMDPs). Formally, a POMDP P is a tuple P (H, A, O,b, R, T, 0), where:
H E N is a positive integer denoting the horizon length; S is a finite set of states of size S == |S]; A
finite set of actions of size A := |AA| O is a finite set of observations of size 0 = |0] b2 is the initial distribution over states; and R, T, O are given as follows. First, R = (R ......... RH) denotes
tuple of reward functions, where, for h E [H]. RA O + [0, 1] gives the reward received as function of the observation at step h. (It is customary in the literatue [JKKL20, LCSJ22] to define the rewards as being a function of the observations as opposed to being observed by the algorithm as separate information.) Second, T = (T...... Th) ) is tuple of transition kernels, where, for E [H, s, E S.a a E A, (s' s, a) denotes the probability of transitioning from s' at step h when action a is taken. For each E A, we will write T, R*SS to denote the matrix with TA (a).../ = (s]s'' ( a). Third, O = (O,...., O1) is tuple of observation matrices, where for h E { E S, E O, (On)a,s. also written as O2 (ols), denotes the probability observing while in state at step h. Thus On E R for each h. Sometimes, for disambiguation, we will refer to the states S as the latent states of the POMDP P.
The interaction (namely, a single episode) with P proceeds as follows: initially state 8 ~ by is drawn from the initial state distribution. At each step h < H, an action as A is chosen (as function of previous observations and actions taken), P transitions to a new state 8h+1 ~ (- on). a new observation is observed, 0 ~ (++1(-|1/44)) and a reward of (o)+1) is received (and observed). We emphasize that the underlying states $1-H are never observed directly. As a matter of convention, we assume that no observation is observed step 1; thus the first observation is 02-
2.2 Policies, value functions
deterministic policy a is a tuple o = (aI,..., ., ,HH), where on -h- x Oh-1 + A is a mapping from histories up to step h. namely tuples (a1:h-1, 02:),, to actions. We will denote the collection of histories up to step h by Hr, == -h-1 x -h-1 and the set of deterministic policies by det
3

---

meaning that II = -I A A A general policy π is distribution over deterministic policies; the set of general policies is denoted by _| := A ))) Given a general policy 1[gen we denote by a π the draw of deterministic policy from the distribution æı; to execute general policy тT, a sample a x is first drawn and then followed for an episode of the POMDP. For a general policy и and some event E, write P
-n.n-1-02 11 n~T (E) to denote the probability of & when is drawn from a trajectory following policy x for the POMDP P. At times we will compress notation in the subscript, e.g., write P (E) if the definition of $1.H d1:H-11 O2:H is evident. In similar spirit, we will write -11.8-1022.8880
S1:H; -1 O2:H 02:H
to denote expectations.
Given general policy x E I[ define the value function for π at step by VT. (0) EP BoL Σ Ru(on)] namely as the expected reward received by following π.
Our objective is to find a policy π which maximizes V V (0). in the PAC-RL model [KS02]: in particular, the algorithm does not have access to the transition kernel, reward function, observation matrices of P, but can repeatedly choose a general policy т and observe the following data from a single trajectory drawn according to m: (a1, 02, R2(02) 0g,.... dH-1, Ru (oz)). The challenge is to choose such policies ι which can sufficiently explore the environment.
Finally, we remark that Markov decision processes (MDPs) are special case of POMDPs where O == and (ols) = [o = s] for all h E [H) 0, s E S. For the MDPs we will consider, the initial state distribution will be left unspecified (indeed, the optimal policy of an MDP does not depend on the initial state distribution). Thus, we consider MDPs M described by a tuple M = (H, A, R, T).
2.3 Belief contraction
A prerequisite for a computationally efficient learning algorithm in observable POMDPs is a com- putationally efficient planning algorithm, i.e. an algorithm to find an approximately optimal policy when the POMDP is known. Recent work [GMR22] obtains such a planning algorithm taking quasipolynomial time; we now introduce the key tools used in [GMR22], which are used in our algorithm as well.
Consider POMDP P (H,S, R,T,O,,,,TTT))) Given some h E [H] and a history (01:h-1, 02:h) E Hh. the belief state by (Q::h-1,02t) E A(S) is given by the distribution of the state sp conditioned on taking actions 01:h-1 and observing 02 in the first h steps. Formally,
the belief state is defined inductively as follows: (0) = bj. and for 2 < h < H and any
(01.h-1,02.h) E Hr.
by (2)) 02:1) (aa 0z:h 1): 0n-1, on); where for b A(S). E A. O. (b; E (SS) is the distribution defined by On+1(ols) Eves b(s') (n(sss'
Up (b((ba,o)(s)= Exes (n+1(0lx) Eves b(8') (n(s)s',a)
We call UP the belief update operator. The belief state by (A1:A-1,02. is sufficient statistic for the sequence of future actions and observations under any deterministic policy. In particular, the optimal policy can be expressed as function of the belief state, rather than the entire history. Thus, a natural approach to plan a near-optimal policy is to find a small set H C (SS) of distributions over states such that each possible belief state bj, (a1:h-1.02.) is close to some element of B. Unfortunately. this is not possible, even in observable POMDPs [GMR22, Example D.2]. The main result of [GMR22] circumvents this issue by showing that there is a subset B A(S) of quasipolynomial size (depending on P) so that b7. (01:A-1, 02:h) ) is close to some element of B in expectation under any given policy. To state the result of [GMR22], we need to introduce approximate belief states:
Definition 2.1 (Approximate belief state). Fix POMDP P (H, S. A, O, b, R, T,T,O O). For any distribution D E (SS), as well as any choices of 1 < h < И and L 2 O. the approximate belief state Z) is defined as follows, via induction on L: in the case that L = 0.
by P (a)- On- L41
then we define
: h
b apx,7
: h > 1,
4

---

and for the case that L > O, define, for h >> L,
bh (ah- L.h- 1, Oh 9) == (b (On-LAh-21 Oh- 1+ 10: 0%))
P
We extend the above definition to the case that h S L by defining (0
(Amax (1,1- 1.) (2,x 1+11aa () words, the approximate belief state by bupx.Pp (an-LA L---L-h-11 Oh P L+1:h; 2) is obtained by applying the belief update L > 1 (and otherwise, starting from b,
2) = by b
operator starting from the distribution 2 at step / - L. if step At times, will drop the superscript P from the above definitions and write b b
The main technical result of [GMR22], stated as Theorem 2.1 below (with slight differences, see Appendix B), proves that if the POMDP P is "yobservable for some O, then for wide range of distributions 2, for sufficiently large L, the approximate belief state by bupx. (ak-L:h-20 Oh L+I:A: ②) will be close to (i.e.. "contract to") the true belief state by (Q1:1-1,02.1.)
Theorem 2.1 (Belief contraction; Theorems 4.1 and 4.7 of [GMR22]). Consider any y-observable POMDP P, any 6 > 0 and E so that T. 2 C min log(1/(e))) log(log(1/0)/e) log(1/(eol)
}. Fix
any π E I and suppose that 2 E A satiisiex by 1 < for all (an-1,02.)
(1s)
Then
E B B(a
by (aIn-1, bapx. (0h 141.4 1)) SE.
Se.
2.4 Visitation distributions
For POMDP P = (H,S,A,O,)) R, 0), policy x E I[gen and step / E [H]. the (latent) state p..= visitation distribution at step h is S,h ASS) defined by di = Pp $1.8 w (8h = 5). and the dP.5
observation visitation distribution at step h is df E A(O) defined by do,h = 1 (or =
.) = On d As will be discussed in Section 4.1, Theorem 2.1 implies that the transitions of the POMDP P can be approximated by those of an MDP M whose states consist of L-tuples of actions and observations. Thus we will often deal with such MDPs M of the form JM - (H, 2, R. T) where the set of states has the product structure Z = A x O³. We then define by o(a1,L, 01.L) OL. For such MDPs, we define the observation visitation distributions by M.n (o) == Wdd - (o(z)) = o). Finally, for o E O, we let e, E R200 denote the oth unit vector; thus, for instance, we have d'.T (o) = (Co, (p.).
2 + O
Main result: learning observable POMDPs in quasipolynomial time
Theorem 3.1 below states our main guarantee for BaSeCAMP (Barycentric Spanner policy Cover with Approximate MDP; Algorithm 3).
Theorem 3.1. Given any a. 3,,77 > O and 7-observable POMDP P, BaSeCAMP with parameter settings as described in Section C.1 outputs a policy which is a-suboptimal with probability at least 1 - B, using time and sample complexity bounded by (OA)OL log(1/3), where C' > 1 is a constant and L min log (HSO/(a)) log" (HS0 ((a))))))))))))))))))))
is natural to ask whether the complexity guarantee of Theorem 3.1 can be improved further. [GMR22, Theorem 6.4] shows that under the Exponential Time Hypothesis. there is no algorithm for planning in --observable POMDPs which runs in time (SAHO) ( a-suboptimal policies, even if the POMDP is known. Thus, up to polynomial factors the exponent, Theorem 3.1 is optimal. It is plausible, however, that there could be an algorithm which runs in quasipolynomial time yet only needs polynomially many samples; we leave this question for future work.
((log(S AHO/s)//////// and produces
5

---

4 Algorithm description
4.1 Approximating P with an MDP.
A key consequence of observability is that, by the belief contraction result of Theorem 2.1, the POMDP P is well-approximated by an MDP M of quasi-polynomial size. In more detail, we will apply Theorem 2.1 with ø = 1/S, 9 = Unif(S), and some L = poly(log(S/c)//) sufficiently large so as satisfy the requirement of the theorem statement. The MDP M has state space 2 == AA x O", horizon H, action space A, and transitions P)M(1zu (-IzA, an) which are defined via Un)) in particular, for state belief update the approximate belief state ba.x. (zy; (z,;
2/ = (AN--LL--, E Z of M, action axe and subsequent observation ON+1 E O, define
((ah 0h-L+2:++1 zA. an) == Cout1 O.+1 T (ax) by. Unif(S)). (1)
The above definition should be compared with the probability of observing o++1 given history (01:1, 02.6) and policy when interacting with the POMDP P, which is
P 0h+1 (0h+1 ansh, 02.h) = Corts 0h41 Th (an) bj (21))
Theorem 2.1 gives that by (a1=h-1, 02.h) a (an- Lih- L+ Unif(S)) is small in expectation under any general policy n,, which, using (1) and (2), gives that, for all π E 11 and [H].
Σ 06+1E0
I (on+1lEn, an) Po (on+ 1 02.) Se.
(3)
(Above have written 2/1 (an- L.h 1h 0 and, via abuse of notation, P.M (o1++1122 an) in place of MPMMM ((an-+11h, 0h- Zh. a.).)) The inequality (3) establishes that the dynamics of P under any policy may be approximated by those of the MDP .M. Crucially, this implics that there exists deterministic Markov policy for .M which is near-optimal among general policies for P; the set of such Markov policies for M is denoted by Tmaakkv Because of the Markovian structure of M, such policy can be found in time polynomial in the size of M (which is quasi-polynone in the underlying problem parameters), if M is known. Of course, M is not known.
Approximately learning the MDP M. These observations suggest the following model-based approach of trying to learn the transitions of M. Suppose that we know sequence of general policies ..... (abbreviated as π æ!:H) so that for each h, x² visits a uniformly random state of P at step h L (i.e. de - Un). Then we can estimate the transitions of M as follows: play x² for h- L steps and then play L+1 random actions, generating trajectory (a1:k, 02:4+1)- Conditioned on ΣΛ = (an-L:h-1, oh Ph-1+1:h) and final action 4n, the last observation of this sample trajectory, 0h+1, would give an unbiased draw from the transition distribution IPMM (-|z2, ax). Repeating this procedure would allow estimation of IP, (see Lemma E.
P.*
This idea formalized in the procedure ConstructMDP (Algorithm 1): given a sequence of general policies n²' ,...., , (abbreviated II.H), ConstructMDP constructs an MDP, denoted M M)) which empirically approximates M using the sampling procedure described above. For technical reasons, M actually has state space Z = A o where Ō = OU U forink and şiin is a special "sink observation" so that, after Jaiuk is observed, all future observations are also sink Furthermore, we remark that &p,=" does not have to be exactly uniform it suffices h visits all states of P step / L with non-negligible probability.
4.2 Exploration via barycentric spanners
The above procedure for approximating M with M omits crucial detail: how can we find the "exploratory policies" n I.H ? Indeed a major obstacle to finding such policies is that we never directly
For simplicity, descriptions of the reward function of M are omitted; we refer the reader to the appendix for the full details of the proof

---

observe the states of P. By repeatedly playing policy on P, we can estimate the induced observation visitation distribution d which is related to the state visitation distribution via the equality 0/ O,K-L pp.7 - Unfortunately, the matrix Oa-L is still unknown, and in general
unidentifiable.
On the positive side, we can attempt to learn M layer by layer in particular, when learning the lihh layer, we can assume that we have learned previous layers, i.e., O approximates d..r. d and define "formal"
therefore df &f,-- O. Even though M does not have underlying latent states, latent state distributions on .M in analogy with P. i.e. d... - == 0', dM O, But this does not seem helpful, again because - is unknown. Our first key insight is that a policy n", for which MM -. puts non-negligible mass all states, be found (when it exists) via knowledge of M and the technique of Barycentric Spanners all without ever explicitly computing ShhhLL
M.r
Barycentric spanners. Suppose we knew that the transitions of our empirical estimate M approxi- mate those of M up to step h, and we want to find a policy x² for which the (formal) latent state distribution dssh is neg-nggli on all states. Unfortunately, the set of achievable latent state
distributions (0) (0)_1 0.h-
[ RR is defined implicitly, via the unknown observation matrix On-L- But we do have access to X M == {do, r. π I[ C IR, the set of achievable distributions over the observation at step h - L. In particular, for any reward function on observations at step L, we can efficiently (by dynamic programming) find a policy π that maximizes reward on M over all policies. In other words, we can solve linear optimization problems over X. By a classic result [AK08], we can thus efficiently find barycentric spanner for X -i
M.r
Definition 4.1 (Barycentric spanner). Consider a subset X' C Rdd. For B 2 1, set X" C of size d is a B-approximate barycentric spanner of X if each x E X' can be expressed linear combination of elements X' with coefficients in [-B, (3,B) B}.
Using the guarantee of [AK08] (restated as Lemma D.I) applied to the set X XM we can find,
in time polynomial in the size of M, 2-approximate barycentric spanner ,,,..., 70 of X -Min-zi this procedure is formalized in BarySpannerPolicy (Algorithm 2). Thus, for any policy n, the M.#
observation distribution d.M.a O, induced by is a linear combination of the distributions {d
i [O]} with coefficients in 2- 2]. Since M,r d 0i,_,. do for all x, it follows that the formal latent state distribution ds induced by π is a linear combination of the formal latent state
MM.n
distributions (ds.h- - : [0]} with the same coefficients. Now, intuitively, the randomized mixture policy Tmix 1 ( +... # should explore every reachable state; indeed, we show the following guarantee for BaryspamnePPolccy:
Lemma 4.1 (Informal version & special case of Lemma D.2), In the above setting, under some technical conditions, for all S and π E T[gen, it holds that d M.
d.hh (8) 2 -0
(s)
M,x
But recall the original goal: a policy x which explores P - not M. Unfortunately, those states in P which can only be reached with probability that is small compared to the distance between P and M may be missed by Tmix- When we use Tmix to compute the next-step transitions of M, this will lead to additional error when applying belief contraction (Theorem 2.1), and therefore additional error between P and M. If not handled carefully, this error will compound exponentially over layers.
4.3 The full algorithm via iterative discovery
The solution to the dilemma discussed above is to not try to construct our estimate M of M layer by layer, hoping that at each layer can explore all reachable states of P despite making errors in
7

---

Algorithm ConstructMDP
1: procedure CONSTRUCTMIP(L,, No. N1.7", , 7
2: for 1 < H do
3: Let Ht be the policy which follows T² for the first max h L 1, 0} steps and thereafter
chooses uniformly random actions.
4:
Draw No independent trajectories from the policy Th:
5: Denote the data from the ith trajectory by a di:--1 O2. for [No]-
6: Set 21, (a) I.h - h 1- for all i [No], [H].
7:
// Construct the transitions PM (214.1 Eh, an) as follows: for each n = (ah- 1,,-1, Oh- Ishhs)) E Z, an do
8:
9:
// Define P/ (1|2k, (h.) ) be the empirical distribution of zh+ 1 ai as follows:
For uh+1 E O, define sp(o+1) = Hi (a maxxx11 L of
(Amaxx (1.xxx111111 L L) (2ax(2.h-L++))h++ Eonm (((h-1) 2 N1 then
11:
12:
Set PMM "1a- L+1:h: Oh- an)
for all oh+1 E O.
Expn p(on4s)
13:
Set (Fh((z,, an) = R2 (o%) ) for some with of = on.
D RR (o%) is observed.
else
15:
Let (-12h, an) put all its mass on (an- (0n orink)).
16:
for each 2n (an- 1:h-1, on- 1+hh 2 and an E A do
17:
Let 1-, (-IZh, an) put all its mass on (a2-L+1sh (0) L+2 , gziuk))
Let M denote the MDP (Z, H, A, R.M.P.M..
18:
19:
return the MDP M, which we denote by M(TI:
Algorithm 2 BarySpannerPolicy
& M MDP state space Z, horizon H; h [H] 2: if S L then return an arbitrary general policy.
1: procedure BARYSPANNEAPOLICCCCM
3:
Let Ø be the linear optimization oracle which given E RO, returns
arg max, Ellparrkoo (r, (r.do O, and max
M.M (r, O, b Note that & can be implemented
in time Õ( HO) using dynamic programming Using the algorithm of [AK08] with oracle 0, compute policies { ....,, [.} so that
4:
( ii [0]} is 2-approximate barycentric spanner of (do E Nuarkkov). b This algorithm requires only O log O) calls to O
5: return the general policy y Ee
earlier layers of M. Instead, we have be able go back and "fix" errors in our empirical estimates at earlier layers. This task is performed in our main algorithm, BaSeCAMP (Algorithm 3). For some K N, BaSeCAMP runs for total of K iterations: each iteration & [K], BaSeCAMP defines H general policies, * #K. I (abbreviated #HH step 4). The algorithm's 's overall goal is that, for some k, for each [H], kh, explores all latent states at step h L that are reachable by any policy.
To ensure that this condition holds at some iteration, BaSeCAMP performs the following two main steps for each iteration k: first, it calls Algorithm I to construct an MDP, denoted M using the policies 1k11 Then, for each h [H], it passes the tuple (A) h) to BarySpannerPolicy which returns as output general policy, N +,,,, Then, policies A are produced (step 7) by averaging * 1,A .0 for all h' 2 h. The policies 1, are then mixed into the policies 1,+ for next iteration + 1. follows from properties of BarySpannerPolice policies म Rith are not sufficiently exploratory, one of the new policies n. * visits some latent state (s, h²) E x [H], which was not previously visited by k.H with significant probability. Thus, after a total of K O(SH) iterations k it follows that must have visited all (reachable) latent
that, in the event that the

---

states of the POMDP. At the end of these K iterations, BaSeCAMP computes an optimal policy for each ( and returns the best of them (as evaluated on fresh trajectories drawn from P; step 12).
Algorithm 3 BaSeCAMP (Barycentric Spanner policy Cover with Approximate MDP)
1: procedure BASECAMP(L, No, Ni, a. B, K)
2: Initialize 1 1.11 ................................ , to be arbitrary policies.
3: for k E [K] do
4: For each [4]. set R = E &h'h
5:
Run ConstructMDP(I, No: 14, and let its output be (())
6:
For each [H], let n 1,,00 be the output BarySpannerPolicy (MM)),
7:
For each E [H], define xk+11 = --h+T Em= n k+1,''
Choose the best optimal policy amongst all M(K for k E [K] do
8:
9:
Let x denote an optimal policy of M
Execute T for 100H² log K/B trajectories and let the mean reward across them be p*
11:
a²
12: Let k* = arg [ pk.
return x4""
Proof Outline
We now briefly outline the proof of Theorem 3.1; further details may be found in the appendix. The high-level idea of the proof is to show that the algorithm BASeCAMP makes a given amount of progress for each iteration as specified the following lemma:
Lemma 5.1 ("Progress lemma": informal version of Lemma 1.2). Fix any iteration k in Algorithm 3,
step Then, for some parameters 8, & with a > 8 > o > 0, one of the following statements holds:
1. Any h) with P.
S,h-1. (. (8) < d satisfies S.h 1 (0) S 8 for all general policies
2. There is some (h, s) E [ so that:
dP. th d Sh-L (+) < H2S, yet, for all k: S.h-L ds)n-L(s) (8) Φ5 H2S.
Given Lemma 5.1, the proof of Theorem 3.1 is fairly straightforward. In particular, each (h, s) E [H] x S can only appear as the specified pair in item 2 of the lemma for single iteration k. Thus, as long as K > HS, item must hold for some value of k, say k* E [K]. In turn, it is not difficult to show from this that the MDP ((k)) is good approximation of P, in the sense that for any general policy æ, the values of M((k) and in P are close (Lemma H.3). Thus, the optimal policy = of M((") will a optrmal policy of P, and steps 9 through 12 of BaSeCAMP will identify either the policy ot or some other policy n.K which has even higher reward on P.
Proof of the progress lemma. The bulk of the proof of Theorem 3.1 consists of the proof of Lemma 5.1, which we proceed to outline. Suppose that item of the lemma does not hold, meaning
that there some π [[gen and some (h, E [M] so that dp L (s) Φ yet dP. ( > 8;
i.e., khh does not explore (s, h - I.). but the policy does. Roughly speaking, BaSeCAMP ensures that item holds in this case, using the following two steps:
(A) First, show that (e., 0/ - -. 2 8', where 8' is some parameter satisfying à > d'
In words, the estimate of the underlying state distribution provided by (k) also has the property that some policy π visits (s, h L)) with non-negligible probability (namely, 8'). While this statement would be straightforward if (k) were close approximation P. this is not necessarily the case (indeed, if it were the ease, then item of Lemma 5.1 would hold). To circumvent this issue, we introduce family of intermediate POMDPs indexed by H' e [H] and denoted Po. (IHH.

---

which we call truncated POMDPs. Roughly speaking, the truncated POMDP P 6.Hr (T diverts transitions away from all states at step Hf' L which  does not visit with probability least 6. This modification is made to allow Theorem 2.1 to be applied to Po.ar (Tk.1:8f and any general policy n. By doing so, we may show a one-sided error bound between Po. (TFh1:H) and M(() (Lemma G.4) which, importantly, holds even when the policies 7k.1.H may fail to explore some states. is this one-sided error bound which implies the lower bound on (e,, 0/_ (M()
doh-L")
(B) Second, we show that the policy πt * produced by BarySpannerPolicyy in step 6 explores (s, h - L) with sufficient probability. To do so, we first use Lemma 4.1 to conclude that (ex. 0/= =M
40 The more challenging step is to use this fact to conclude a lower bound
8'
on SAA-L (s); unfortunately, the one-sided error bound between P and M( that we used in the previous paragraph goes in the wrong direction here. The solution is to use Lemma H.3, which
P. P.
P (s) is not too small, or else the policy x²* 1,,00 visits some state at step prior to T. which was not sufficiently explored by any of the policies 8.1H (see Section C for further details). In either case a *1I1,,, visits state that was not previously explored, and the fact that n²
has the following consequence: either ds.h-I.
is mixed in to  'N'' for k k,hh' h/ < h (steps 4, 7 of BaSeCAMP) allows us to conclude item 2 of Lemma 5.1.
6 Conclusion
In this paper we have demonstrated the first quasipolynomial -ime (and quasipolynomialssmpphl algorithm for learning observable POMDPs. Several interesting directions for future work remain:
It is straightforward to show that a 7-observable POMDP is 2(7/v/) weakly-revealing in the sense of [LCSJ22, Assumption 1]. Thus, the results of [JKKL20, LCSJ22] imply that 7-observable POMDPs can be learned with polynomially many samples, albeit by computationally inefficient algorithms. Thus, as discussed following Theorem 3.1, it is natural to wonder whether we can achieve the best of both worlds: is there quasipolynomial- time algorithm that only needs polynomially many samples, statistical tradcoff?
one show computational-
It is also natural to ask whether an analogue of Assumption 1.1 for the l norm, namely that ||Or b O,,b'l I|2 2 2 1/ for all h E [H) is sufficient for computationally efficient learnability. Even the planning version of this question (where the parameters of the POMDP are known and the problem is to find a near-optimal policy) open.
Acknowledgments and Disclosure of Funding
N.G. is supported by a Fannie & John Hertz Foundation Fellowship and an NSF Graduate Fellowship. A.M. is supported by a Microsoft Trustworthy AI Grant, NSF Large CCF-1565235, a David and Lucile Packard Fellowship and an ONR Young Investigator Award. D.R. is supported by an Akamai Presidential Fellowship and U.S. DoD NDSEG Fellowship.
References
[AGH+14] 14] Animashree Anandkumar, Rong Ge. Daniel J Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15(1):2773-288 2-32,, 2014.
[AHKS20] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in Neural Infor- mation Processing Systems, 33:13399-1341 2020.
[AK08] Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114 2008.
10

---

[ALA16] Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Open problem: Approximate planning of pomdps the class of memoryless policies. In Conference on Learning Theory, pages 1639-1642. PMLR, 2016.
[AYA18] Kamyar Azizzadenesheli, Yisong Yue, and Animashree Anandkumar. Policy gradient in partially observable environments: Approximation and convergence. arXiv preprint 1rXiv:1810.09900 2018.
[BDRS96] Dima Burago, Michel De Rougemont, and Anatol Slissenko. On the complexity of partially observed markov decision processes. Theoretical Computer Science, 157(2):161-183, 1996.
[BS18] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374) 2018.
[Can20] Clément L Canonne. short note on learning discrete distributions. arXiv preprint arXiv:2002. /457, 2020.
[CJ]+21] Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, and Ufuk Topcu. Robust finite-state controllers for uncertain pomdps. In AAAI, pages 11792-11801 AAAI Press, 2021.
[CJJT22] Steven Carr, Nils Jansen, Sebastian Junges, and Ufuk Topcu. Safe reinforcement learning via shielding for pomdps. CoRR, abs/2204.00755, 2022.
[CKK96] Anthony R Cassandra, Leslie Pack Kaclbling, and James A Kurien. Acting under uncertainty: Discrete bayesian models for mobile-robot navigation. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. IROS 96, volume pages 963-972. IEEE, 1996.
[CLCC99 Chenghui Cai, Xuejun Liao, and Lawrence Carin. Learning to explore and exploit in pomdps. In Y. Bengio, D. Schuurmans, Lafferty, Williams, and Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
[CLZ97] Anthony Cassandra, Michael L. Littman, and Nevin L. Zhang. Incremental pruning: A simple, fast, exact method for partially observable markov decision processes. In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, UAI'97, page 54-61, , San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc.
[DGZ22] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of markov equilibrium in stochastic games. arXiv preprint 03Xiv:2204.03991, 2022.
[DKJ+19] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1663-1674. PMLR, 2019.
[DLB17] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uni- form pac bounds for episodic reinforcement learning. Guyon, Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[DVPWR15] Finale Boshi-Velez, David Pfau, Frank Wood, and Nicholas Roy. Bayesian nonpara- metric methods for partially-observable reinforcement learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37:394-407, 2015.
[HDKM05] Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Reinforcement learning in pomdps without resets. 2005.
[EDKM07] Eyal Even-Dar, Sham Kakade, and Yishay Mansour. The value of observation for monitoring dynamic systems. In IJCAI, pages 2474-2479, 2007.
11

---

[EJKM22] Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforcement learning with short-term memory. CoRR, abs/2202.03983, 2022.
[FKQR21] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprini arxiv:2112.134483 2021.
[GDB16] Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A pac r1 algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pages 510-518. PMLR, 2016.
[GHLI9] Neha Priyadarshini Garg, David Hsu, and Wee Sun Lee. Despot-alpha: Online pomdp planning with large state and observation spaces. In Robotics: Science and Systems, 2019.
[GMR22] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Planning in observable pomdps in quasipolynomial time. arXiv preprint arXiv:220.047335 2022.
[Han98] Eric A Hansen. Solving pomdps by searching in policy space. In Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence, pages 21 1-219, 1998.
[Hau00] Milos Hauskrecht. Value-function approximations for partially observable markov decision processes. Journal of artificial intelligence research, 13:33-94, 2000.
[HDT20] Dongqi Han, Kenji Doya, and Jun Tani. Variational recurrent models for solving partially observable control tasks. In ICLR, 2020.
[HFOOa] Eric A. Hansen and Zhengzhu Feng. Dynamic programming for pomdps using factored state representation. In Proceedings of the Fifth International Conference AI Planning Systems, pages 130-139, 2000.
[HF00b] Milos Hauskrecht and Hamish Fraser. Planning treatment of ischemic heart disease with partially observable markov decision processes. Artificial intelligence in medicine, 18(3):221-22) -244, 2000.
[HKZ12] Daniel Hsu, Sham M. Kakade, and Tong Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 1865):1460-1140, 2012. JCSS Special Issue: Cloud Computing 2011.
[JJN21] Mehdi Jafarnia-Jahromi, Rahul Jain, and Ashutosh Nayyar. Online learning for unknown partially observable mdps. CoRR, abs/2102.12661, 2021.
[JJ++1] 17] Sebastian Junges, Nils Jansen, Ralf Wimmer, Tim Quatmann, Leonore Winterer, Joost- Pieter Katoen, and Bernd Becker. Permissive finite-state controllers of pomdps using parameter synthesis. CoRR, abs/1 7 10. 10294, 2017.
[JKA+ 17] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnbbe.. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1704-1713. PMLR, 06 11 Aug 2017.
[JKKL20] Chi Jin, Sham M Kakade, Akshay Krishnamurthy, and Qinghua Liu, Sample-efficient reinforcement learning of undercomplete pomdps. arXiv preprint arXiv:2006. 12484, 2020.
[JKSY20] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning (ICML), pages 4870-4879, PMLR, 2020.
[KAL16] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. arXiv preprint 160..02222.222.... 2016.
[KECM21a] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. Rein- forcement learning in reward-mixe mixing mdps. arXiv preprint 21..::2110.03743, 2021.
12

---

[KECM2IB] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Regret guarantees and lower bound. arXiv preprint arXiv:2102.04999, 2021.
[KLLM22] Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computational- statistical gaps in reinforcement learning. arXiv preprint 2202::2002.0444,, 2022.
[KMN99] Michael Kearns, Yishay Mansour, and Andrew Y Ng. Approximate planning in large pomdps via reusable trajectories. In NIPS, pages 1001-1007. Citeseer, 1999.
[KOA19] Sammie Katt, Frans Olichock, and Christopher Amato. Bayesian reinforcement learning in factored pomdps. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, page 7-15, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems.
[KS02] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polyno- mial time. Machine learning, 49(2):209-233 2002.
[LCSJ22] Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? arXiv preprint wrXiv:2204.0867. 2022.
[LGMO1] Christopher Lusena, Judy Goldsmith, and Martin Mundhenk. Nonapproximabiltty results for partially observable markov decision processes. Journal of artificial intelli- gence research, 14:83-103, 2001.
[Lit94] Michael L Littman. Memoryless policies: Theoretical limitations and practical results. From animals animats, 3:238-244 1994.
[LLC09] Hui Li, Xuejun Liao, and Lawrence Carin. Multi-task reinforcement learning in partially observable stochastic environments. J. Mach. Learn. Res., 10:1 jun 2009.
[LLCI]] Miao Liu, Xuejun Liao, and Lawrence Carin. The Infinite Regionalized Policy Repre- sentation. In Proceedings of the 28th International Conference on Machine Learning, pages 769-776. Omnipress, 2011.
[LLCI3] Miao Liu, Xuejun Liao, and Lawrence Carin. Online expectation maximization for reinforcement learning pomdps. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI '1, page 1 1501-1507. AAAI Press, 2013.
[LS17] Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. Artificial Intelligence and Statistics, pages 738-737. PMLR, 2017.
[LXX1]] Yanjie Li, Baoqun Yin, and Hongsheng Xi. Finding optimal memoryless policies of pomdps under the expected average reward criterion. European Journal of Operational Research, 211(3):556 567, 2011.
[MGK21] Lingheng Meng, Rob Gorbet, and Dana Kuli'c. Memory-based deep reinforcement learning for pomdp. ArXiv, hbbs///02.1234,, 2021.
[MHKL20] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kine- matic state abstraction and provably efficient rich-observation reinforcement learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6961-6977 PMLR, 13-18 Jul 2020.
[MKKC99]
Nicolas Meuleau, Kee-Eung Kim, Leslie Pack Kaelbling, and Anthony R. Cassandra. Solving pomdps by searching the space of finite policies. In Proceedings of the Fifteenth Conference on Uncertainty Artificial Intelligence, UAI'99, page 417-426, San Francisco, CA, USA, 1999, Morgan Kaufmann Publishers Inc.
13

---

[Mon82] George E. Monahan. State of the art-a survey of partially observable markov decision
processes: Theory, models, and algorithms. Manage. Sci., 28(1):1-16, jan 1982.
[MR05] Elchanan Mossel and Sébastien Roch. Learning nonsingular phylogenies and hidden markov models. CoRR, abs/cs/0502076. 2005.
[NES22] Tianwei Ni, Benjamin Eysenbach, and Ruslan Salakhutdinov. Recurrent model-free rl can be a strong baseline for many pomdps, 2022.
[PB04] Pascal Poupart and Craig Boutilier. Vdcbpi: an approximate scalable algorithm for large pomdps. NIPS, pages 1081-1088. Citeseer, 2004.
[PGT06] Joelle Pineau, Geoffrey Gordon, and Sebastian Thrun. Anytime point-based approx- imations for large pomdps. Journal of Artificial Intelligence Research, 27:335-380, 2006.
[PT87] Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathemattcc of operations research, 12(3):441-450 1987.
[PV08] Pascal Poupart and Nikos Vlassis. Model-based bayesian reinforcement learning in partially observable domains. In Proc Int. Symp. on Artificial Intelligence and Mathematics, pages 1-2, 2008
[RCdP07] Stephane Ross, Brahim Chaib-draa, and Joelle Pineau. Bayes-adaptive pomdps. In
J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
[RG02] Nicholas Roy and Geoffrey Gordon. Exponential family pea for belief compression in pomdps. Advances in Neural Information Processing Systems, 15:1667-1674, 2002.
[RPCaK11] Stéphane Ross, Joelle Pineau, Brahim Chaib-draa, and Piere Kreitmann. A bayesian approach for learning and planning in partially observable markov decision processes. J. Mach. Learn. Res., 12muul): jul 2011.
[RPPCD08] Stéphane Ross, Joelle Pineau, Sébastien Paquet, and Brahim Chaib-Draa. Online planning algorithms for pomdps. Journal of Artificial Intelligence Research, 32:663- 704, 2008.
[SBS05] Guy Shani, Ronen Brafman, and Solomon E. Shimony. Model-based online learning of pomdps. In João Gama, Rui Camacho, Pavel B. Brazdil, Alípio Mário Jorge, and Luis Torgo, editors, Machine Learning: ECML 2005, pages 353-364, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
[Sch90] Jürgen Schmidhuber. Reinforcement learning in markovian and non-markovian envi- ronments. In Proceedings of the 3rd International Conference on Neural Information Processing Systems, NIPS'90 90, page 500-506, San Francisco, CA, USA, 1990. Morgan Kaufmann Publishers Inc.
[SS12] Trey Smith and Reid Simmons. Heuristic search value iteration for pomdps. arXiv preprint arXiv: 2266.416. 2012.
[SVO5] Matthijs TJ Spaan and Nikos Vlassis. Perseus: Randomized point-based value iteration for pomdps. Journal of artificial intelligence research, 24:125-220, 2005.
[SV10] David Silver and Joel Veness. Monte-carlo planning in large pomdps. Neural Informa- tion Processing Systems, 2010.
[SYHLI3] Adhiraj Somani, Nan Ye, David Hsu, and Wee Sun Lee. Despot: Online pomdp planning with regularization. Advances in neural information processing systems, 26:1772-1780, 2013.
[TK03] Georgios Theocharous and Leslie Kaelbling. Approximate planning in pomdps with macro-actions. Advances Neural Information Processing Systems, 16:775-782, 2003.
14

---

[VLB12] Nikos Vlassis, Michael L. Littman, and David Barber. On the computational complexity of stochastic controller optimization in pomdps. ACM Trans. Comput. Theory, 4(4), nov 2012.
[W]]+21] Gellert Weisz, Philip Amortila, Barnabás Janzer. Yasin Abbasi- Yadkori, Nan Jiang. and Csaba Szepesvári. On query-efficient planning in mdps under linear realizability of the optimal state-value function. In Conference on Learning Theory, pages 4355 4385. PMLR, 2021.
[WDZ22] Chen- Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In Sanjoy Dasgupta and Nika Haghtalab, editors, Proceedings The 33rd International Conference on Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pages 1043-1096. PMLR, 29 Mar-01 Apr 2022.
[WL21] Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. CoRR, abs/2102.054000 2021.
[WME+22] Xintong Wang, Gary Qiurui Ma, Alon Eden, Clara Li, Alexander Trott, Stephan Zheng, and David C. Parkes. Using reinforcement learning to study platform economies under market shocks, 2022.
[WYDW21] Tianhao Wu, Yunchang Yang, Simon Du, and Liwei Wang. On reinforcement learning with adversarial corruption and its application to block mdp. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 1 11296- 11306. PMLR, 18- 24 2021.
[XCGZ21] Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps. arXiv preprint arXiv:2107.03635 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethies review guidelines and ensured that your paper conforms
them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
15

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' ro using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "hFv7hve55e", "reviewer": "Reviewer_C7us", "summary": "The paper proposes a quasi-polynomial-time algorithm for learning in a class of partially observable Markov decision processes (POMDPs). It builds on the recent set of results that noticed the reductions in the computational complexity of planning in POMDPs that comply with an assumption on the observability in the POMDP. ", "questions": "* When is it easy to check the underlying assumptions?\n* How much does the result rely on the complexity reduction in planning under the observability assumption and how much of it is specific to the learning setting? A discussion cannot hurt.", "limitations": "There is no explicit discussion of the limitations in the paper or an empirical study that would help the reader establish an intuition on the implications and limitations of the results.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper tackles a difficult problem and offers a novel perspective.\n* The direction of understanding the implications of imposing practically viable assumptions on POMDPs on planning and learning is an emerging one. It makes sense to investigate problems in this direction. \n* It is a relatively dense yet sufficiently clearly written paper. \n\nWeaknesses: \n* While I am sure the authors will claim that the paper is a theoretical one, a paper that argues to be not computationally intractable should provide empirical evidence of the implied traceability. \n* It relies on assumptions similar to those in the recent literature. Nevertheless, it is necessary to provide additional and convincing evidence that the assumptions can be checked in practice and they will hold for interesting and large classes of problem instances. The lack of empirical evidence as mentioned in the previous bullet point hurts here as well. \n* While with a different perspective, there is additional recent work that aims to cope with the computational impracticality of planning in POMDPs: https://arxiv.org/abs/2009.11459, https://arxiv.org/abs/2204.00755, and https://arxiv.org/abs/1710.10294. Contrast with this work would help and may broaden the interest in the current paper. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "drvgU_FT-h6", "reviewer": "Reviewer_kngr", "summary": "The paper introduces a method for approximately solving unknown POMDPs. The method relies on constructing an MDP approximation and a set of policies that incrementally improve coverage of that MDP's state space, thereby increasing the accuracy of the MDP approximation. The approach makes use of a novel exploration objective that uses the concept of barycentric spanners to ensure that every possible observation distribution can be represented as a linear combination of a small \"core\" set of observation distributions. The resulting algorithm has approximately optimal time complexity and quasi-polynomial sample complexity.", "questions": "(See numbered items above.)", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The paper covers a lot of difficult theoretical ground and communicates the high-level ideas very clearly.\n- The theoretical results appear to be correct, and the supplementary materials appear to be detailed enough that one could verify the claims presented in the main text, although I was only able to check them at a high level.\n- The section \"Overview of results\" is extremely helpful for communicating the high-level ideas quickly, and for providing a roadmap of the remainder of the paper.\n\n**Weaknesses:**\n\n1. Lines 135-141: I'm a little worried about the way the policies are defined here. It's fine to say a general policy is a distribution over deterministic policies, but when we execute that policy, we sample a deterministic policy from it, and follow that deterministic policy for the entire episode. My concern is: does this scheme necessarily include the optimal policy for the POMDP? Are all trajectories that can be achieved with a fully stochastic policy still supported under the resulting distribution? Is this construction allowed because the policy is conditioned on the entire history?\n\n2. I'm confused about a few things:\n\n    a. Line 46: \"A necessary first step towards solving the learning problem is having a computationally efficient planning algorithm.\" -> Is there a reason why a model-free approach wouldn't work?\n\n    b. Line 120: Why is reward a function of observations $O$? I'm used to seeing it depend on states $S$.\n\n    c. Lines 280-282: \"the formal latent state distribution induced by $\\pi$ is a linear combination of the formal latent state distributions with the same coefficients\" -> Why is this the case?\n\n3. In a few of the definitions and assumptions, I would have preferred to have more detail. However, I appreciate that the paper is quite short on space, so I understand that many sections have been significantly compressed already.\n\n    a. Assumption 1.1 defines the distance between two distributions as the sum of the differences in probability for each outcome. Why use this particular definition for $\\gamma$-observability?\n\n    b. In section 2.2, while I appreciate that the notation is presented up front, it would be helpful to see an example for why we need to define the probability of an event $\\mathbb{P}^\\mathcal{P}_\\pi(\\mathcal{E})$.\n\n    c. In section 2.4, the presentation of the product space $\\mathcal{Z}$ is confusing. It took until much later for me to realize that we need this because it's the form that the POMDP -> MDP conversion requires.\n\n    d. In Algorithm 3, lines 3-4, there are multiple definitions of $k$, which is confusing.\n\n    e. In line 331, I could not find a definition for $e_s$ anywhere. I assumed this was a unit/one-hot vector, so the $\\langle e_i, \\cdot \\rangle$ is equivalent to indexing the second term at position $i$. It would be helpful to have this notation explicitly defined, even if it's just in the appendix.\n\n-----\n\n**Review Summary:**\n\nThis paper seems useful for several reasons. First, it introduces an algorithm for learning in POMDPs that achieves optimal time complexity and quasi-polynomial sample complexity. Second, it presents a novel exploration scheme that relies on the concept of barycentric spanners, rather than the ubiquitous \"optimism under uncertainty\" principle. While I can only verify the correctness at a high level, the material is presented clearly and the high-level ideas are very approachable. Unfortunately, space limitations preclude a more detailed treatment in the main text, but the supplementary materials appear to more than make up for it. Accept.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Rd9HvaEWsJP", "reviewer": "Reviewer_9ek8", "summary": "This paper proposes a novel algorithm for learning tabular POMDPs based on belief contraction and barycentric spanners. \nBoth its sample complexity and computational complexity scales exponentially w.r.t the observable parameter $1/\\gamma$ and quasi-polynomially w.r.t $S,A,O,H$ and $1/\\alpha$.\n\n", "questions": "\n1.  Given that poly sample complexity is achievable  [LCSJ22], do you think one can combine the techniques in this paper and  [LCSJ22] to obtain poly sample and quasi-poly computation algorithm?\n\n2. The belief contraction result hints that a POMDP can be approximated by an MDP by viewing the most recent M-step observations-actions as states. So I am curious in stead of using the barycentric spanners, can we simply run UCRL or other tabular MDP algorithms on this MDP? ", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a nice paper with interesting results and novel analysis. I enjoy reading it.\n\nStrength\n\n1. To my knowledge, this is the first quasi-polynomial time algorithm for learning tabular MDPs under reasonable assumptions.\n\n2. The application of barycentric spanners is novel and the analysis is nontrivial.\n\n\nWeakness\n\n1. The sample complexity is exponential in $1/\\gamma$ and quasi-polynomially in all other parameters. If I understand correctly, the algorithms in [LCSJ22] only require a polynomial number of samples to learn a near-optimal policy under the same observable condition. (Nonetheless, the algorithms in [LCSJ22]  seem to require exponential time to implement as pointed out in this work. ) I believe these differences should be pointed out explicitly in the main paper. \n\n2. The observable assumption can never be satisfied when the number of states is larger than the number of observations. Any comments on how to address this limitation and generalize the results in this paper?\n\n\n [LCSJ22] Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? arXiv preprint arXiv:2204.08967, 2022.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept