Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction
Authors: Dilip Arumugam
Satinder Singh
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayes-Adaptive Markov Decision Process
Bayesian reinforcement learning
Exploration
Planning

Abstract: The Bayes-Adaptive Markov Decision Process (BAMDP) formalism pursues the Bayes-optimal solution to the exploration-exploitation trade-off in reinforcement learning. As the computation of exact solutions to Bayesian reinforcement-learning problems is intractable, much of the literature has focused on developing suitable approximation algorithms. In this work, before diving into algorithm design, we first define, under mild structural assumptions, a complexity measure for BAMDP planning. As efficient exploration in BAMDPs hinges upon the judicious acquisition of information, our complexity measure highlights the worst-case difficulty of gathering information and exhausting epistemic uncertainty. To illustrate its significance, we establish a computationally-intractable, exact planning algorithm that takes advantage of this measure to show more efficient planning. We then conclude by introducing a specific form of state abstraction with the potential to reduce BAMDP complexity and gives rise to a computationally-tractable, approximate planning algorithm.

Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction
Dilip Arumugam
Satinder Singh DeepMind, London laveja@deepminde com
Department of Computer Science Stanford University dilip@cs stanf fonfood.eet edu
Abstract
The Bayes-Adaptive Markov Decision Process (BAMDP) formalism pursues the Bayes-optimal solution to the exploration-exploitaiiie learning. As the computation of exact solutions Bayesian reinforeeeentleamiingg problems is intractable, much of the literature has focused on developing suitable approximation algorithms. In this work. before diving into algorithm design, we first define, under mild structural assumptions, a complexity measure for BAMDP planning. As efficient exploration BAMDPs hinges upon the judicious acquisi- tion of information, our complexity measure highlights the worst-case difficulty of gathering information and exhausting epistemic uncertainty. To illustrate its significance, we establish computationally wwwooonlllllinitaabbbbaa exact planning algorithm that takes advantage of this measure to show more efficient planning. We then con- clude by introducing specific form of state abstraction with the potential to reduce BAMDP complexity and gives rise to a computationallly-raatii approximate planning algorithm.
trade-off in reinforcement
Introduction
The Bayes-Adaptive Markov Decision Process (BAMDP) [Duff, 2002] is classic formalism encap- sulating the optimal treatment of the opplorationeexploiaatoon trade-off by a reinforcement-leamee agent with respect to prior beliefs over an uncertain environment. Unfortunately, the standard formu- hyperstate space (that is, the joint collection of environment
lation suffers from an intractably- states coupled with the agent's current state of knowledge over the unknown environment) and much of the literature has been dedicated to identifying suitable approximations [Bellman and Kalaba, 1959, Dayan and Sejnowski, 1996, Duff and Barto, 1997, Dearden et al., 1998, Strens, 2000, Duff, 2001, 2003b,a, Wang et al., 2005, Poupart et al., 2006, Castro and Precup, 2007, Kolter and Ng, 2009, Asmuth et al., 2009, Dimitrakakis, 2009, Sorg et al., 2010, Araya-López et al., 2012, Guez al., 2012, 2013, 2014, Ghavamzadeh et al., 2015, Zintgraf et al., 2019]. In this work, we take steps toward clarifying the hardness of BAMDPs before outlining an algorithmic concept that may help mitigate problem difficulty and facilitate near-optimal solutions.
First, we introduce the notion of information horizon as a complexity measure on BAMDP plamning. characterizing when it is truly difficult to identify the underlying uncertain environment. Naturally, the agent's state knowledge at each timestep (a component of the overall BAMDP hyperstate) reflects its current epistemic uncertainty and, as the agent accumulates data, this posterior concentrates, exhausting uncertainty and identifying the true environment; after this point, the Bayes-optimal policy naturally coincides with the optimal policy of the underlying Markov Decision Process (MDP). Simply put, the information horizon quantifies the worst-case number of timesteps needed for the agent to reach this point whereupon there is no more information to be gathered about the uncertain environment.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

With this complexity measure in hand, we then entertain the idea of epistemic state abstraction as an effective algorithmic tool for trading off between reduced information horizon (complexity) and sear-Bayes-optimalii of the corresponding planning solution. Intuitively, as the total number of knowledge states an agent may take on drives the intractable size of the hyperstate space, we operationalize state abstraction [Li et al., 2006, Abel et al., 201 6] to perform lossy compression of the epistemic state space, inducing a "smaller" and more tractable BAMDP for planning; our results not only mirror those of analogous work on state aggregation for improved efficiency in traditional MDP planning [Van Roy, 2006] but also parallel similar findings [Hsu et al., 2007, Zhang et al., 2012] on the effectiveness of belief state aggregation in partially-observve MDP (POMDP) planning [Kaelbling et al., 1998].
On the whole, our work provides one possible answer to a question that has already been asked and answered several times in the context of MDPs [Bartlett and Tewari, 2009, Jaksch et al., 2010, Farahmand, 2011 1, Maillard et al., 2014, Bellemare et al., 2016, Arumugam et al., 2021, Abel et al., 2021]: how hard my BAMDP? While the remainder of the paper goes on to examine how one particular mechanism for reducing this complexity can translate into more efficient planning algorithm, we anticipate that this work can serve as a starting point for building a broader taxonomy of BAMDPs, paralleling existing structural classes of MDPs [Jiang et al., 2017, Sun et al., 2019, Agarwal et al., 2020, Jin et al., 2021].
2 Problem Formulation
In this section, we formally define BAMDPs studied in this paper. As point of contrast, we begin by presenting the standard MDP formalism used throughout the reinforcement-lerrnig literature [Sutton and Barto, 1998]. We use A(X) to denote the set of all probability distributions with support on an arbitrary set X' and denote, for any natural number N E N. the index set as
[N] = 21, ......., N). For any two arbitrary sets X' and y, we denote the class of all functions mapping from X' y as (X - >} & {f f: xx x V}.
2.1 Markoy Decision Processes
We begin with a sequential decision-making problem represented via the traditional finite-horizon Markov Decision Process (MDP) [Bellman, 1957, Puterman, 1994] (S, R. T,3, H) where S is finite set of states, A is a finite set of actions, R : S A + [0, 1] is a deterministic reward function, T SxA- + (SS) is transition function prescribing next-state transition distributions for all state-action pairs, 3 E (S)) is an initial state distribution, and H E N is the horizon denoting the agent's total number of steps interactions with the environment. An agent's sequential interaction within this environment proceeds in each timestep h E [H] starting with an initial state $1 ~ B(.), by observing the current state S/ S, selecting action On E A, and then enjoying reward R(sh. ax) as the environment transitions to 81+1 T- 8h. an.. Action selections made by the agent are governed by its non-stationary policy m: collection of H stationary, deterministic policies π = (M1, ........ -T)) ) where Vh. E [H] u S + A. We quantify the performance of policy x at timestep h E [H] by its induced value function V S IR denoting the expected sum of future rewards by deploying policy
π from particular state E S: (s)
E R(sh ax) Sh
where the expectation
integrates over randomness in the environment transitions. Analogously, define the value function induced by policy т at timestep h as Q7, : S x A > R which denotes the expected future sum of rewards by being in particular state E S, executing particular action E A.
and then following policy thereafter: Q7 a) EE
Σ R(SN ax) sh s, ah
We are
guaranteed the existence of optimal policy .²* that achieves supremal value VT,(s) sup V (i((s *е
for all E S, [H] where the policy class contains all deterministic policies II {- T S A). Since rewards are bounded in [o, 1]. we have that 0 < (s) < (s) < H - h + 1 for all
E S [H]. and म. These value functions obey the Bellman equation and the Bellman optimality equation, respectively:
(s) (T)) (s) max (s.a), aEA
V+++(s)= -0 (s+ -0 Vs E
2

---

(% = R) + (s)], @)(s,a) (Bs,,))BBxTTe ~T(aa) [Viti
2.2 Bayes-Adaptive Markov Decision Processes
The BAMDP formalism offers Bayesian treatment of agent interacting with uncertain MDP. More specifically, a decision-makinn agent is faced with a MDP M = (S, .A. R. To, 3, H) defined around an unknown transition function To for some latent parameter 0 O. Prior uncertainty in 0 is reflected by the distribution p()). In classic work on BAMDPs with finite state-action spaces, the parameters denote visitation counts and p(0) is a Dirichlet distribution, so as leverage the convenience of Dirichlet- multinomial conjugacy for exact posterior updates [Duff, 2002, Poupart al., 2006]. For our purposes. we will assume an alternative parameterization whose importance will be made clear later when defining our complexity measure.
Assumption 1. We assume that known and |+| < oo such that an agent is only ever reasoning about its uncertainty over finite set of [Q] known MDPs. We further make realizability assumplion that the true parameters reside in this finite set, 0 e θ.
Under Assumption 1, an agent's s prior uncertainty in To is reflected by the distribution p(0) E (()) which, with each step of experience encountered by the agent, may be updated via Bayes' rule to recover corresponding posterior distribution in light of observed data from the environment. For simplicity, we do not concern ourselves with the computation
the posterior and instead assume access to deterministic B: A()) x S x x S - A()) that performs an exact posterior update to any input distribution E (()) based on the experience tuple (s,a,s') E S x A x S in (11) time.
The corresponding BAMDP for M is defined around so-called hyperstate space X' = S x A(O) such that any hyperstate r (s. p) X denotes the agent's original or physical state s S within the true MDP while y E (()) denotes the agent's information state or epistemic state [Lu et al., 2021 ]] about the uncertain environment; intuitively, the epistemic state represents the agent's knowledge of the environment based on all previously observed data. This gives rise to the BAMDP
(X A. R. T.3, H) where A is the same action set as the original MDP M. R : X' A - [0. 1] is the same reward function as in M (that is, R(s,, p). a) = R(s, a) V(s,p) E X. E A), B A(X) is defined as 3 = 3 x 5y(0) where 6p(e) denotes a Dirac delta centered around the agent's prior p(0). and H is the same horizon as MDP M. Due to the determinism of the posterior updates given by B, the BAMDP transition function T X' x A A(X) is defined
T(x' x a = Σ To a))(() (p' B(p,,,,,''),
EE
where ='=(''p')) E X. The associated BAMDP policy π = (T T2 TH), TA 2' e [H] selects actions based on the current state of the MDP as well as the agents accumulated knowledge of the environment thus far. With these components, we may define the associated BAMDP value functions with x' (5/, B(p, 8, a, s')):
(x) = (x))
V (x) = max Q1 a), aEA
(x+ =0 V2+z((z) =0
Vx E E
QT(2, a) = R(s,a)+ Σ To('' | (.)
(1 = R(s,a) a)+ + ΣTa( s, ()))))))V (x.).
s'.0
Based on these optimality equations, we see that the optimal policy of BAMDP achieving supremal value VA across all timesteps h [H] is the Bayes-optimal policy which appropriately balances the exploration--xpploittton trade-off in reinforcement learning. An observation is that this Bayes-optimal policy will tend to achieve lower value than the optimal policy of MDP M the agent takes more informative (possibly sub-optimal) actions to identify the true underlying environment.
3 Related Work
Bellman and Kalaba [1959] offer the earliest formulation of Bayesian reinforcement learning, whereby the individual actions of a decision-making agent not only provide an update to the physical state
For ease of exposition, we focus on uncertainty in transition dynamics although one could model uncertainty in either the reward function the full MDP model (rewards & transitions).
3

