Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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:

1. 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.
2. 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$.
strengths_and_weaknesses: Strengths:

- 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.
- Expansive related work (although given that this is not my area, so I cannot say for sure that it is not overlooking work).
- 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.

Weaknesses:

- 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.
- 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.

Admittedly 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.
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.
- 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

Despite 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. 


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. 

The 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.

I 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.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
 
For 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.
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.
 
There are several shortcomings that I think the paper could address better:

Weakness 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.
 
I 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.
 
Weakness 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.
 
Weakness 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
 
Minor comments:

* 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.

* 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)

* When discussing the information horizon, authors say I<=H but immediately after discussing the case where I=\infty. Make it more precise.

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.
 
Lets 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.
 
Then, 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.
 
If 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).
 
Summary of questions to the authors:

* Please address weaknesses 1, 2, 3 above
* Is it fair to say that sampled-based algorithms such as BAMCP already implicitly make use of the information horizon as discussed above?
* 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?

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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: # Strengths
The 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.

# Weaknesses
I'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.

## Post-Rebuttal Update

The 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.
questions: # Questions and Comments

**Section 2.1 -- Definition of the value function**: I believe there is
a typo in the state/action indexing in the sum -- it should be
$\mathcal{R}(s_{h'}, a_{h'})$ rather than $\mathcal{R}(s_h,a_h)$.

**Assumption 1**: Is the assumption that the parameter space $\Theta$ is
finite not much more limiting than existing work? In the setting with a
Dirichlet prior that is mentioned, the agent would be modeling a belief
over uncountably many MDPs. Moreover, on line 71, it says \"we do not
concern ourselves with the computation of the posterior\" -- but
doesn\'t this neglect much of the issue of intractability in BAMDPs?
Finally, how fair is it really to assume a constant-time posterior
update? Even with finitely-many MDPs, I would expect that the number of
known MDPs ($|\Theta|$) must somehow grow with the state/action spaces
in a reasonable model.

**Assumption 2**: I believe this is notationally incorrect. While you
assume \"an agressively-fine quantization\" of $\Delta(\Theta)$,
$\Delta(\Theta)$ itself is not finite, so $|\mathcal{X}|\not < \infty$.
The quantization of $\Delta(\Theta)$ should be made explicit, i.e.,
\"let $\widehat{\Delta}\subset\Delta(\Theta)$ be finite... let
$\mathcal{X}
= \mathcal{S}\times\widehat{\Delta}$\".

**Value iteration in hyperstate space**: When discussing the complexity
of value iteration in hyperstate space, the term $|\mathcal{X}|$ appears
frequently. To my understanding, this term hides a lot of complexity. In
particular, we\'re assuming an aggressively-fine quantization of
$\Delta(\Theta)$ as part of the space $\mathcal{X}$, which leads me to
believe that $|\mathcal{X}|\in
\mathcal{O}(|\mathcal{S}|\exp(|\Theta| - 1))$. If
$|\Theta|\in\omega(\log|\mathcal{S}|)$, then already any algorithm with
complexity 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
scaling of $|\Theta|$ w.r.t. $|\mathcal{S}|$ should be discussed. Note
that if $|\Theta|\in\mathcal{O}(1)$, then as
$\mathcal{S}\uparrow\infty$, one has less and less uncertainty over the
MDP. While this does appear to be addressed in line 222, it may be
interesting to discuss settings where these algorithms *are* tractable,
since already so many \"finiteness\" assumptions have been made.

**Proposition 1**: Naively, one should expect that
$\max_{x\in\mathcal{X}}|V_h^\star(x) -
V_{\phi,h}^\star(\phi(x))|\leq H - h + 1$ since the rewards are bounded
in $[0,1]$. For this proposition to be at all interesting, we must have
$\delta(H - h) < 1/2$. Thus, as the horizon increases, the parameter
$\delta$ must decrease proportionally for this to be a meaningful
result.

**Proposition 3**: Similar to my comment about Proposition 1: for this
result to be meaningful, we must have $\delta<(4(H - h)(H - h +
1))^{-1}$. Altogether, for this propositions to match the naive
performance-loss bound, we need $\delta\in O(1/H^2)$. This is addressed
on line 349, but can this be reflected in the complexity bound on line
312, via the
$\mathcal{N}(\Delta(\Theta), \delta, \|\cdot\|_{\text{TV}})$ term? I
suspect that the size of the cover would be very large in this case,
which would add greater dependence on $H$ to the complexity, which the
goal was to avoid.

# Minor issues

-   It would be helpful to have hyperlinks. In particular, the long list
    of citations starting on line 21 is very daunting when the only way
    to check the citations is by manually scrolling through the
    references section.
-   For the long list of citations starting on line 21, it would also be
    nice if they were listed in numerical order, which make it easier to
    scan the list without navigating back in forth between line 21 and
    the references section so many times.

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.
review_title: null

Meta-review: metareview: In post-rebuttal discussion, reviewers debated the merits of the paper and especially reviewer Gwj8's concerns.  In the end, reviewer Gwj8 agreed with other reviewers that the paper should be accepted, although all reviewers would like to see the final revision reflect the points and concerns raised in the post-rebuttal discussion.

confidence: Certain
Decision: Accept