---

of the world but also impact the agent's internal model of how the world operates. Dayan and Sejnowski [1996] follow this line of thinking to derive implicit exploration bonuses based on how an agent performs posterior updates. Kolter and Ng [2009] make this more explicit and incorporate a specific visitation-based bonus that decays with the concentration of the agent's Dirichlet posterior. As an alternative, Sorg et al. [2010] incorporate an exploration bonus based on the variance of the agent's 's posterior while Araya-López et al. [2012] achieve optimistic exploration by boosting transition probabilities. Duff' and Barto [1997] identify multi-armed bandits (that is, MDPs with exactly one state and arbitrarily many actions) as a unique setting where the Bayes-optimal solution is computationally tractable through the use of Gittins indices [Gittins, 1979]. While the vast space of more complicated BAMDPs are computationally intractable, a goal of this paper is to add a bit of nuance and clarify when one might still hope to recover efficient, approximate planning. This is also distinct from the PAC-BAMDP framework introduced by Kolter and Ng [2009], which serves as a characterization of algorithmic efficieney, rather than problem hardness.
Representing uncertainty in the optimal value function rather than environment transition function, Dearden et al. [1998] derive practical Bayesian Q-learning algorithm by foregoing representation of the epistemic state and instead resampling Q"-values at each timestep. Strens [2000] finds an alternate, tractable solution by lazily updating the epistemic state at the frequency of whole episodes, rather than individual timesteps; a long line of work [Agrawal and Jia, 2017, Osband et al., 201 6a,b, Osband and Van Roy, 2017, O' D'Donoguue et al., 2018, Osband et al., 2019] analyzes this type of approximation to the Bayesian reinforeement-lerrnigg problem thcoretically and also explores how to scale these solution concepts with deep neural networks.
Duff [2001] finds tractability in representing policies as finite-state stochastic automata, noting structural similarities between BAMDPs and pabteally MDPs (POMDPs) [Kaelbling et al., 1998]; this type of thinking is further extended by Poupart et al. [2006] who exploit similar structure between the optimal value functions of BAMDPs and POMDPs. Duff [2003a] examine improved memory requirements when applying actor-critic algorithms [Konda and Tsitsiklis, 2000] to BAMDPs while Duff [2003b] consider how to approximately model the stochastic process of the evolving epistemic state via diffusion models. Wang et al. [2005] introduce a sparse- sparse-sampling approach [Kearns et al., 2002] for balancing computational efficiency against fidelity to Bayes-optimal action selection. An analogous sparse-sampling approach is also developed by Castro and Precup [2007], but with linear- programmigggg methodology for value-function approximation. A line of work [Guez et al., 2012, 2013, 2014] develops more scalable, sparse-sampling lookahead approaches on the back of Monte-Carlo tree search [Koesis and Szepesvári, 2006]; these algorithms are somewhat similar in spirit to the approach of Asmuth et al. [2009] who merge multiple posterior samples into single model while Guez et al. [2014] keep each sample distinct and integrate out the posterior randomness. For more complete and detailed survey of Bayesian reinforcement learning, we refer readers to Ghavamzadeh et al. [2015]. Crucially, the aforementioned approaches largely revolve around ignoring the epistemic state, lazily updating the epistemic state, or approximating the impact of the epistemic state via random sampling. In contrast, this work offers a new approach and highlights how lossy compression of the epistemic state may naturally reduce BAMDP hardness. Perhaps the most related prior work is by Lee al. [2018] who introduce a practical ppproximaae-planniiii approach by quantizing the epistemic state space; this paper clarifies the theoretical ramifications of this quantization step.
Our work is also connected to analyses of approximate value iteration [Bellman, 1957] in the MDP setting [Tseng, 1990, Littman al., 1995], where more recent work has managed recover improved sample complexity bounds for approximate value iteration [Sidford et al., 201 8b,a]. Like Kearns and Singh [1999], our algorithms utilize exact value iteration almost as black box and it is an open question for future work to see if similar ideas and proof techniques for these approximate variants might be leveraged in the BAMDP setting. Crucially, the variants of value iteration introduced in this work are merely backdrop for illustrating the utility of our complexity measure and, more generally, a regard for underlying information structure in BAMDPs.
The particular class of epistemic state abstraction introduced and studied in this work revolves around the covering number of the epistemic state space. Curiously, this deepens an existing connection between BAMDPs and POMDPs [Duff, 2001], where a line of work establishes the covering number of the belief state space as a viable complexity measure for the latter both in theory [Hsu al., 2007] and in practice [Zhang et al., 2012]. In a less related but similar vein, Kakade et al. [2003a] establish a provably siiforreement-earmee algorithm when the MDP state space is a metric space;

---

their corresponding sample complexity guarantee depends on the covering number of the state space under the associated metric. Our planning complexity result for abstract BAMDPs mirrors those established by these works in its dependence on the covering number of the epistemic state space.
4 The Complexity of BAMDP Planning
In this section, we examine the difficulty of solving BAMDPs through the lens of a classic planning algorithm: value iteration [Bellman, 1957]. Due to space constraints, we relegate pseudocode for all discussed algorithms to Appendix A. We begin with an quick review of the traditional algorithm applied to our setting before introducing the information horizon as a complexity measure for BAMDPs. This quantity gives rise to a more efficient planning algorithm for BAMDPs that waives excessive dependence on the original problem horizon. order to facilitate an analysis of planning complexity in BAMDPs via value iteration, we require a finite hyperstate space X. For now, we will assume that X is finite, but still considerably large, by virtue of an aggressively- the (l0) 1) -immenniionall simplex. also considered in the empirical work of Lee et al. [2018]:
quantization of
Assumption 2. We assume the existence of a suitable, fixed quantization of simplex ((0) C A()) where| [ < oc such that the BAMDP hyperstate space X = S x (()) is finite, |X| < co.
4.1 Naive Value Iteration
To help build intuitions, we begin by presenting a typical version of value iteration for finite-horizon
BAMDPs Algorithm 1. This algorithm iterates backwards through the H timesteps, computing Q% across every byperstate-action avoid a square dependence on the hyperstate space (1x)²) and instead only require O(S to compute next-state value. Consequently, the resulting planning complexity of Algorithm is (([])))][[]]))) Clearly, this represents an onerous burden for two distinct reasons: (I) we are forced to contend with potentially very large horizon H and (2) we must also search through the entirety of the hyperstate space, X. In the sections that follow, we alleviate the burdens of challenges (1) and (2) in series, using our new notion of information horizon to mitigate the impact of H/ and leveraging epistemic state abstraction to further reduce the role of (x), where the latter occurs at the cost of introducing approximation error.
pair. With the provision of our posterior update oracle B, we
4.2 Information Horizon
As noted in the previous section, our planning complexity suffers from its dependence on the BAMDP horizon H. A key observation, however, is that once an agent has completely resolved its uncertainty and identified one of the [0] environments, all that remains is to deploy the optimal policy for that particular MDP. As an exaggerated but illustrative example of this, consider a BAMDP where any action executed at the first timestep completely identifies the true environment ! E O. With no residual epistemic uncertainty left, the Bayes-optimal policy would now completely coincide with the optimal policy and take actions without changing the epistemic state since, at this point, the agent has acquired all the requisite information about the previously unknown environment. Even if the problem horizon H is substantially large, simple BAMDP like the one described should be fairly easy to solve as epistemic uncertainty is so easily diminished and information is quickly exhausted; is this principle that underlies our hardness measure.
Let be arbitrary non-stationary policy. For any hyperstate x E X, we denote by PT (2), x)) the probability that policy ग visits hyperstate x at timestep h. With this, we may define the reachable hyperstate space of policy π at timestep h e [H] as X {ar E X IPT (Ix = z) > 0} c X. In words, the reachable hyperstate space of a policy π at particular timestep is simply the set of all possible hyperstates that may be reached by π at that timestep with non-zero probability. Recall that for any hyperstate x = (s.p) E X, the epistemic state p E A(0) is a (discrete) probability distribution, for which we may denote its corresponding entropy as H(p). Given a BAMDP, we define the information horizon of a policy π as [(T) = inf {h E [H] Vzn, = (sh. Ph) E X H(.)) = 0}. The information horizon of a policy, if it exists, identifies the first timestep in [H] where, regardless of precisely which hyperstate is reached by following at this timestep, the agent has fully resolved all of its epistemic uncertainty over the environment 0. At this point, we call attention back to our structural Assumption I for BAMDPs and note that, under the standard parameterization of epistemic
5

---

state via count parameters for Dirichlet priors/posteriors we would only be able to assess residual epistemic uncertainty through differential entropy which, unlike the traditional (Shannon) entropy H.(.), is potentially negative and has no constant lower bound [Cover and Thomas, 2012].2 Naturally, to compute the information horizon of the BAMDP, we need only take the supremum across the non-stationary policy class: I sup I(Tr), where IT = (X - A}.
m=11"
Clearly, when it exists, we have that 1 S SIS H; the case where I = 1 corresponds to having a prior p(0) that is itself Dirac delta óg centered around the true environment, in which case, is known completely and the agent may simply compute and deploy the optimal policy for the MDP (S, A, R, To: B3 H). . At the other end of the spectrum, information horizon I = H suggests that, in the worst case, an agent may need all H steps of behavior in order to fully identify the environment. In the event that there exists any single non-stationary policy π for which the infimum of I(x) does not exist (that is, [(T) = oo), then clearly I = oo; this represents the most difficult, worst-case scenario wherein an agent may not always capable of fully resolving its epistemic uncertainty within the specified problem horizon H. For certain scenarios, the supremum taken over the entire non- stationary policy class may be exceedingly strict and, certainly, creates a computational intractability should one wish to operationalize the information horizon algorithnically; in these situations, it may be more natural to consider smaller or regularized policy classes (for instance, the collection of expressible policies under chosen neural network architecture) that yield more actionable notions of BAMDP complexity. We now go on to show how the information horizon can be used to design more efficient BAMDP planning algorithm whose planning complexity bears a more favorable dependence on H.
4.3 Informed Value Iteration
The key insight from the previous section is that, when the information horizon exists and once an agent has acted for I timesteps, the Bayes-optimal policy necessarily falls back to the optimal policy associated with the true environment. Consequently, if the solutions all [0] possible underlying MDPs are computed up front, an agent can simply backup their optimal values starting from the Ith timestep, rather than backing up values beginning at the original horizon H. This high-level idea is implemented as Algorithm 2 which assumes access to a sub-routine mdp_ sap_value___ welluleeteaatiioo that consumes a MDP and produces the associated optimal value function for the initial timestep. Vi*.
Since the underlying unknown MDP is one of [+] possible MDPs, Algorithm 2 proceeds by first computing the optimal value function associated with each of them in sequence using standard value iteration, incurring a time complexity of [[ - -)). Note that the horizon of each MDP is reduced to H I acknowledging that, after identifying the true MDP in I steps, an agent has only H - I steps of interaction remaining with the environment. With these [+] solutions in hand, the remainder of the algorithm proceeds with standard value iteration for BAMDPs (as in Algorithm 1), only now bootstrapping value from the I timestep, rather than the original problem horizon H. Note that in Line 9, we could also compute the corresponding @ in question by taking the mean of the next epistemic state p', however, we use this calculation to make explicit the fact that, by definition of the information horizon, the agent has uncertainty in 0 at this point. As result, instead of planning complexity that scales the hyperstate space size by a potentially large problem horizon, we incur a complexity of O [|O||S]|AA| (IX + (S) - I))). Naturally, as the gap between the information horizon I and problem horizon H increases, the more favorably Algorithm 2 performs relative to the standard value iteration procedure of Algorithm 1.
In this section, we've demonstrated how the information horizon of a BAMDP has the potential to dramatically reduce the computational complexity of planning. Still, however, the corresponding guarantee bears an unfavorable dependence on the size of the hyperstate space X' which, in the reality that voids Assumption 2, still renders both Algorithms and 2 as computationally intractable. Since this is likely inescapable for the problem of computing the exact optimal BAMDP value function, the next section considers one path for reducing this burden at the cost of only being able to realize an approximately-optimal value function.
Prior work (see, for example, Theorem I of Kolter and Ng [2009]) operating with the Dirichlet parameteri- zation will make an alternative assumption for similar effect where epistemic state updates cease after a certain number of state-action pair visitations.

---

5 Epistemic State Abstraction
5.1 State Abstraction in MDPs
As numerous sample-efficinncy guarantees in reinforcement learning [Kearns and Singh, 2002, Kakade et al., 2003b, Strehl et al., 2009] bear dependence on the size of the MDP state space, [8], large body of work has entertained state abstraction as a tool for improving the dependence on state space size without compromising performance [Whitt, 1978, Bertsekas et al., 1988, Singh et al., 1995, Gordon, 1995, Tsitsiklis and Van Roy, 1996, Dean and Givan, 1997, Ferns et al., 2004, Jong and Stone, 2005, Li et al., 2006, Van Roy, 2006, Ferns et al., 2012. Jiang al., 2015a, Abel et al., 2016, 2018, 2019. Dong et al., 2019, Du et al., 2019, Misra et al., 2020, Abel, 2020]. Broadly speaking, state abstraction Φ S + S maps original or ground states of the MDP into abstract states in Sg. Typically, one takes é to be defined with respect to an abstract state space S& with smaller complexity (in some sense) than S: in the case of state aggregation where all spaces in question are finite, this desideratum often takes the very simple form of S < (S). Various works have identified conditions under which specific classes of state abstractions é yield no approximation error and perfectly preserve the optimal policy of the original MDP [Li et al., 2006], as well as conditions under which near-optimal behavior is preserved [Van Roy, 2006, Abel et al., 2016]. As its name suggests, our proposed notion of epistemic state abstraction aims to lift these kinds of guarantees for MDPs over to BAMDPs and contend with the intractably large hyperstate space.
Before examining BAMDPs, we provide brief overview of how state abstraction impacts the A,
traditional MDP, as a point of comparison with the BAMDP setting. Given MDP AS R, T. H).
a state abstraction Φ : S + S₂ induces a new abstract MDP Ma = g.. A, R. s, T H) where the abstract reward function Ræ S. x A -> [0, 1] and transition function To S x A - (SSs) are both defined with respect to a fixed, arbitrary weighting function measures the contribution of each individual MDP state s E S to its allocated abstract state (ss). More specifically, w is required to induce probability distribution on the constituent MDP states of each abstract state: V8g E So.
S + [0, 1] that, intuitively,
w(s) = 1. This fact allows for well-defined rewards and (96)
Σ
transition probabilities given by
R. (sp.
Σ R(s,a)w(s)) SE (s0)
Tal''s a), a)=
Σ Σ
T(s' 88, s))))(s)
SEO (NO) S'E ((()))
As studied by Van Roy [2006], the weighting function s does bear implications the efficiency of learning and planning. Naturally, one may go on to apply various planning or reinforcement-leariigg algorithms to M& and induce behavior in the original MDP MM by first applying & the current state 8 E S and then leveraging the optimal abstract policy or abstract value function of Ma. Conditions under which & will induce a MDP Ms that preserves optimal near-optimal behavior studied by Li et al. [2006]. Van Roy [2006], Abel et al. [2016].
5.2 Compressing the Epistemic State Space
In this section, we introduce epistemic state abstraction for BAMDPs with the goal of paralleling the benefits of state abstraction MDPs. In particular, we leverage the fact that our epistemic state space (e) = A |||- is the (|@) - -)ddimension probability simplex. Recall that for any set 2; any threshold parameter 5 > 0; and any metric p: 2 - R on 2, set {21,22.... 22. 2x) å-cover of 2 if V2 E 2, Ei E [K] such that p(2, 2,) S In this work, we will consider 8-covers with arbitrary parameter 5 > defined on the simplex A |0|-1 with respect to the total variation distance metric on probability distributions, denoted || |/Tv. Let E A()) be the ith standard basis vector such that H(e,) O, Vi E [[o]]- We define an epistemic state abstraction with parameter 5 >> 0 as the projection from A(O) onto the smallest 8-cover of A(O) with respect to || |/Tv that contains all standard basis vectors (21,62,... Ejer J: paralleling notation for the 5-covering number, we use A(A(O), Il lIrv) to denote the size of this minimal cover and, for consistency with the state-abstraction literature in MDPs, use Φ A(9) + Ao(O) to denote the epistemic state abstraction. Briefly, we note that while computing exact 8-covers a NP-hard problem, approximation algorithms do exist [Hochbaum, 1996, Zhang et al., 2012]; our work here is exclusively concerned with establishing theoretical guarantees that warrant further investigation of such approximation techniques to help solve BAMDPs in practice.
7

---

It is important to note that while there are numerous statistical results expressed in terms of covering numbers (for instance, Dudley's Theorem [Dudley, 1967D, our definition of covering number differs slightly in its inclusion of the standard basis vectors. The simple reason for this constraint is that it ensures we may still count on the existence of abstract epistemic states for which an agent has fully exhausted all epistemic uncertainty in the underlying environment. Consequently, we are guaranteed that the information horizon is still a well-defined quantity under this abstraction'. As increases, larger portions of the epistemic state space where the agent has residual, but still non-zero, epistemic uncertainty will be immediately mapped to the nearest standard basis vector under Φ. If such a lossy compression is done too aggressively, the agent's 's beliefs over the uncertain environment may prematurely and erroncously converge. On the other hand, if done judiciously with a prudent setting of 6, one has the potential to dramatically reduce the complexity of planning across much smaller, finite hyperstate space and recover an approximately-optinee
BAMDP value function.
To make this intuition more precise, consider an initial BAMDP (X, A, R, T, 3, and, given an epistemic state abstraction o (+) + Ae(O) with fixed parameter 5 > O, we recover an induced abstract BAMDP (Kx,, A. R.b T Φ, B.. H) where, most importantly X² = S x ( Just as in the MDP setting, the model of the abstract BAMDP depends on a fixed, arbitrary weighting function of the original epistemic states w A()) - [0, 1] that adheres to the constraint: Vpp (O), Sg-M(ns ((n)) (p) = 1, which means abstract rewards and transition probabilities for a current and next abstract hyperstates, 2 pb) and x's (s', .')). are given by
Ro(Ig, 1 (p-)(p))
R(s,a)u(p)dp= = R(s,a) / R(I, a(w))) (po)
(ps)(p)) w())dp= = R(s,a).
T (1's x a)= = [
w(p)
Σ NEB ((%)
7 x, d)p, where x = (s, p) and x' = (s',
(po(
The initial abstract hyperstate distribution is defined as 3==
= do()(()) where 3 (SS) denotes the initial state distribution of the underlying MDP while o)(p())) is a Dirac delta centered around the agent's 's original prior, p(0), projected by & into the abstract epistemic state space. Observe that the abstract BAMDP transition function is stochastic with respect the next abstract epistemic state p/g- unlike the original BAMDP transition function whose next epistemic states deterministic. This is, perhaps, not a surprising observation as it also occurs in standard state aggregation of deterministic MDPs well. Nevertheless, it is important to note the corresponding abstract BAMDP value functions must now acknowledge this stochasticity for any abstract policy π = (T To.2,.... TT,H). Tah Xx A, vh (H]:
Vol 27 (Fro Tan(())) (Tn) = max 2h,1 (1 DEA
VzHH-1(T0)) =0 V (0.41((0)) = Var Xo:
(T = R(s,a)+ ITol'ss Te a) Vo) (x/b): a)) = R((,
Σ Tala's VVo 8 K'p
''
Beyond the fact that this abstract BAMDP enjoys reduced hyperstate space, we further observe that the information horizon of this new BAMDP, Iz,, has the potential to be smaller than that of the original BAMDP. That is, if I steps are needed to fully resolve epistemic uncertainty in the original BAMDP then, by compressing the epistemic state space via o. we may find epistemic uncertainty exhausted in fewer than I timesteps within the abstract BAMDP. Furthermore, for a suitably large setting of the 8 parameter, we also have cases where the original BAMDP has I = co while I,p < oc; in words, whereas it may not have been possible to resolve all epistemic uncertainty within H timesteps, compression of the epistemic state space reduces this difficulty in the abstract problem as knowledge states near (in the total-variation sense) each vertex of the probability simplex e are immediately aggregated. Due to space constraints, we defer further discussion of the abstract information horizon and its relationship with the original information horizon to Appendix C.
"Noe that an alternative would be to introduce an additional constant 7 E R and define the information horizon based on H(p) 7: construction avoids carrying this cumbersome additional parameter dependence
the results.
'One could also imagine abstracting over the original MDP state space S which, for clarity, we do not consider in this work.
8

---

As toy illustration of last scenario, consider & with å sufficiently large such that any step from the agent's prior distribution immediately maps to a next abstract hyperstate with no epistemic uncertainty. Clearly, regardless of I. we have an abstract BAMDP where I = 2. Of course, under such an aggressive abstraction, we should expect to garner an unfavorable degree of approximation emror between the solutions of the abstract and original BAMDPs. The next section makes this error analysis and performance loss precise alongside an approximate planning algorithm that leverages the reduced complexity of abstract BAMDPs to recover near-optimal solution to the original BAMDP of interest.
5.3 Informed Abstract Value Iteration
Observe that if, after inducing the abstract BAMDP according to a given epistemic state abstraction é, the resulting information horizon is finite Ip < oc, then are in a position to Algorithm on the abstract BAMDP. Moreover, we no longer need the crutch of Assumption 2 as, by definition of é, we are guaranteed finite abstract hyperstate space of size [2y] |8| (N(A(O) 5, l|TT). With the solution to the abstract BAMDP in hand, we can supply values to any input hyperstate of the original BAMDP = (s, p) E X by simply applying querying the value of the resulting abstract hyperstate (s, <(p) E Xz.. We present this approximate BAMDP planning procedure as Algorithm 3.
the agent's current epistemic state p and
By construction, this algorithm inherits the planning complexity guarantee of Algorithm 2. specialized to the abstract BAMDP input, yielding O ([0] s| (A(A( I (H I=)))- A key feature of this result is that we entirely forego a (direct) dependence on the hyperstate space of the original BAMDP and, instead, take on dependencies with the size of the abstract hyperstate space, |x = |S| (S) ó, =|TV)), and the abstract information horizon Ig. While both terms decrease
there a delicate balance to be maintained between the ease with which one may solve the abstract BAMDP and the quality of the resulting solution when deployed in the original BAMDP of interest. We dedicate the remainder of this section to making this balance mathematically precise. Due to space constraints, all proofs are relegated to Appendix B. A natural first step in our analysis to establish an approximation error bound:
Proposition 1. Let Vř and Va,, denote the optimal original and abstract BAMDP value functions, respectively, for any limestep i E [H]. Let d be an epistemic state abstraction as defined above. Then, max V1 Va, (+(x)) < 2H( h))HH h 1)-
xEX
In order to establish complimentary performance-loss bound, we require an intermediate result characterizing performance shortfall of a BAMDP value function induced by greedy policy with respect to another near- oetrmmp BAMDP value function. The analogue of this result for MDPs is proven by Singh and Yee [1994], and the proof for BAMDPs follows similarly.
Proposition 2. Let V = (Vi V2...., "......H]
| be an arbitrary BAMDP value function. We denote by
Th.V the greedy policy with respect to V defined Vx (s,p) X
(1) = arg aEAA
R(x,a) + Tasss' 1s, s,a)p(0)Vn+ (x')
0.6'
where x' = Bs,, a, s')) E X. Recall that Vi+1 denotes the optimal BAMDP value function at timestep h + and मं denote the Bayes-optimal policy. for all h [H]. for all s E S, and any p. E (0)) [V, - Vv((s, 4))l Se, e, then I|V V V.T 1lx S 2= - +
Combining Propositions and immediately yields a corresponding performance-loss bound as desired, paralleling the analogous result for state aggregation in MDPs (see Theorem 4.1 of Van Roy [2006]):
Proposition 3. Let n denote the greedy policy with respect to Vor+1 Then, I|V 48(H h)(H h h+ 1)2.
V 11 S
6 Discussion & Conclusion
In this work, we began by characterizing the complexity of a BAMDP via an upper bound on the total number of interactions needed by agent to exhaust information and fully resolve its

---

epistemic uncertainty over the true environment. Under an assumption on the exact form of the agent's s uncertainty, we showed how this information horizon facilitates more efficient planning when smaller than the original problem horizon. We recognize that Assumption deviates from the traditional parameterization of uncertainty in the MDP transition function via the Dirichlet distribution [Poupart et al., 2006, Kolter and Ng, 2009] (sometimes also known as the flat Dirichlet-Multnnnme model [Asmuth, 2013]). The driving force behind this choice is to avoid dealing in differential entropy when engaging with the (residual) uncertainty contained in any epistemic state. Should one aspire to depart from Assumption I altogether in a rigorous way that manifests within the analysis, we suspect that it may be fruitful to consider lossy compression of each epistemic state into discrete, [ -valuee random variable. Under such a formulation, the appropriate tool from information theory for the analysis would be rate- rate-distortion theory [Cover and Thomas, 2012, Csiszár, 1974]. This would, in a theoretically-sound way, allow for an arbitrary BAMDP parameterization and, for the purposes of continuing the use (discrete) Shannon entropy in the definition of the information horizon, induce a lossy compression of each epistemic state whose approximation error relative to the true epistemic state could be accounted for via the associated rate-distortion function.
or FDM
Recognizing the persistence of the intractable BAMDP hyperstate space, we then proceeded to outline epistemic state abstraction as mechanism that not only induces finite, tractable hyperstate space but also has the potential to incur a reduced information horizon within the abstract problem. Through analysis of approximation error and performance loss, we observe an immediate consequence of Proposition 3: if one wishes to compute an E-optimal BAMDP value function for an original BAMDP of interest, one need only find the TリH 1+ cover of the simplex, (O)), and then apply the corresponding epistemic state abstraction through Algorithm 3, whose planning complexity bears no dependence on the hyperstate space of the original BAMDP and has reduced dependence on the problem horizon. One might observe that the right-hand side of the value-loss bound maximized at timestep h = I, making this first step the limiting factor when determining what value of 5 to employ for computing the epistemic state abstraction. As this cover could become quite large and detract from the efficiency of utilizing epistemic state abstraction in subsequent time periods, future work might benefit from considering abstractions formed by a sequence of exactly H covers, where the indexing of 5% in time h E [H] affords better preservation of value (via a straightforward extension of Proposition 3) across all timesteps simultancously.
One caveat and limitation of our planning algorithms (both exact and approximate) is the provision of the information horizon as an input. An agent designer may seldom have the preseience of knowing the underlying BAMDP information structure or, even with suitable regularity assumptions on the policy class, be able to compute it. An observation that many sampling-based algorithms for approximately solving BAMDPs, like BAMCP [Guez et al., 2012], implicitly hypothesize a small information horizon (typically, a value of 1) through their use of posterior sampling and choice of rollout policy. Meanwhile, recent work has demonstrated strong performance guarantees for reinforcement-leaneee learning agent acting an arbitrary environment (Dong et al., 2022] through the use of an incrementally increasing discount factor [Jiang et al., 2015b, Arumugam et al., 2018], gradually expanding the effective range over which the agent is expected to demonstrate competent behavior. Taking inspiration from this idea, future work might consider designing more-efficient planning algorithms that, while ignorant of the true information horizon, instead hypothesize a sequence of increasing information horizons, eventually building up to the complexity of the full BAMDP. Of course, prior to development of novel algorithms, the notion that existing BAMDP planners may already make implicit use of the information horizon is in and of itself task for future work to tease apart and make mathematically rigorous.
Moreover, similar to how the simulation lemma [Kearns and Singh, 2002] provides principled foundation for model-based reinforcement learning, our analysis might also be seen as offering theoretical underpinnings to the Bayes-optimal exploration strategies learned by meta reinforcement- learning agents [Ortega et al., 2019, Mikulik et al., 2020] whose practical instantiations already rely upon approximate representations of epistemic state [Zintgraf et al., 2019, 2021].
Acknowledgements
The authors gratefully acknowledge the anonymous reviewers for their insightful comments, questions, and discussions.
10

---

References
David Abel. A Theory of Abstraction in Reinforcement Learning. PhD thesis, Brown University, 2020. 7
David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state abstraction. In International Conference on Machine Learning, pages 2915-2923, PMLR, 2016. 2,
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. Toward good abstractions for lifelong learning. In NeurIPS Workshop Hierarchical Reinforcemenl Learning, 2017. 22
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong reinforcement learning. International Conference on Machine Learning, pages 10-19. PMLR, 2018. 7
David Abel, Dilip Arumugam, Kavosh Asadi, Yuu Jinnai, Michael L Littman, and Lawson LS Wong. State abstraction as compression in apprenticeship learning. In Proceedings of the AAAI 2019. 7
Conference on Artificial Intelligence, volume 33, pages
David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman. Value preserving state-action abstractions. In International Conference on Artificial Intelligence and Statistics, pages 1639-1650. PMLR, 2020. 22
David Abel, Cameron Allen, Dilip Arumugam, D. Ellis Hershkowitz, Michael L. Littman, and Lawson L.S. Wong. Bad-policy density: A measure of reinforcement learning hardness. In ICML Workshop on Reinforcement Learning Theory, 2021. 2
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural com- plexity and representation learning of low rank MDPs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20095-20107, 2020.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pages 1184-1194, 2017.
Mauricio Lópe,, Vincent Thomas, and Olivier Buffet. Near-optimal BRL using optimistic local transitions. In Proceedings of the 29th International Conference on Machine Learning, pages 515-522, 2012. 1,4
Dilip Arumugam, David Abel, Kavosh Asadi, Nakul Gopalan, Christopher Grimm, Jun Ki Lee, Lucas Lehnert, and Michael L. Littman. Mitigating planner overfitting in model-based reinforcement learning. arXiv preprint arXiv: /8/2.01 129, 2018.
Dilip Arumugam, Peter Henderson, and Pierre-Luc Bacon. An nnformatton-thhoore perspective on credit assignment in reinforcement learning. arXiv preprint arXiv:2103.0mm
2021. 2
John Asmuth, Lihong Li, Michael L Littman, Ali Nouri, and David Wingate. A Bayesian sampling approach to exploration in reinforcement learning. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 19-26, 2009. 1.4
John Thomas Asmuth. Model-based Bayesian reinforcement learning with generalized priors. Rutgers The State University of New Jersey-New Brunswick, 2013. 10
Peter L Bartlett and Ambuj Tewari. REGAL: regularization based algorithm for reinforcement learning in weakly communicating MDPs. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 42, 2009. 2
Mare G Bellemare, Georg Ostrovski, Arthur Guez, Philip Thomas, and Rémi Munos. Increasing the action gap: New operators for reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016. 2
Richard Bellman. Markovian decision process. Journal of mathematics and mechanics, pages 679-684, 1957. 2, 4.

---

Richard Bellman and Robert Kalaba. On adaptive control processes. IRE Transactions on Automatic Control, 4(2):1-9, 1959. 1,
Dimitri P Bertsekas, David A Castanon, et al. Adaptive aggregation methods for infinite horizon dynamic programming. 1988.
Pablo Samuel Castro and Doina Precup. Using linear programming for Bayesian exploration in Markov decision processes. In IJCAI, volume 24372442, 2007. 1,
Thomas M Cover and Joy Thomas. Elements of information theory. John Wiley & Sons, 2012. 6, 10
Imre Csiszár. On an extremum problem information theory. Studia Scientiarum Mathematicarum Hungarica, 9, 1974. 10
Peter Dayan and Terrence Sejnowski. Exploration bonuses and dual control. Machine Learning, 25 (1):5-22, 1996. 1,
Thomas Dean and Robert Givan, Model minimization in Markov decision processes. In AAAI/IAII, pages 106-111, 1997. 7
Richard Dearden, Nir Friedman, and Stuart Russell. Bayesian Q-laaring. Proceedings of the Fifteenth National/Tenth Conference on Artificial Inteliggence/hnovatiie Applications of Artificial Intelligence, pages 761-768, 1998. 1,
Christos Dimitrakakis. Complexity of stochastic branch and bound methods for belief tree search in Bayesian reinforcement learning. arXiv preprint arXiv:0912.5029, 2009.
Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou. Provably efficient reinforcement learning with aggregated states, arXiv preprint arXiv:1912.06366, 2019. 7
Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou. Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States. Journal of Machine Learning Research, 23(255):1-54, 2022. URL /att:://jmli jttpjirrrrrrrrr..oreeeeeeeeooerl
html. 10
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 Machine Learning, pages 1665-1674, PMLR, 2019.
Richard Dudley, The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis, 1(3):290-330, 1967. 8
Michael O Duff. Monte-Carlo algorithms for the improvement of finite-state stochastic controllers: Application to Bayes-adaptive Markov decision processes. In International Workshop on Artificial
Intelligence and Statistics, pages 93-97. PMLR, 2001. 1,4
Michael O Duff. Design for an optimal probe. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 131-138. 2003a. 1.4
Michael O Duff. Diffusson approximation for Bayesian Markov chains. In Proceedings of the 20th
International Conference Machine Learning (ICML-03), pages 139-146, 2003b. 1,4
Michael O Duff and Andrew G Barto. Local bandit approximation for optimal learning problems. In Advances in Neural Information Processing Systems, pages 1019-1025, 1997.
Michael O'Gordon Duff. Optimal Learning: Computationall procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002. 1,3
Amsi-md Farahmand. Action-gap phenomenon in reinforcement learning. Advances in Neural Information Processing Systems, 24:172-180, 201
Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite Markov decision processes.
In UAI, volume 4, pages 162-169, 2004.
12

---

Norman Ferns, Pablo Samuel Castro, Doina Precup, and Prakash Panangaden. Methods for computing state similarity in Markov decision processes. arXiv preprint arXiv:/206.6880 68366 2012.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian reinforcement learning: A survey. Foundations and Trends@ in Machine Learning, 8(5-6):359 -833 2015. 1, 4
John Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), 41(2):148-164, 1979.
Geoffrey J Gordon. Stable function approximation in dynamic programming. In Machine Learning Proceedings 1995, pages 261-268. Elsevier, 1995.
Arthur Guez, David Silver, and Peter Dayan. Efficient Baycs-adaptive reinforeement learning using sample-based search. In Proceedings of the 25th International Conference on Neural Information Processing Systems-Voit Volume I, pages 1025-1033, 2012. 1, 1,4,1, 10
Arthur Guez, David Silver, and Peter Dayan. Scalable and efficient Bayes-adaptivy reinforcement learning based on monte-carlo tree search. Journal of Artificial Intelligence Research, 48:841-883, 2013. 1,
Arthur Guez, Nicolas Heess, David Silver, and Peter Dayan. Bayes Bayes-adaptive simulation-based search with value function approximation. In Advances in Neural Information Processing Systems, pages 451-459, 2014. 1,
Dorit S Hochbaum. Approximating covering and packing problems: set cover, vertex cover, indepen- dent set, and related problems. In Approximation algorithms for NP-hard problems, pages 94-143, 1996.
David Hsu, Wee Sun Lee, and Nan Rong. What makes some POMDP problems easy to approximate? In Proceedings of the 20th International Conference on Neural Information Processing Systems, pages 689-696, 2007. 2,4
Thomas Jaksch, Ronald Ortnr,, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010. 2
Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforcement learning. In International Conference on Machine Learning, pages 179-188. PMLR, 2015a. 7
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon on model accuracy. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 1181-1189. Citeseer, 2015b. 10
Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert Schapire. Contex- tual decision processes with low Bellman rank are PAC-learnable. In International Conference on Machine Learning, pages 1704-1713. PMLR, 2017. 2
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman Eluder dimension: New rich classes of RL problems, and samplc-efficient algorithms. arXiv preprint arXiv:2102.00815, 2021.
Nicholas K Jong and Peter Stone. State abstraction discovery from irrelevant state variables. In IJCAI, volume 8, pages 752-757. Citeseer, 2005. 7
Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99-134 1998.
Sham Kakade, Michael J Kearns, and John Langford. Exploration in metric state spaces. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pages 306- 312, 2003a. 4
Sham Machandranath Kakade et al. On the sample complexity of reinforcement learning. PhD thesis, 2003b.
Michael Kearns and Satinder Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. Advances in Neural Information Processing Systems, pages 996-1002, 1999. 4
13

---

Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning. 49(2-3):209-2333 2002. 7, 10
Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine learning, 49(2):193-200 2002. 4
Levente Kocsis and Csaba Szepesvári. Bandit based Monte- planning. In European conference on machine learning, pages 282-293. Springer, 2006. 4
J Zico Kolter and Andrew Y Ng. Year-Rayesian exploration in polynomial time. In Proceedings of the 26th annual international conference on machine learning, pages 513-520, 2009. 1, 4, 6, 10
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, pages 1008-1014, 2000. 4
Gilwoo Lee, Brian Hou, Aditya Mandalika, Jeongseok Lee, Sanjiban Choudhury, and Siddhartha Srinivasa. Bayesian policy optimization for model uncertainty. In International Conference on Learning Representations, 2018. 4,
Lihong Li, Thomas Walsh, and Michael Littman. Towards a unified theory state abstraction for MDPs. ISAIM, 4:5, 2006. 2,7
Michael L Littman, Thomas L Dean, and Leslie Pack Kaelbling. On the complexity of solving Markov decision problems. In Proceedings of the Eleventh conference on Uncertainty in Artificial Intelligence, pages 394-402, 1995.
Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, and Zheng Wen. Reinforcement learning, bit by bit. arXiv preprint 2xXiv:2103.04000 2021.
Odalric-Ambrym Maillard, Timothy A Mann, and Shie Mannor. How hard is my MDP?" the distribution-norm to the rescue". Advances Neural Information Processing Systems, 27:1835- 1843, 2014. 2
Vladimir Mikulik, Grégoire Delétang, Tom McGrath, Tim Genewein, Miljan Martic, Shane Legg, and Pedro A Ortega. Meta-trained agents implement Bayes-optimal agents. In NeurIPS, 2020. 10
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning, pages 6961-6971. PMLR, 2020. 7
Pedro A Ortega, Jane X Wang, Mark Rowland, Tim Genewein, Zeb Kurth-Nelson, Razvan Pascanu, Nicolas Heess, Joel Veness, Alex Pritzel, Pablo Sprechmann, et al. Meta-learning of sequential strategies. arXiv preprint drX0v.105.003030. 2019. 10
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Leurning, pages 2701-2710, 2017. 4
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via
bootstrapped DQN. In Advances in neural information processing systems, pages 6026-4034 2016a.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386, 2016b. 4
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62,, 2019.
Brendan O' D'onogguee, Ian Osband, Remi Munos, and Volodymyr Mnih. The uncertainty Bellman equation and exploration. In International Conference on Machine Learning, pages 3836-3845. 2018. 4
Pascal Poupart, Nikos Vlassis, Jesse Hoey, and Kevin Regan. An analytic solution to discrete Bayesian reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pages 697-704, 2006. 1, 3, 4, 10
14

---

Martin L. Puterman. Markov Decision Processes Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, 1994.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving Markov decision processes with generative model. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pages 5192-5202, 2018a. 4
Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving Markov decision processes. In Proceedings of the Twenty-Ning Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770-787. SIAM, 2018b. 4
Satinder P Singh and Richard C Yee. An upper bound on the loss from approximate optimal-value functions. Machine Learning, 16(3):227-233 1994. 9
Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. Reinforcement learning with soft state aggregation. Advances in neural information processing systems, pages 361-368, 1995.
Jonathan Sorg, Satinder Singh, and Richard Lewis. Variance-based rewards for approximate Bayesian reinforcement learning. In Proceedings of the Twenty-Sixih Conference on Uncertainty in Artificial Intelligence, pages 564-571, 2010. 1,
Alexander L Strehl, Lihong Li, and Michael L Littman. Reinforcement learning in finite MDPs: PAC analysis. Journal of Machine Learning Research, 10(Nov):2413-245) 2009. 7
Malcolm Strens. A Bayesian framework for reinforcement learning. In ICML, volume 2000, pages 943-950, 2000.
1,4
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933. PMLR, 2019.
Richard S Sutton and Andrew G Barto. Introduction to reinforcement learning. 1998. 2
Paul Tseng. Solving H-horizon, stationary Markov decision problems in time proportional to log(H).
Operations Research Letters, 9(5)2277-277, 1990. 4
John Tsitsikkis and Benjamin Van Roy. reature-based methods for large scale dynamic program- ming. Machine Learning, 22(1):59-99)) 94, 1996.
Benjamin Van Roy. Performance loss bounds for approximate value iteration with state aggregation. Mathematics of Operations Research, 31(2):234-244, 2006. 2, 7,9
Tao Wang, Daniel Lizotte, Michael Bowling, and Dale Schuurmans. Bayesian sparse sampling for on-line reward optimization. In Proceedings of the 22nd International Conference on Machine Learning, pages 956-963, 2005. 1,4
Ward Whitt. Approximations of dynamic programs, I. Mathematics of Operations Research, 3(3): 231-243, 1978.
Zongzhang Zhang, Michael Littman, and Xiaoping Chen. Covering number as complexity measure for POMDP planning and learning. In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012. 2, 7
Luisa Zintgraf, Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hofmann, and Shimon Whiteson. VariBAD: A very good method for Bayes-adaptive deep RL via meta-learning. In International Conference on Learning Representations, 2019. 1,
Luisa M Zintgraf, Leo Feng, Cong Lu, Maximilian Igl, Kristian Hartikainen, Katja Hofmann, and Shimon Whiteson. Exploration in approximate hyper-state space for meta reinforcement learning. In International Conference on Machine Learning, pages 13901-13001, PMLR, 2021. 10
15

---

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 ethics review guidelines and ensured that your paper conforms to 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 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 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 (c.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]
(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're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe 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 participant compensation? [N/A]
16


Reviews:
[{"review_id": "ieckprUbd0e", "reviewer": "Reviewer_e61u", "summary": "The paper deals with Bayes-adaptive Markov decision processes. The paper presents a complexity measure that quantifies the worst-case difficulty for solving an BAMDPs. The measure, the information horizon, is the longest horizon required for an agent to completely reduce it is uncertainty about either the dynamics or reward of the underlying MDP. This measure can then be used to perform planning in a BAMDP over a reduced horizon, before switching to planning in a fully-known MDP, thus reducing time complexity. \n\nDespite the reduction of time complexity by reducing the planning horizon, time complexity of value iteration in BAMDP is still dominated by the size of the state space. The second contribution of the paper revolves around applying principles of state-abstraction on the hyperstate-space of BAMDPs (state X info-state). This leads to a complexity that depends on the state size of the abstract BAMDP. \n\n", "questions": "N.A.", "limitations": "* The paper discuss the limitations an addresses them. Nonetheless, I wish the authors would find a way to integrate parts of the discussion that appear in the appendix into the main text.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well-written. Assumptions are clearly stated and background work is discussed in detail. The quality of presentation is excellent. There is a clear thread and argument structure to follow. \n\nThe contribution is solid. BAMDPs are computationally very expensive and this paper proposes, what appears to me, as well-grounded improvements. The impact might be somewhat limited due to the fact that it considers only discrete state-action spaces, but anything else would explode the scope.\n\nI am not an expert in the domain of BAMDPs, but the concepts presented in the paper appear novel, despite the fact that they are closely related to a large body of work, that the authors cite.", "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": "UG5Og5Xj4T5", "reviewer": "Reviewer_bYxQ", "summary": " This paper addresses state abstraction in BAMDPs to find approximately Bayes-optimal solutions at reduced computational expense. The paper first introduces the idea of the information horizon: the number of steps at which the true underlying MDP will be identified for any policy. It suggests a simple algorithm to reduce the complexity of solving the BAMDP if the information horizon is less than the BAMDP horizon. This involves finding the optimal Bayes-adaptive policy up until the information horizon, and then executing the optimal policy in the identified MDP thereafter.\n \nFor most realistic examples, we cannot expect the ambiguity over the underlying MDP to be completely removed in a small (or indeed, finite) number of steps. Therefore, we can't necessarily expect the information horizon to be less than the BAMDP horizon. To address this, the paper suggests to use state abstraction over the information states. Depending on the coarsity of the abstraction, more of the original information states will be considered to be \"close enough\" to having resolved the ambiguity over the MDP. Therefore, for more coarse abstractions, we can expect the information horizon to be reduced in the abstract BAMDP. The paper analyses the sub-optimality induced by considering the abstract version of the BAMDP.", "questions": "The informed value iteration idea means that once the information horizon has been reached, we just solve standard MDPs, and only need to find the Bayes-optimal solution up until the information horizon. It seems to me that existing sample-based algorithms already become equivalent to solving standard MDPs after the information horizon is reached.\n \nLets consider BAMCP [37], or indeed any algorithm which makes use of root sampling (sampling a candidate MDP from the initial state to simulate each rollout). Let's also imagine that the information horizon is 1 (i.e. the ambiguity over the MDP is resolved after one step). To make the example very simple, let’s assume the ambiguity is resolved as follows: if, after the first step the agent reaches states in set A, then the MDP is known to be MDP_A, and if the agent reaches states in set B, then the MDP is known to be MDP_B.\n \nThen, all trials that reach set A after the first step are using MDP_A, and all trials that reach set B after the first step are using MDP_B. This means that after the first step, BAMCP reduces to performing standard MCTS in two standard MDPs (i.e. standard MCTS in MDP_A for states in set A and standard MCTS in MDP_B for states in set B).  The point I am trying to make is that if ambiguity over the MDP has been resolved, algorithms which search forward over reachable information states (including RL algorithms) already have the property that they become equivalent to solving individual MDPs after reaching the information horizon.\n \nIf this is true, this limits the impact of the work as I don't think the insight of informed value iteration vs value iteration will translate into improvements into other algorithms (i.e. knowledge of the information horizon can only improve performance for naïve value iteration over the entire BAMDP, but wouldn't improve BAMCP-like algorithms).\n \nSummary of questions to the authors:\n\n* Please address weaknesses 1, 2, 3 above\n* Is it fair to say that sampled-based algorithms such as BAMCP already implicitly make use of the information horizon as discussed above?\n* Can utilising the information horizon more explicitly as proposed in your work make any improvement in the efficiency of existing sample-based (or RL) algorithms, which simulate rollouts in candidate MDPs rather than iterating over the entire belief space?\n", "limitations": "More discussion of limitations due to finite set of MDPs, and applicability of the idea to improve sampled-based/RL algorithms (rather than only improving the most naïve value iteration approach) would improve the paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and easy to follow. I think this idea of considering an appropriate information horizon is both interesting and can potentially be an impactful idea. I think the analysis of state abstraction in BAMDPs can be useful for informing approximate algorithms.\n \nThere are several shortcomings that I think the paper could address better:\n\nWeakness 1. The paper uses value iteration over the entire information state space to analyse the complexity of informed value iteration vs value iteration, and to demonstrate how using the information horizon can reduce the complexity of value iteration. However, most algorithms for BAMDPS do not iterate over the entire state space, but only compute solutions over the reachable information state space. To me, it seems like these existing algorithms already implicitly take advantage of the fact that some problems have a reduced information horizon, by becoming equivalent to solving standard MDPs once the information horizon is reached. I think this reduces the impact of the informed value iteration idea, as it seems that other common algorithms already (implicitly) do something similar, and this performance improvement might only be applicable to naïve value iteration (which wouldn't be used in practice for BAMDPs). I will elaborate on this in the questions section.\n \nI still think that the paper is good overall since explicitly reasoning about the information horizon allows for providing theoretical bounds. However, it would benefit from discussing this if this is the case.\n \nWeakness 2. Both the informed VI, and informed abstract VI algorithms require knowing what the information horizon is for the given (abstract) BAMDP. However, it is unclear how the information horizon would be determined for a given problem, even for an abstract BAMDP with a known \\delta used to compute the state abstraction. It is also not clear when we can expect the information horizon to be decreased when using the state abstraction technique. I would appreciate a greater discussion of this in the paper and in rebuttal.\n \nWeakness 3. Most BAMDP problems (even for finite state and action spaces) assume that the space of possible MDPs is infinite. However, in Assumption 1, this paper assumes that the uncertainty is over a finite set of MDPs. Therefore, to match Assumption 1, additional discretisation may be required over the space of MDPs to make it finite. The paper does not discuss this issue, and would be strengthened if it did also analyse the error introduced by discretising the space of possible MDPs to match Assumption 1. Is it possible to apply the abstraction if the space of possible MDPs is infinite? Please discuss\n \nMinor comments:\n\n* In the preliminaries, \\pi is initially used to indicate a non-stationary deterministic policy. However, when discussing the existence of an optimal policy, \\pi is then used to refer to a stationary deterministic policy. Please make this clearer.\n\n* Presentation of Bellman equations needs further formatting (e.g. they overflow for BAMDPs and the use of commas and full stops looks a bit arbitrary)\n\n* When discussing the information horizon, authors say I<=H but immediately after discussing the case where I=\\infty. Make it more precise.\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": "PPI2Qaj9Vkj", "reviewer": "Reviewer_YjRz", "summary": "This paper considers how to tractably plan in BAMDPs, which are the belief-level MDPs induced by introducing uncertainty over the transition dynamics into a traditional finite-horizon MDP. The paper makes two contributions:\n\n1. The paper coins a notion of \"information horizon\", which is the first timestep at which the agent is guaranteed to be certain about the environment dynamics under a given policy (the information horizon of a BAMDP itself is the maximum of such horizons over all policies). This horizon makes it possible to decompose the complexity of BAMDP planning into a deterministic planning component after the information horizon, and a (much more expensive) belief-space planning component before the information horizon.\n2. The paper also suggests an approximate planning scheme for BAMDPs which projects belief states onto a $\\delta$-cover for the space of all beliefs. This cover is constructed to contain all the standard basis vectors of the space of beliefs, which correspond to distributions in which the agent is certain of the dynamics. Consequently, as $\\delta$ increases, the agent becomes more likely to project its uncertain beliefs onto a deterministic/certain belief. This decreases the effective information horizon. Theoretical analysis provides bounds for the value of a greedy policy under such an approximate belief for a given $\\delta$.", "questions": "- Do the authors foresee a particular \"killer app\" for this technique for which the information horizon is both small and easy to compute? I can imagine some artificial problems for which this is true, but I'm wondering whether there's a general class for which it holds.\n- How does the complexity of computing the information horizon compare to the overall complexity of BAMDP planning? Is there any worst-case win obtained by using Algorithm 2 in situations where $\\mathcal I$ is not known a priori?", "limitations": "I felt the paper was clear in its assumptions and results (such as acknowledging that Assumption 2 will not hold in practice). I do not see obvious negative social impacts specific to this work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Crisp exposition throughout. POMDPs and Bayesian RL are not my area, but I felt that the proposed concepts built naturally on top of one another.\n- Expansive related work (although given that this is not my area, so I cannot say for sure that it is not overlooking work).\n- The value approximation scheme requires fairly weak assumptions on the structure of the MDP, and its utility (relative to precise VI on the BAMDP) is precisely quantified in Section 5.3.\n\nWeaknesses:\n\n- The definition of the information horizon is quite strict. If there is any path taken by a policy $\\pi$ under which the agent might still have uncertainty at a given time step $h$, then the information horizon  for $\\pi$ must be greater than $h$. This is even worse at the level of the BAMDP, where we take a maximum over all $\\pi$, including $\\pi$ that do not gather much information because they do not act strategically. Consequently, I'm not sure how many \"real\" BAMDPs are likely to have a small information horizon.\n- Although Algorithm 2 makes fairly weak assumptions, it still requires computations that are likely very expensive in practice, like computation of $\\mathcal I$ and standard VI repeated over every possible transition function. Both of these are very expensive operations, and I'm not sure how one would easily compute the information horizon or prune the computation of optimal policies with respect to each $\\theta$ in order to make the process more tractable.\n\nAdmittedly these weaknesses (\"the assumptions are too strong/don't scale\") are common to many theory-oriented papers. My accept recommendation below is because I feel this paper has adequately demonstrated that the \"information horizon\" (and abstractions that decrease effective information horizon) is an interesting concept worthy of further fleshing out, even if the practical questions (like how to make Algorithm 2 more efficient) are not solved in this 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": "FS2zCqYuwhs", "reviewer": "Reviewer_Gwj8", "summary": "This paper introduces a novel concept for analyzing the complexity of Bayes-Adaptive MDPs (BAMDPs), which is called the Information Horizon. The authors argue that BAMDPs with low Information Horizon (relative to the episode horizon) -- that is, those BAMDPs in which an agent can potentially deduce the underlying MDP without uncertainty after relatively few environment steps -- can be solved more efficiently since value iteration in the hyperstate space is carried out over a shorter horizon. The authors then demonstrate how the complexity of (approximately) solving BAMDPs can be further reduced via state abstraction, and error bounds are provided for the value functions learned in such abstract BAMDPs.", "questions": "# Questions and Comments\n\n**Section 2.1 -- Definition of the value function**: I believe there is\na typo in the state/action indexing in the sum -- it should be\n$\\mathcal{R}(s_{h'}, a_{h'})$ rather than $\\mathcal{R}(s_h,a_h)$.\n\n**Assumption 1**: Is the assumption that the parameter space $\\Theta$ is\nfinite not much more limiting than existing work? In the setting with a\nDirichlet prior that is mentioned, the agent would be modeling a belief\nover uncountably many MDPs. Moreover, on line 71, it says \\\"we do not\nconcern ourselves with the computation of the posterior\\\" -- but\ndoesn\\'t this neglect much of the issue of intractability in BAMDPs?\nFinally, how fair is it really to assume a constant-time posterior\nupdate? Even with finitely-many MDPs, I would expect that the number of\nknown MDPs ($|\\Theta|$) must somehow grow with the state/action spaces\nin a reasonable model.\n\n**Assumption 2**: I believe this is notationally incorrect. While you\nassume \\\"an agressively-fine quantization\\\" of $\\Delta(\\Theta)$,\n$\\Delta(\\Theta)$ itself is not finite, so $|\\mathcal{X}|\\not < \\infty$.\nThe quantization of $\\Delta(\\Theta)$ should be made explicit, i.e.,\n\\\"let $\\widehat{\\Delta}\\subset\\Delta(\\Theta)$ be finite... let\n$\\mathcal{X}\n= \\mathcal{S}\\times\\widehat{\\Delta}$\\\".\n\n**Value iteration in hyperstate space**: When discussing the complexity\nof value iteration in hyperstate space, the term $|\\mathcal{X}|$ appears\nfrequently. To my understanding, this term hides a lot of complexity. In\nparticular, we\\'re assuming an aggressively-fine quantization of\n$\\Delta(\\Theta)$ as part of the space $\\mathcal{X}$, which leads me to\nbelieve that $|\\mathcal{X}|\\in\n\\mathcal{O}(|\\mathcal{S}|\\exp(|\\Theta| - 1))$. If\n$|\\Theta|\\in\\omega(\\log|\\mathcal{S}|)$, then already any algorithm with\ncomplexity linear in $|\\mathcal{X}|$ is intractable. Conversely, if $|\\Theta|\\in \\mathcal{O}(\\log|\\mathcal{S}|)$, the algorithm may actually be tractable. Thus, I think the\nscaling of $|\\Theta|$ w.r.t. $|\\mathcal{S}|$ should be discussed. Note\nthat if $|\\Theta|\\in\\mathcal{O}(1)$, then as\n$\\mathcal{S}\\uparrow\\infty$, one has less and less uncertainty over the\nMDP. While this does appear to be addressed in line 222, it may be\ninteresting to discuss settings where these algorithms *are* tractable,\nsince already so many \\\"finiteness\\\" assumptions have been made.\n\n**Proposition 1**: Naively, one should expect that\n$\\max_{x\\in\\mathcal{X}}|V_h^\\star(x) -\nV_{\\phi,h}^\\star(\\phi(x))|\\leq H - h + 1$ since the rewards are bounded\nin $[0,1]$. For this proposition to be at all interesting, we must have\n$\\delta(H - h) < 1/2$. Thus, as the horizon increases, the parameter\n$\\delta$ must decrease proportionally for this to be a meaningful\nresult.\n\n**Proposition 3**: Similar to my comment about Proposition 1: for this\nresult to be meaningful, we must have $\\delta<(4(H - h)(H - h +\n1))^{-1}$. Altogether, for this propositions to match the naive\nperformance-loss bound, we need $\\delta\\in O(1/H^2)$. This is addressed\non line 349, but can this be reflected in the complexity bound on line\n312, via the\n$\\mathcal{N}(\\Delta(\\Theta), \\delta, \\|\\cdot\\|_{\\text{TV}})$ term? I\nsuspect that the size of the cover would be very large in this case,\nwhich would add greater dependence on $H$ to the complexity, which the\ngoal was to avoid.\n\n# Minor issues\n\n-   It would be helpful to have hyperlinks. In particular, the long list\n    of citations starting on line 21 is very daunting when the only way\n    to check the citations is by manually scrolling through the\n    references section.\n-   For the long list of citations starting on line 21, it would also be\n    nice if they were listed in numerical order, which make it easier to\n    scan the list without navigating back in forth between line 21 and\n    the references section so many times.\n", "limitations": "As previously mentioned, I believe the theoretical results are quite limited due to the assumptions on the belief space over MDPs. The authors discuss these limitations briefly, although it would have been nice to see more in-depth discussion. ", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\nThe goal of this paper -- to identify a class of BAMDPs that can be solved efficiently -- is a very interesting and ambitious one. For the most part, the authors do a good job of clearly stating assumptions and precisely defining the setting that they're working in. The notion of the information horizon is quite novel to the best of my knowledge, and it seems to be a reasonable and important concept. The proofs of theoretical results are clear and appear to be correct.\n\n# Weaknesses\nI'm mainly concerned with some of the assumptions that are made throughout the paper. In particular, the assumption that the agent maintains a belief over a finite, constant number of MDPs seems excessively limiting. It would have at least been interesting to have a discussion about cases where the number of MDPs in the support of the agent's belief could increase with the size of the state space, even if it must remain finite. Consequently, I'm afraid the results in this paper may have limited relevance.\n\n## Post-Rebuttal Update\n\nThe authors cleared up most of my concerns. I am still skeptical about the relevance of the problem setting, particularly that of a constant-size prior MDP support regardless of the size of the MDP, but I think the information horizon approach is interesting. I have adjusted my score to reflect this.", "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