Abstraction for Bayesian Reinforcement Learning in Factored POMDPs
Authors: Rolf A. N. Starre
Sammie Katt
Mustafa Mert Çelikok
Marco Loog
Frans A Oliehoek
Venue: Accepted by TMLR ()

Abstract: Bayesian reinforcement learning provides an elegant solution to addressing the exploration-exploitation trade-off in Partially Observable Markov Decision Processes (POMDPs) when the environment’s dynamics and reward function are initially unknown. By maintaining a belief over these unknown components and the state, the agent can effectively learn the environment’s dynamics and optimize their policy. However, scaling Bayesian reinforcement learning methods to large problems remains to be a significant challenge. While prior
work has leveraged factored models and online sample-based planning to address this issue, these approaches often retain unnecessarily complex models and factors within the belief space that have minimal impact on the optimal policy. While this complexity might be necessary for accurate model learning, in reinforcement learning, the primary objective is not to recover the ground truth model but to optimize the policy for maximizing the expected sum of rewards. Abstraction offers a way to reduce model complexity by removing factors that are less relevant to achieving high rewards. In this work, we propose and analyze the integration of abstraction with online planning in factored POMDPs. Our empirical results demonstrate two key benefits. First, abstraction reduces model size, enabling faster simulations and thus more planning simulations within a fixed runtime. Second, abstraction enhances performance even with a fixed number of simulations due to greater statistical strength. These results underscore the potential of abstraction to improve both the scalability and effectiveness of Bayesian reinforcement learning in factored POMDPs.

Published in Transactions on Machine Learning Research (06/2025)
Abstraction for Bayesian Reinforcement Learning in Fac- tored POMDPs
Rolf A. N. Starre
r.a.nstarreSSuddelf..tt
Delft University of Technology
Sammie Katt
summii.kkttt@uallt.
Aalto Universiby
Mustafa Mert Çelikok Delft University of Technology
m.m.ccelkook@tuudeef.
Marco Loog Radbout University
marco. marco.loog @ro..ru.dd
Frans A. Oliehoek
f.o olwehookk
Delft University of Technology
Reviewed on OpenReview: https: openreview. net/ pet/foree forum? id- Hilgd66m9L9
Abstract
Bayesian reinforcement learning provides elegant solution to addressing the explo- ration-exploitaioon trade-off in Partially Observable Markov Decision Processes (POMDPs) when the environment's dynamics and reward function are initially unknown. By maintain- ing a belief over these unknown components and the state, the agent can effectively learn the environment's dynamics and optimize their policy. However, scaling Bayesian reinforce- ment learning methods to large problems remains be a significant challenge. While prior work has leveraged factored models and online sample-based planning to address this issue, these approaches often retain unnecessarily complex models and factors within the belief space that have minimal impact on the optimal policy. While this complexity might be nec- essary for accurate model lcarning, in reinforcement learning, the primary objective is not to recover the ground truth model but to optimize the policy for maximizing the expected sum of rewards. Abstraction offers way to reduce model complexity by removing factors that are less relevant achieving high rewards. In this work, we propose and analyzo the integration of abstraction with online planning in factored POMDPs. Our empirical results demonstrate two key benefits. First. abstraction reduces model size, enabling faster sim- ulations and thus more planning simulations within fixed runtime. Second, abstraction enhances performance even with fixed number of simulations due to greater statistical strength. These results underscore the potential of abstraction to improve both the scala- bility and effectiveness of Bayesian reinforcement learning in factored POMDPs.
1 Introduction
Deep reinforcement learning methods have achieved significant milestones, such as attaining superhuman performance on Atari games with only 100k frames (Ye et al., 2021), solving highly complex games such as Go (Silver et al., 2016), and achieving high performance in simulated control tasks (Haarnoja et al., 2018). Most of these achievements rely on recent function approximation advances made with the work on deep neural networks. However, despite these advances, Reinforcement Learning (RL) still faces critical hurdles that must be addressed to enable its application in diverse real-world scenarios. One of the most pressing

---

Published in Transactions on Machine Learning Research (06/2025)
challenges is the high sample complexity of deep RL methods, which remains problematic in real-world applications where data collection is expensive, difficult, or dangerous. Fortunately, many such applications offer prior knowledge that can be leveraged to reduce sample complexity. To effectively utilize this knowledge, it is crucial to move away from the tabula rasa approaches of neural networks and incorporate domain-specific prior knowledge into the learning process (Jonschkowski & Brock, 2015; De Bruin et al., 2018; Katt et al., 2022).
Another critical challenge is exploration, which is strongly tied to sample complexity. Effective exploration of unknown and interesting parts of the environment is essential in almost every application. A better exploration strategy means faster learning and improved sample efficiency. Importantly, in RI, an agent must balance exploration (i.e., learning) with exploitation (iee, maximizing reward). Most deep RL methods rely on heuristics for exploration, which can perform poorly in complex domains (Osband et al., 2016). These challenges are particularly pronounced in partially observable environments, where agents must make decisions based on limited information.
Model-based Bayesian RL (BRL) (Ross et al., 2011) offers principled approach to addressing the exploration-exploitttio trade-off by maintaining a belief over the environment's 's state and dynamics. This belief enables the agent to balance the
trade-off effectively. In this work, we build on the Factored MayyesAdaptive POMDP (FBA-POMDP) framework (Katt et al., 2017; 2019), a model-based BRL approach that combines partial observability and structured factored models. FBA-POMDPs incorpo- rate factorized representations of the environment's dynamics, allowing agents to exploit problem structure for improved scalability. Additionally, thanks to its Bayesian nature, prior knowledge can be incorporated into FBA-POMDPs in principled way via Bayesian priors, further improving sample efficiency.
Despite its advantages, the FBA-POMDP framework faces siguificant challenges. While factorization en- ables better generalization, the inclusion of irrelevant state factors in the model can lead to unnecessarily large model spaces. This increases computational demands during planning and reduces statistical strength by hypothesizing dependencies that are irrelevant to maximizing rewards. For instance, in a cluttered envi- ronment, an agent may only need to consider the positions of objects to navigate effectively, while features such as their colors or shapes are irrelevant for the reward. Abstracting away such unnecessary details can simplify the model space, improve computational efficiency, and enhance learning performance. Previous studies have demonstrated that even lossy abstractions can improve performance in planning (He et al., 2020; Chitnis et al., 2021). This is because simplified models can generate more simulations within a fixed runtime, potentially leading to better results in sampling- online planning. Motivated by this insight, we propose incorporating abstraction into the FBA-POMDP framework to improve scalability and learning efficiency.
We focus on discrete Factored POMDPs (F-POMDPs) and explore the application of abstraction within the FBA-POMDPs framework to enhance planning efficiency, scalability, and learning performance. To achieve this, we augment. Factored Bayes-Adaptive Partially Observable Monte-Carlo Planning (FBA- POMCP) (Katt et al., 2017; 2019), an established online planning and learning algorithm for FBA-POMDPs. to incorporate multiple levels of abstraction. This contribution addresses abstraction discovery in the par- tially observable reinforcement learning setting, where the lack of access to the true model and the complexity of dcaling with partial obscrvability make the creation and utilization of abstractions both important and challenging.
We base ourselves on previous abstraction method for planning in fully observable factored Markov decision processs (MDPs) (Dearden & Boutilier, 1997). It creates abstractions automatically based on the problem's 's structure, enabling agents to plan and learn more effectively. Our approach extends this idea to a partially observable learning setting, where the underlying dynamics are not known beforehand, introducing additional complexities. In this setting, the combination of an unknown model, partial observability, and inherent inexactness of approximate abstractions makes it difficult to evaluate abstractions in advance, making the ability to dynamically update abstract models during learning crucial. To address this challenge, we propose to automatically construct abstractions based on the hypothesized connectivity of state factors to the reward function and leverage the Bayes-adaptive framework to adapt the abstract model over time. A key feature
2

---

Published in Transactions on Machine Learning Research (06/2025)
of our approach is its ability to maintain belief over multiple candidate structures and their corresponding abstract models, ensuring consistent belief updates of the (abstract) models.
Our work represents a novel step toward combining abstraction with BRL in F-POMDPs. Empirically, we demonstrate that abstraction improves performance in two critical ways: (1) by reducing model size, allowing for more simulations within given computation time, and (2) by simplifying the learning problem, leading to faster learning and improved performance in fewer episodes. These findings highlight the potential of abstraction to address key challenges in BRL for F-POMDPs and open a promising direction for future research into leveraging abstractions to improve scalability, exploration, and decision- decision-making in complex, real-world environments.
2 Background
In this section, we introduce the rich body of literalure that our work builds upon. In particular, section 2.1 introduces the POMDP as the general mathematical model for sequential decision-making. We then describe (model-based) Bayesian reinforcement learning in factored POMDPs in section 2.2, which is (belief-space) Partially-observable Markov decision process itself. Lastly, we discuss algorithmic approaches for solving these decision problems in section 2.3.
2.1 POMDPs and Factorization
Sequential docision-making in stochastic domains with hidden states can be formalized as a POMDP (Boutilier & Poole, 1996; Kaelbling el al., 1998). The POMDP is defined by the tuple (S, A, 0, D, 7,, H), where S, A, and O are the (discrete) set of states, actions, and observations, respec- tively. The dynamics DD specify the system's 's transition probabilities D E D: (S A) + A(S x 0), and R: (S A x 8) R is the reward function. The (maximum) number of time steps in an episode is the horizon H E Z, and y E [0, 1] is the discount factor.
The goal of the agent is to maximize the discounted return, T.r. To do so, it can use the observable action (a E A) and observation (o E 0) history h, = (av. 01...., ot),, or it can use the belief as a sufficient statistic. The belief the probability distribution over the current state b E B: AS, which can be updated with Bayes' rule: b((s') 7(b, a, 05') x E. D(s', a)b(s). However, in most problems, the computation of the belief update is intractable. Section 2.3 will cover how to find solution.
Running Example As a simple intuitive example, consider the Corridor domain shown in fig. la. The agent starts at the "Start" location and its goal is to reach the "Reward" location. As depicted in the figure, there is also a "Boots" location and a "Button" location. To reach the reward the "Door" must be open. There is also always a "Person" present in the environment. There are 8 different persons, with exactly one present during each episode. The probability of the person opening the door at some point during an episode varies depending on which person is present, but this probability is generally very low, ranging from about 1.25% to 10%. The agent cannot interact with the person.
The state consists of the location of the agent, the person present and the binary statuses of the boots, button, and door. The agent has four actions: move left or right, put on boots, push button, and lock pick the door. Moving left or right succeeds 30% of the time without boots and 95% of the time with boots. The probability of success for both pul on boots and push bullon is 90%, provided the agent is in the correct location. When the button is pressed, there is a 100% chance that the door opens. The lock pick action only has an effect when the agent is standing next to the door and has a 40% chance of success. The agent can also open the door by "bashing" into it, specifically by using the move right action to collide with the door. This method not very effective and has only a 5% chance of opening the door. The state is not fully observable to the agent; instead, it receives noisy observation, which will be explained later.
The dynamics of POMDPs can often be captured efficiently through factorization and graphical models, such as Dynamic Bayes networks (DBNs) (Boutilier et al., 1999; Murphy, 2002). Through- out this work, the graphical model we rely is specifically a two-stage DBN (Boutilier et al., 1999). Such
Factorization
3

---

Published in Transactions on Machine Learning Research (06/2025)
Start
Boots
Button
Goal
(0)
(4)
(a)
DBN of the true Corridor environment
Abstracted models and constructed from the true Corridor DBN.
kz
Kg
X
X
X
Boots
Boots
Boots
Books
Boots
Boots
Reward
Button
Button
Button
Button
Door
Doar
Door
Door
Dioor
Door
Neward
Person
Person
Porson
Porson
Reward
Reward
(b)
(c)
DBN of particle representing the belief
Abstracted models (lg, k2 and ku) used for planning, constructed from the particle DEN.
X
X
Boots
Boots
Boots
Reward
Button
Dulton
Reward
Rewaard
Door
Door
Person
Person
Revard
(d)
(e)
Figure 1: a) The Corridor domain. b) ground truth graph representing the dynamics of the Corridor domain for the action right. All the factors are partially observable, the agent gets an independent but noisy observation of each state factor. c) The abstract models for different levels of abstraction (denoted by ko, k22, constructed from the true Corridor DBN for the action right. d) We use particle filters to represent the belief, each particle contains DBN of the corridor, this is an example of such DBN, and e) the abstract models constructed from this example DBN.
models represent random variables by their features (also referred to as factors) and provide the ability to capture independence between these features. We assume that the full set of state factors and their (discrete) set of possible values is known.
A Bayes network (BN) is defined by a topology and conditional probability tables (CPTs). The topology G E G describes the structure of the nodes in the graph, whether there is a dependency between pairs of nodes, where G is the sot of all possible edge configurations. These directed edges define the porents Pa(a4; G) of each node xif as the of incoming nodes (where we typically drop the dependency topology G in the notation). The CPTs 0 E θ govern the conditional probability distribution of node 2 given the full set of nodes x p(={l=)= = p(a)]Pa(<';; O)) In discrete environments, for example, these typically are categorical distributions; one for each parent value combination for each node. The Dynamic BN (DBN) restricts the space of graph topologies by allowing only directed edges from variables at one time
the
Here, denotes the full of nodes, and Pa(x;; G) a the subset that directly influences x
4

---

Published in Transactions on Machine Learning Research (06/2025)
step to variables at the next. This is convenient for (Markovian) dynamic systems, where random variables change over time. The Factored POMDP (F-POMDP) factorizes the state and observation space into nodes and describes the dynamics with DBN for each action (Boutilier & Poole, 1996) (e.g., see fig, as a DBN of the running example). In this work, we propose to learn abstract models that remove factors from the graph based on the reward node's dependency on them.
Bayesian inference over DBNs When the parameters of a model are not given, the Bayesian approach is to assume a prior (to compute posteriors) instead. The DBN is defined by - and thus a prior must describe probability distribution over its topology and CPTs. The prior over the topology assigns (prior) probability to each graph structure: the probability that next state and observation factor depends current state factor. The CPTs are categorical distributions and, hence, the Dirichlet distribution is a natural prior (Frigyik et al., 2010). Dirichlet distributions are parameterized by a collection of conditional count tables (CCCT), with one conditional count table (CCT) X E X for cach unique set of parent values for each node.
Given initial counts specified by a prior and data from a categorical distribution, the posterior is again a Dirichlet (with new counts CCCT). In particular, given topology G, prior CCCT and new data point (x,,x), the Bayesian posterior is computed by incrementing the count [ of each node xf that is associated with its parent's 's values x=(aa<')]. This incrementing operation on POMDP transitions will be used frequently and we denote updating counts X E X given a transition (s, (s,,,,',)) 8) with U: (XxSxAx8x0)
X. Note that there is no closed-form form solution to the posterior over topologies.
2.2 Factored BA-POMDPs
If the state transitions were not hidden, one could simply maintain a set of the counts CCTs associated with each transition and over time converge to the true dynamics. This is the case under full observability (MDPs), and is called the Bayes-Adaptive MDP (BA-MDP) (Duff, 2002). Unfortunately, this is not the case in partially observable environments", and hence, there is uncertainty over these counts X-
The Factored Adaptive POMDP (FBA-POMDP) (Katt et al., 2019) captures this uncertainty by using the POMDP formalism. In particular, this Bayes- model is a POMDP whose state space consists of both the state and the dynamics of the original POMDP (Ross et al., 2011). Formally, the FBA-POMDP is tuple ($, A, 0, D, R. 7: H), where $ is the augmented state space: $ S x G x X. L.c., cach fhyper-)state & E S contains a domain state 8, lopology G, and a CCCT X: 8 == (s, x) The action and observation spaces, the horizon, and the discount factor are taken directly from the original POMDP. Similarly, the reward function relies on the underlying system: R($, 8') R(s, a, s'). Note that, while this function is typically assumed known in BRL, we also conduct experiments in which this too uncertain. Lastly, the dynamics D dictate how augmented states transition:
D p(s', o, G² xls,,,
(1)
=pss', ols, (Xl,CCC
(2)
where p(s', ols, a; G, x) can be written as:
p(s', ols, G. = p('')) x)
(3)
In equation 2 the term p(s', a; G. x) shows that the model xG in state é determines the probabilities of the next state s' and observation o. The 1.(.) is the indicator function, and encodes that there is only one non-zero transition, namely where the next topology equals the previous G' and the next counts are increments of the previous according to U. Since the POMDP is fully specified, the original learning problem is cast to planning problem with known dynamics, given prior pD. Most importantly, the exact solution
"In MDP we see the whole transition (s.a.a"), we update the count a(s,a, In contrast, both and a' are hidden in the partially observable case. So we have to update a(), based our belief resulting from the action-oberrvation history rather than the real transitions.
IIn Section we extend these hyperstates incorporate an abstract model, comprising abstract topology G and corresponding abstract counts X-
5

---

Published in Transactions on Machine Learning Research (06/2025)
to this planning problem yields the optimal policy, in terms of exploration-exxloitattoo, with respect to the prior (Ross et al., 2011). Now we can apply our standard POMDP planning tools (e-g,, particle filtering, planning) to FBA-POMDPs, as anytime solvers provide good approximations which converge to the exact solution in the limit of infinite compute (Silver & Veness, 2010; Katt ct al., 2017; 2019).
2.3 Solving FBA-POMDPs
Unfortunately, FBA-POMDPs are very large, and naive applications of planning techniques will fail. Specifi- cally, methods that require exact belief updates cannot be directly applied, as these updates are only feasible with a finite POMDP representation, which is impractical for large problems. This limitation makes it diffi- cult to apply traditional POMDP planning methods without significant modifications. We give high-level description of how solutions for F'BA-POMDPss can be found, and refer to the original work (Katt et al., 2017: 2019) for details. Just like in any other POMDP, a planning solution requires two components: belief tracking and action selection. 4
Belief tracking in the FBA-POMDP The belief, the posterior over the current state, is a probability distribution over the POMDP state and its distribution b E A x D) given the observed history h, = "o,,0,,,.,,,1....... or). Unfortunately, the computation of the belief update is intractable in most problems. Thus, the belief is often approximated with particles instead (Thrun, 1999). A particle filter represents a distribution through particles, which in this case represent FBA-POMDP states, specifically each particle is a weighted FBA-POMDP state (w, 8, G, with (unnormalized) weight E RR. There are numerous sampling mechanisms for updating the belief given a new action-observattin pair (Thrun, 1999), but in this work we applied sequential importance sampling and re-invigorate the belief with a Metropolis- Metropolis-Hastingss within-Gibbs sampling procodure (Katt et al., 2019) when necessary (details in appendix A). The initial particles are sampled from a prior belief, which may encode varying degrees of domain knowledge. Across experiments, we consider different settings in which parts of the DBN structure or certain CPTs are assumed to be known, while others are learned from data. Details the prior knowledge used in the experiments can be found in section 4 and appendix D.
Action selection in the FBA-POMDP Even with approximated belief updates, the belief space can be very large, especially in high-dimensional problems. Thus is often infeasible to compute the action that maximizes the discounted return for every possible belief the agent could end up in. As result, we extend the planner for FBA-POMDP (Katt et al., 2019) to pick actions online instead. Like any Monte-Carlo tree search (MCTS) method, this method incrementally builds a look-ahead tree of simulated interactions in the (FBA-POMDP) environment. Each iterations samples a (hyper) state (s, (x) ~ b and simulates an interaction in the FBA-POMDP, where actions are picked according to Upper Confidence Bounds Applied to Trees (UCT) (Koesis & Szepesvári, 2006) to trade-off exploration and exploitation. For more details, see (Browne et al., 2012) for survey on MCTS, (Silver & Veness, 2010) for MCTS in POMDPs, and (Katt et al., 2017; 2019) for MCTS in Bayes-Adaptive POMDPs (BA-POMDPs).
2.4 State abstraction for (factored) MDPs
State abstraction can be used to simplify complex problems by mapping the original state space to a smaller abstract state space (Ti et al., 2006). This mapping is defined by an abstraction function o, which maps each state 8 to an abstract state s, where the bar notation indicates the abstract state space. Related to our abstraction approach is the notion of model-similarity abstraction. This comes in both an exact form, modellirrelevance abstraction (Li et al., 2006), and an approximate form, approximate model-similarity abstraction (Abel et al., 2016). These abstractions are also known as (approximate) stochastic bisimula- tion (Dean et al., 1997; Givan et al., 2003).
In the exact case, states are grouped if and only if they yield identical rewards and transition functions in the abstract space under all actions. Formally, in a model-irreevaance abstraction, d(s1) = ((82) if and only
"The original POMCP (Silver & Veness, 2010) implementation combined these steps to some extent, but we separate them out.
6

---

Published in Transactions on Machine Learning Research (06/2025)
if
YEEA R(s1, a) = R(82, 0),
(4)
and VEES T( 81, a) = (5' (88118,,0)
(5)
where the transition probability to an abstract state 8' is given by T(3 == EvEr T(s'ss,a). In the approximale case, these equalities are relaxed, requiring that the reward functions and transition probabilities to any abstract state s' differ by no more than a small parameter 7). Exact abstractions preserve optimality, that is, solution in the abstract MDP is an optimal solution in the original MDP. Approximate abstractions do not preserve oplimality, but have a bounded loss in value based on the value of v (Abel et al., 2016).
In Factored MDPs (F-MDPs), Dearden & Boutilier (1997) suggest leveraging the structure of the problem to remove factors which are less relevant or irrelevant. An abstract MDP can be constructed from the remaining lactors. Such an abstraction can be viewed implicitly as a mapping function d, where each configuration of the retained factors defines an abstract state, and all corresponding combinations of the removed factors are mapped to this same abstract state.
3 Abstraction for FBA-POMCPS
FBA-POMCP is able to learn and exploit the structure in POMDPs in Bayesian way. However, it struggles when the number of factors grows large. On the one hand, the presence of many state factors itself slows down sampling, potentially leading to insufficient simulations to derive adequate actions. On the other hand, the prior belief over models with many state factors typically have low probability for models in which all factors have a small number of parents. As consequence, the particle filter typically contains models that have at least few factors with many parents. This leads to slow learning (low statistical strength) and possibly to exploration of factors with little or no effect the rewards. These issues are problematic because our primary focus is on the task performance, rather than on learning the correct model itself.
A natural idea, therefore, is to explore in how far abstrontion can address these two issues. While abstractions could load to inaccurate modols, in the regular (non-Baycs adaptive) planning case, it has been demonstratod that abstracting away factors with weak influence can still improve the performance of online planning (He et al., 2020). Further, without abstraction, the agent could waste time exploring the dynamics of factors with little impact the performance, if they are falsely believed to be influential. By removing these factors, abstraction can reduce unnecessary exploration and focus on the factors relevant for performance. As such, we propose to explore the impact that abstraction of state factors can have when learning in partially observable settings, formalized as FBA-POMDPs.
Specifically, we propose to perform the Partially Observable Monte-Carlo Planning (POMCP) simulations with an abstracted FBA-POMDP model. We hypothesize that such abstraction can improve performance by 1) increasing the number of simulations that can be done thus improving performance in online planning, and 2) reducing unnecessary exploration of factors with little impact on the performance, and allowing to focus exploration on the relevant. factors.
We cover the combination of abstraction with FBA-POMMP in four parts. First, we give a high-level overview of the abstraction method and how it is added to FBA-POMCP. Second, we define abstractions on different levels, denoted by ko, kj...., where ko represents the coarsest abstraction. We define these through subsets of state factors and show how to generate a subset of state factors from a graph structure for a particular level of abstraction. Third, we show how to use the subset of state factors to construct the abstract structure and counts. Finally, we provide theoretical support for the combination of FBA-POMCP with abstraction.
3.1 Adding Abstraction to FBA-POMCP
We propose method to enable the FBA-POMDP framework to benefit from abstraction. Specifically, we use abstract models for online planning with variant of FBA-POMCP, To operationalize this, we cover the following steps:
1. We expand the representations to include abstract states.
7

---

Published in Transactions on Machine Learning Research (06/2025)
Algorithm Initialize Abstract Particle Filter
Algorithm 2 Abstract
1: Input: Pag prior over initial state
1: Input: k: abstraction level
n: number of desired particles
= G. x): hyper-state
k: abstraction level
2: Q + GetSubset
for O...., do
3: G+G G
(8%, G4 Xi) Pso
x
(5t, G Xi)
Abstract(k, (st, Gi xi))
5: for (q,a) E Q Ao
Wi 4
6: C, + y.MarginalireCountSGG X, Q,
6: end for
7: end for
7: return
{3,, G., Xi, wi)==
8: for x E G Q do
9: Gremove(r))
// Remove factor
10: X.remove(r)
// Remove factor
end for return (8,
2. While we do not exploit abstraction in the belief update, the abstracted belief state still needs to be updated. We cover the necessary modifications to the belief update process.
Finally, we explain how FBA-POMCP can use abstracted states.
Expanding the Belief Representation When initializing the weighted particle filter in FBA-POMCP, each particle is hyper-state á = (s, G,) associated with a weight w. The hyper-state & contains ground state 8, a graph utructure G, and a set of counts X. For the initialization we require probability distribution over the possible starting states, over the possible structures, and a probability distribution over the counts given a structure. For the running example, fig. 1d shows a possible structure of hyper-state, this case the factor Door is not believed to influence the factor, and the factor Bulton is not believed to influence the Door factor. When combining FBA-POMCP with abstraction, we abstract G and X and add the resulting abstracted structure G and counts X to each hyper-state 3. This leads to abstract hyper-state: ş == (8. G, X). The particle filter thus stores both the original hyper-state á and the abstracted structure G and counts X. The construction of the abstract hyper-states is done during the initialization of the particle filter, as shown in algorithm 1.
For our running example, fig. 1e illustrates the structure for different levels of abstraction, corresponding to the original structure G in fig. 1d. In algorithm 1, the function Abstract creates the abstract model from a hyper-state 8, detailed in algorithm 2. In the following sections claborate on the methods for selecting subset based on the level of abstraction & and on creating the abstract Ō and
The Belief Update Process To ensure consistency of the belief, we use the full model (G and x) during the belief update (Russell & Norvig, 2016; Katt et al., 2019), as described in sections 2.2 and 2.3. This means that the belief update process remains largely the same. The main difference is that we now track and update both the full and abstract models, as shown in algorithm 3. As in section 2.2, the graph structures of both the full and abstract models stay the same during the update. The counts X are updated via U. Since each state maps to exactly one abstract state, the abstract counts X can be updated through the update of the counts X. Essentially, the (abstract) graphs remain unchanged, while the (abstract) counts are updated.
Using Abstracted States in FBA-POMCP The planning process exclusively abstract models. Specifically, in Algorithm 8, the abstract representation is used to perform the environment Step function, which is utilized during simulations and roll-outs in the look-ahead tree search. The Step function uses the hyper-state with the abstract model and an action to sample next abstract state by iteratively sampling the factors. is shown in Appendix B.
The benefit of using an abstract model is that it speeds up planning since it contains fewer state factors, allowing for fasting sampling of the next state. When there limited time for planning, this is one way in
8

---

Published in Transactions on Machine Learning Research (06/2025)
Algorithm 3 SIS with Abstraction
Algorithm 4 GetSubsetK
Input: {&, G, X, w = current (weighted) filter
1: Input: k: abstraction level
a, o: action and observation
G: Graph structure.
for i O2 do
2: Q f GetMinimumSet() // ko. the IR factors
3:
s ~ p(-1s;; Xi)
3: if k == 0 then
4:
w + x a;
return Q
5: end if
5:
X, -
6: X +
6: Q
end for
7: for == - L++ do
// Normalize & re-sample
8: for (q.a) E + do
return {8%, Gi X4, Gi X-
9: Q' U.QU..gegeooeeeee a) parents()
10: end for
11: Q-Q'
end for
13: return Q
which abstraction can improve performance. It. is important to note that the abstract models are constructed at the beginning the agent's lifetime, when its belief is initialized. As a result, these abstract models are always available.
3.2 Abstraction Via Subsets of State Factors
We introduce a method for performing abstraction the Bayesian RL (BRL) context. Since we are interested in understanding how abstraction impacts the learning process, we base our approach on a relatively simple planning method for F-MDPs (Dearden & Boutilier, 1997), which is easy to understand and analyze. We make three important adaptations: 1) we make it applicable to partially observable problems, 2) we extend it to the RL setting, where the abstraction is not only used for planning but also for learning, and 3) we incorporate the counts required in BRL. Our approach introduces a level of abstraction that determines the factors to include based on the graph structure.
We define different levels of abstraction based on their conncction to the reward the graph structure. Each abstraction level is defined by set of stale factors that is included in the model, observation factors are always kept in the model. After abstraction, this can lead to observation factors without parents, we explain how we deal with this in section 3.3.4. We start building abstractions from the factors directly influencing the reward, the immediately relevant factors (IR). We first give a formal definition and then illustrate it with an example.
Definition 1. The set of immediately relevant factors (IR) contains only the factors E G that directly influence the reward. Specifically, these are the factors that are parents of the reward, denoted as Pa(reward) The smallest subset of state factors kn equal IR, Ko = IR. The set k; the smallest set such that the following holds:
1. ki-1 S kig
2. 1ʃ q k then Pa(g) E kg.
The set keng refers to the full model.
In the running example, we see an example a structure in fig. 1d. In this problem, the agent only receives a reward when it is the goal location, i.c., x 4. This reflected in the graph structure where the only parent factor of the reward is z. In this case, x is the only IR factor and the abstraction ko only contains æ shown in fig. le. To construct the subset of state factors for kn, we add the parents of the factors in -
9

---

Published in Transactions on Machine Learning Research (06/2025)
So to which factors to include in h1 in this example, check in fig. 1d which factors are parents of In this case, that is only Bools. Finally, for k2, no new factors are added since in the structure in fig. 1d the parents of Boots do not include any factors not yet in the set of k1.
The procedure to get the subset of state factors for given level of abstraction & and a particle (or hyper- state) shown algorithm First, it initializes a set Q with the set TR, retrieved with GetMinémumSSt. For abstraction level ko, this is what is returned immediately. For higher levels, it then builds the subset incrementally by adding the parents of the factors in Q. That is, to construct the subset of state factors kn, it starts with hn-1 and then adds the parents of these factors.
When the reward function is known, the function GetMinimumSubset directly returns the set IR. When the reward function is unknown, the reward itself is also modeled as a stale factor that takes the same value as the reward. Uncertainty about the reward function can then be incorporated in the belief, and hyper-states may end up with different graph structures for the reward. The IR can then be retrieved by finding the parents of the reward state factor. We demonstrate that our method can deal with uncertainty about the reward and IR in section 4.4.
3.3 Abstract Model Construction
After retrieving a subset of state factors, we construct the abstract model. Since the abstraction uses only subset of the state factors, this involves removing factors, and therefore need to decide how to treat factors that have missing parents one in fig. 1d to create the abstract model on level kn ( fig. 1e), we remove Bools and create distribution for x with only x itself as the parent factor. The question then is how we can define a CCT that does not depend on 'Boots' from the original one that docs.
result of this. To illustrate, when we abstract full model such as the
For probability distributions in known models is logical to resort to marginalization. However, in sec- tion 3.3.1 we show that the problem is more deeply rooted: marginalization leaves us with a term that is difficult to specify since it depends not only on the values of its parents but also the policy, and it change over time. As such there is no fundamentally right approach to do this form of abstraction. Instead, novel ideas and approximate approaches are needed. We explore two initial ideas for this form of abstraction in sections 3.3.2 and 3.3.3. In section 3.3.2 we make an assumption on the abstraction and show that we can simply aggregate the counts in that case. In section 3.3.3, we motivate using approximate abstraction and discuss potential issues that arise with the approximation.
3.3.1 Marginalization of Probability Distributions
Before considering the case of CCTs, we treat the case of probability distributions. For a probability distri- bution, given a factor X with a set of parents Parents(X), we can marginalize out a parent Y or a set of parents. For ease of notation, we show the marginalization for one parent, multiple parents can be removed by repeating this process:
P(z,lz) Σ P(a,, Yj z)
(6)
Σ M5
P(a: 2.3;) |z)
(7)
where z = (21, 22...., 2n, denotes the realization of Parents(X) Y, while o; and yj represent a specific realization of the factors X and Y. The term P(y5 z) acts as a weight for the contribution of P(z. to the marginal distribution P(x; z).
However, estimating P(y, 2) for a DBN is nontrivial. In the running example, consider the probability of moving from to x' = 2 after taking the action right. The sampled model fig. 1d only has the factors and Boots parents of æ, and the abstract model kn (fig. 1e) does not include Boots Following equation 7,
10

---

Published in Transactions on Machine Learning Research (06/2025)
can obtain the marginal distribution for by summing over the separate values of Boots:
(1 =
Σ
pright (z(1a,b)PP((z)))
(8)
be Boots
However, while the probabilities pright (2' [o b) are well defined (e.g., pright = 2 b On) = 0.95), the value of P(b]z) is not as clear. This probability represents the likelihood that the boots are on given a specific location z. However, does not depend solely on x itself. For instance, we might know that the probability of the boots being on is at the start of the episode, but this probability generally depends on the history of actions and observations. In general, can make the following observation:
Observation 1. Accurately estimating Plylz) without additional information is generally not possible. This is because y can depend on other variables, including itself, and on the policy that con change over time.
The view of P(y|z) as weight in equation is related to the concept of weighting function in work on state abstraction (Dearden & Boutilier, 1997; Li al., 2006). Theoretical work shows that, for some abstractions, policy based on the abstract model (with any weighting function) can perform well in the real problem in planning (Li et al., 2006; Abel et al., 2016; Congeduti & Olichoek, 2022) and in RL (Starre et al., 2023). For probability distributions, Dearden & Boutilier (1997) use sort of average of the probabilities but also remark this can lead to suboptimal solutions. The best way to approach estimating Pyy ()) for the optimal performance is still an open problem.
3.3.2 Beliefs and Aggregating Counts for Exact Abstractions
In the previous section we discussod the problem of dealing with conditional probability tables (CPTs) where parents abstracted, leading dependence on the policy and history for estimating P(y 2) in equation 7. In this section, we begin by considering simplified setting where the abstraction is assumed to be exact. This assumption allows to sidestep the difficulty of estimating P(ylz) and to introduce the CCCT more cleanly under idealized conditions. This assumption is made only in this subsection to clarify the conceptual difference between exact and inexact abstractions. The more realistic and interesting case is when the assumption does not hold, which we address in section 3.3.3.
One situation where abstraction makes sense is when the model overspecified: it contains links that are unnecessary. This is the case when the abstract model probabilistically behaves in the same way the full model, which is what assume in this subscction:
Assumption 1. The abstraction ezact. That is, let Z be the set of removed parents for a factor X, let (21, ..,, 2n) denole specific realization of the remaining parends Purends(X) (X) Z, and let 2 gemovedd and 2 removed be two different realizations of the removed parents Z. Then, for all realizations o; of X, assume:
P(z./z) P(z,/2 (2, z remonedy
(9)
= P(z 2 removed)
(10)
This assumption implies that the links between the removed parents and the corresponding child node were obsolete. For instance, consider change in the running example where the boots would have no effect x, then this would mathematically mean that P(r'|z, Boots = On) = P(r'|z, Boots Off). We observe:
Observation 2. Under assumption 1, P(y,Iz) has no influence. That is, since
P(zilz) Σ P(.s,, P(,ll)
(equation 7)
(11)
=Vyer P(z.(z,)).
(12)
11

---

Published in Transactions on Machine Learning Research (06/2025)
Thus, if boots had no inffuence, data collected with boots and off can be used to estimate P(xl (z). For example, consider the conditional counts x(a1|z j = 1, Boots) in table 1.
Observation 2 means that, to marginalize in the CCCT, we no longer have to be concerned about P(y) Which means that in table we can aggregate the counts in the columns, formally:
((z(2))= Σ (xol2,,,))
(13)
For example, to determine the conditional counts table 1, we apply equation 13 to construct the abstracted
Table 1: Initial conditional count table, for æ 1 and ac- tion right.
Table 2: Count table after ag- gregation, for a = 1 and action right.
Table 3: Count table after ag- gregation and normalization, for x == and action right.
Boots
1 x'= =
x' x'= =
x'=1
=
On
8
2+6 = 8+4 = 12
1/2 1/2 + 12 =6 6
Off
4
(or marginalized) counts X from the original counts as follows:
This is done for every action by aggregating the counts
(z'la)=
= Σ
x right b).
(14)
BE Boots
Writing out equation 14 we obtain the counts Fright 1) after aggregation:
x (x' 1/2 1)
Σ right (a' 1,)= =
(15)
bE Boots
and x rrigh 2 1)
Σ
right (x' 2/z = 1,b) = = 4 12.
(16)
be Boots
The resulting conditional counts are shown table Note that now the resulting row has counts (f8, 12)) which are higher than the individual previous rows for Boots On (f2,8)) and Off (f6, 4)). This implies that after abstraction we are (relatively) more confident about these transitions than before. Under assumption 1 this does not have large influence when the prior is close to the true distribution, as in that case these estimates should be close together. However, this could be different when the abstraction is not exact or if the prior is not close to the true distribution.
3.3.3 Aggregating Counts for Approximate Abstractions
Previously, assumed that the abstraction was exact. Of course, this may not always be the case, it may not be necessary to make this assumption. There exist. scenarios where one could argue for the use of approzimate abstractions (Dearden & Boutilier, 1997; Abel et al., 2016; Starre et al., 2023). For example, in cases where a parent only has a small influence, abstracting these parents away can lead to faster learning (Starre et al., 2023). Additionally, reducing the size of the model through abstraction can enhance performance by facilitating faster planning (He et al., 2020).
However, when the abstraction is not exact, observation no longer holds. Specifically, with an approximate abstraction, P(z|z,y) y) generally varies for different instantiations of y. Consequently, P(y|z) does influence the result. In this case, abstracting candidate model could result in probability distribution that deviates significantly from the behavior of the candidate model.
As an example, consider again the running example where with Boots = On we have a probability of moving of 95% and with Boots = Off only 30%. Table shows are initial estimates where Boots still included, counts of 82 and (6, 4} for Boots On and Boots Off. respectively. These are reasonably accurate with, if we translate the counts to probabilities, expected 80% and 40% chance of moving, respectively.
12

---

Published in Transactions on Machine Learning Research (06/2025)
However, when Boots is removed see in table 2 this leads to counts of {8, 12), expected probability of moving of 60%. With Bools being removed from the model the agent is highly likely to be in a state with Boots = Off. and thus this leads to an overestimation of the probability of moving for the agent.
As alluded to in the previous section, the abstraction also increases the confidence the resulting counts. When the abstraction not exact, we could say that the increased confidence in the resulting counts is not warranted, there is overconfidence. This overconfidence can slow down learning since it will take more experience to change the belicf. For example, the change in table 1 of adding an extra observation to the row with Boots Off has relatively larger effect than adding one extra observation after aggregation in table 2.
This means that the proposed aggregation in equation 13 does not work as well when assumption I does not hold, since it can lead to incorrect estimations with a higher confidence. As such, we want to adapt the aggregation method. It is still an open question what the best way to aggregate when using approximatc abstraction.
We propose a way to reduce the overconfidence in the resulting dynamics through normalization scheme, which should lead to quicker learning in cases where the prior and abstraction biased. Let Z T=Y,, V2........ Yn denote the set of removed parents. To normalize, we multiply each entry by
(17)
Ilez |dom(YY)'
where [dom(Y) represents the number of values that the parent Y can take. For example, in the case of the position x from the running example, we have [dom(z)] = 5.
Using X to represent normalized counts, applying the normalization factor equation 17 equation 13 results in:
x(x+2)) IIrez [Y) M2. EYY XYxx..XXx
Σ
X( V1. V2......................... Unn)
(18)
Intuitively, the proposed normalization scheme reduces the counts proportionally to the amount of rows that is removed during aggregation. Applying equation 18 to the example where we remove Boots this leads to:
(s' = 1|x 1) Joo [Boots)
Σ
right (x' 111==1, 11,b)
1 -2 + 6) (--)=44 4,
(19)
BE Boots
and rright = 2/xr- = 1) Idom (dommBools) (Bools)
Σ
rihht = (0,==),)- (8+ 4) =6
1
(20)
bE Boots
also shown in table 3.
By applying the normalization of equation 17 the amount of counts in the table after aggregation is equal to the average amount of counts in the initial prior. For example, table 1 the counts in the rows both sum up to 10, and the counts after the aggregation and normalization also sum up to 10 (table 3).
The proposed normalization provides a robustness against mistakes in the prior and approximate abstrac- tion, by lowering the impact that the prior has on the learning. In our experiments, we investigate this normalization scheme, showing that this can significantly speed up learning.
3.3.4 The Observation Space for Abstract Models
Since we remove state factors from the model in the abstraction, a natural question is how we deal with the observation factors. We can consider two cases, 1) where part of the parents is removed, and 2) when all the parents are removed.
In the first case, we simply perform the aggregation in the same way as for the state factors. It is the second state that poses a problem, as leaves us with no parents for the observation factor. Since in this case the obsorvation would provide no actual information about the underlying state, we enhance the observation space of the abstract model by including an observation "not observed" for all observation factors. For observation factors where all parents are removed the observation function simply returns "not observed".
13

---

Published in Transactions on Machine Learning Research (06/2025)
3.4 Theoretical Support
Here we will show how the combination of FBA-POMCP with the abstraction method can lead to near- optimal performance when the abstraction is good. We first show that transforming the original FBA- POMDP with the abstraction method results in another FBA-POMDP. Because of this, the theoretical guarantees of FBA-POMCP apply to the abstracted problem. Then we give a definition for the quality of the abstraction that gives a guarantee on the performance the original FBA-POMDP. Together this shows that abstractions leads near-optimal solutions with FBBA-POMPP, when a good abstraction used.
First, note that the abstraction results in another FBA-POMDP:
Lemma 1. The result of opplying the abstraction method, described in algorithm 2 and section 3.3, to the original FBA-POMDP results in another FBA-POMDP, the abstract FBA-POMDP.
In appendix C, we present a constructive proof. In essence, abstraction reduces the state space and marginal- ization produces a dynamics function for the resulting state space. Lemma implics that we can use POMCP to find a npar-optimal solution with respect to the belief in the abstract FBA-POMDP, due to the following result:
Theorem (Katt et al., 2019) ) Given a belief b(s, G,x), FBA-POMCP converyes to an c-optimal value function of a FBA-POMDP: (bb & (b, c.
The bias of the value function, 6, can be made arbitrarily small by increasing the maximum search depth. If there is no limit on the search depth, the bias is O ((lo(()) ) in the limit of the number of simulations n starting from the belief b (Silver& & Veness, 2010).
The question that remains is, how good is the solution for the abstract FBA-POMDP in the original FBA- POMDP? In general, the quality of solution when using abstraction depends on the type and quality of the abstraction (Dearden & Boutilier, 1997: Abel al., 2016). We define the quality 1) of the abstraction the upper bound of the difference between optimal value function of the original FBA-POMDP and the value function of the original FBA-POMDP under e-optimal policy for the abstracted FBA-POMDP:
Definition 2.
An abstraction has quality n, s.t. every e-optimal solution π of the abstract FBA-POMDP applied to the original FBA-POMDP has suboptimality bounded by + m::
V(b,a) (V*(b,a) V (b, (b.a)) S 5
(21)
This definition is based existing suboptimality bounds for abstract models such the approximate model- similarity abstraction (Dearden & Boutilier, 1997; Abel et al., 2016), discussed in section 2.4. Informative bounds can be derived, for instance, by assessing how well the abstract model can approximate the original model (Dearden & Boutilier, 1997; Starre et al., 2023). In the case of approximate model-similarity abstrac- tion, the parameter 17 is small when the grouped states have similar transition and reward functions. Recent work shows that, in the context of learning with abstraction MDPs, this type of abstraction can yield such bounds (Starre et al., 2023). Analogously, in POMDPs, similar results could be expected to hold if the dynamics of the abstract model closely resemble those of the true model. Extending the findings in the fully observable to the partially observable setting could be feasible by incorporating learning of the observation function and applying simulation lemma for POMDPs (Lee et al., 2023).
When combined with Theorem 1, definition 2 implics that combining FBA-POMCP with abstraction leads to a near-optimal solution for the original FBA-POMDP, particularly when the abstraction effectively captures the dynamics of the original problem (i.e., when 1) small):
Corollary Given a belief b(s, G. x) and an abstraction, assuming there erists an r for which equation 21 holds, FBA-POMCP combined with abstraction converges to an + n-optimall value function of the original FBA-POMDP: (b, P,
Proof. By lemma 1 the problem after abstraction is still an FBA-POMDP. By theorem 1, we can use FBA- POMCP to get a policy x within e of the optimal solution of this abstract FBA-POMDP. Then, by definition 2 this leads to a solution within + 7 of the optimal solution of the original FBA-POMDP.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Corridor, 20000 simulations
Corridor. 20000 simulatioos,, k0
0.7
Boots
0.6
Door beshed
0.8
Ucor lockpicked
0.5
Button on
Person upened door
0.4
Door opened
0.3
kD
0.2
k_inf Blanningg
0.2
0.1
planning
planning
0.0
0.0
20
40
60
80
100
40
60
100
episodess
episodes
(a)
(b)
Corridor, 20000 simulations, k1
Corridor, 20000 simulations, inf
0.8
0.0
percentoge
0.66
Boots
Boots
0.4
Door bashed
Door bashed
Door lockpicked
Door lockpicked
Bullon on
Bulton on
Person spened door
Person opened doar
Door opened
Door opened
0.0
0.0
episodes
eptsodes
(c)
(d)
Figure 2: a) Performance in the Corridor domain. The learning behavior in the Corridor domain is shown for different models: b) ko, c) k1, and d) kint- The y-axis shows the percentage of runs in which certain behavior or occurrence happened during each episode.
This result shows that we can reach near-optimal performance the original problem with good abstractions, but that better performance can be achieved in theory without abstraction when v > 0. However, in practice abstraction could perform better through faster simulations, and it could get to good performance more quickly through greater statistical strength due to aggregation.
4 Experiments
We aim to investigate three questions; 1) does abstraction lead faster simulations and enable scaling more complex problems, 2) does abstraction lead to faster learning by reducing unnecessary exploration, and 3) does abstraction provide these benefits when the reward function is not known? We empirically evaluated our approach on four domains to answer these questions. The first domain is the Corridor problem from the running example, simple problem where the trade-off of using abstraction is shown. The second domain is Cracky Pavement Gridworld where we show the advantage of abstraction in a very large problem, with a state space of up to size [|] = 6 x 1025, In addition, in this domain we show the effectiveness of the proposed normalization step for abstraction, equation 17, in the ko model. The third domain is an adjusted version of Collision Avoidance (Katt al., 2019; Luo al., 2019), made more complex allow for more abstraction. The final domain Room Configuration, where the agent must learn the reward function. For further details the experimental setup and the domains we refer to appendix D.
4.1 Corridor
The Corridor domain is the domain described in the running example in section 2.1, where there are 8 different Persons that can be present, each with small probability of opening the door. The agent is
15

---

Published in Transactions on Machine Learning Research (06/2025)
uncertain about the transition dynamics of the x-position, for the actions left and right, and the door. We evaluate the abstractions ko, hi, and the full model kinf- The abstraction ko only includes the factor 2. Abstraction L includes I and, depending on the structures included in the belief, can also include the factors Boots, Button and Door
Results We test the effectiveness of two levels of abstraction under a fixed number of simulations. Figure 2a shows the simple moving average of the return per episode, and the shaded arcas show the 95% confidence interval. Figures 2b to 2d illustrate the behavior of the different models across episodes. Specifically, these figures display how often the agent put on the boots, how often the door was opened, and through which means the door was opened. For example, in fig. 2d, it can be seen that in the first episode, the agent rarely lock picked the door (close to 0%), whereas after 20 episodes, the agent lock picked the door in more than 50% of the runs.
First, there is a large difference in the performances between ko and the other two models. This difference occurs because the full model and model hn can learn to open the door through more effective means than simply bashing against it, while ko cannot. This is due to the fact that the model kn only keeps the z factor and does not include Door, Boots, and Button. Consequently, it does not recognize that the actions to open the door, push the button, and put on the boots have any effect. In addition, since these actions have no direct effect on the x-position, Ko is unable to learn interactions with the environment beyond moving left and right. It ultimately learns a strategy of just moving to the right. This strategy can still lead to reaching the goal state, as there is a chance that the door opens when the agent bashes into it by moving right, or when the person opens the door. This can be observed in fig. 2b, which shows that most of the time the agent successfully opened the door by bashing into it. While this shows the agent never learns to open the door by pushing the button, it does occasionally open the door through the lock pick action. This can happen near the end of the episode, with just one step remaining when the agent is at location æ = 3 and the door is still closed. In such situations, the values for the different actions in the tree search will all be zero. Since the action is then randomly chosen among those with the same value, this can lead to selecting the lock pick action.
The k model can effectively learn to interact with part of the environment because it keeps not only the x factor but also the factors that influence x. This means that if the believed model is the correct model, the h model also contains Boots and Door. Consequently, kn learns to put on boots and to lock pick the door, leading to a much better performance than ko. Due to greater statistical strength from aggregation, hy learns to use lock pick more quickly than the full model.
Technically, would be possible for kn to also open the door by pushing the button if the Bullon factor is also believed to influence x. However, as shown in fig. 2c, this did not occur frequently in the experiments. Instead, h rapidly learns to put on boots and lock pick.
When comparing the performance of hn with the full model kinf, we can distinguish three phases. Initially, ki learns more quickly than kine because the full model kinf takes longer to learn to lock pick. Then, kmf catches up as it learns to lock pick. Finally, kint starts to surpass k by learning to open the door through pushing the button, as is visible in fig. 2d.
This experiment shows that when the abstraction is not exact, can initially still lead to better performance because of greater statistical strength due aggregation. Since in this domain the abstract models cannot learn the optimal behavior, they eventually get outperformed by the full model.
4.2 Cracky Pavement Gridworld
The Cracky Pavement Gridworld is a grid world as shown in fig, 3a. The DBN of the domain is shown in fig. 3b. The state space is factored into the z and locations, Rain, and 20 or 80 extra binary factors. Only x, and Rain influence the movement of the agent, though the agent must infer this. Movement success depends on tile type and rain conditions: movement is difficult on Trap tiles, and on the Vendor tile when it is dry, due to the presence of vendor. When it rains, the vendor leaves and the tile becomes casier to traverse. The agent observes z and y noisily and does not know which factors affect transitions. We evaluate the abstiactions ki, ki; and the full model kint. The abstraction kn includes only the factors x
16

---

Published in Transactions on Machine Learning Research (06/2025)
(4.4)
Crucky GrdWord
resalned particle
comnaponding modal resaived particl flter
Goal
Goal
Ro
Trap
Trap
Vendor
Ran
Ran
Bar
Earry
Data
Pertwll Stearvede
Start
(0.0)
64)
(b)
66
Figure 3: a) The Cracky Pavement Gridworld, b) ground truth graph representing the dynamics of the Cracky Paverentt Gridworld problem with 3 extra binary factors, c) example of a full model in the particle filter, d) examples of two abstract models.
Cracky Pavement 80,
0.50
Cracky Paverment Gridwarid, sice 20, 2000 simulations
0.50
6.45
0.45
6.40
6.35
6.30
0.30
0.25
0.30
0.20
k0
0.35
0:35
without cearmatcattion
6.30
0.30
100
400
500
epieodes
(a)
Figure 4: Performance in the Cracky Pavement Gridworld domain, a) with fixed thinking time, b) with a fixed number of simulations.
and y since they are the ones that directly influence the reward (fig. 3b). Abstraction k also includes the parents of and y-
Results First, we examine the results for one particular setting, with extra binary factors and 2000 simulations. Figure 4a shows these results, where the lines represent the simple moving average of the return per episode, and the shaded regions indicate the 95% confidence interval. Both k and the full model kiat struggle to learn good policy, while ko outperforms both.
The primary difference between ko and the other two models that ko retains only the x and factor, while k includes any factor it believes influences r or y, such as Rain or parts of the additional binary factors, and kma retains all factors as does not rast.act. Although ko sacrifices the ability to account for Rain, performs
Table 4: Average number of simulations the Table Average return over the first 500 episodes Cracky Pavement Gridworld.
the Cracky Pavement Gridworld.
Size 20
Size 80
Size 20
Size 80
Time
ku
ki
Kint
ko
kı
kint
Time
ko
kinf
ku
kint
5ms
634
550
272
521
429
149
5ms
0.33
0.26
0.23
0.31
0.25
0.18
10ms
1324
1263
573
1097
871
240
10ms
0.39
0.29
0.26
0.37
0.28
0.21
15ms
1978
1658
660
2044
1726
328
15ms
0.41
0.31
0.27
0.41
0.30
0.23
20ms
2571
2145
803
2433
2360
440
20ms
0.42
0.30
0.28
0.42
0.30
0.25
17

---

Published in Transactions on Machine Learning Research (06/2025)
better because it simplifies learning about the trap states by only considering x and y. This leads to greater statistical strength as it is much easier to learn P(*)(x,,) v) than P(r'|xr, V, rain, and numerous binary factors).
While Kg cannot distinguish between rain and no rain and therefore does not learn when the vendor is on the tile, it can learn to navigate around this tile. Although this is generally not optimal, it is optimal when rain and the vendor are not considered. The full model kinf and l can eventually outperform ko by learning that it is better to cross the vendor tile when it is raining, as shown in appendix E. However, this takes a considerable amount of time, and during the carlier episodes, ho performs much better earlier.
These results shows that the greater statistical strength obtained by removing information, like Rain and extra binary factors, can result in a significant increase in performance. Additionally, fig. 4a compares the performance of kn with and without the proposed normalization step for abstraction (equation 18), demonstrating that the normalization step can significantly improve learning performance.
In fig. 4b, where we compare the performance with a fixed amount of thinking time instcad of a fixed number of simulations, we see that kn oulperforms the full model kint- The main difference between kn and kint is that b abstracts away all the factors that, given the graph topology, are not directly or indirectly relevant for the reward. This means that the 11 model is generally smaller than the kint model, leading to faster simulations. As shown in table 4, 11 performs an average of 2360 simulations with 20ms of thinking time, while the full model only reaches 440 simulations. This increase in simulation speed results in the improved performance shown in fig. 4b.
Table 5 shows that an increase in thinking time generally increases performance, most notably when in- creasing from 5ms to 10ms, with diminishing returns for further increases. The differences between kn and kinf are also most pronounced at lower thinking times, especially with 80 additional binary factors, where the abstraction provides the most benefit. These findings demonstrate that augmenting FBA-POMCP with abstraction can increase performance through computational efficiency.
Overall, these results show that abstraction can be beneficial in multiple ways. Increasing the simulation speed leads to better performance, and simplifying the problem leads to faster learning due to greater statis- tical strength. The improvement in simulation speed is most pronounced when many factors are abstracted away, maximizing the difference in simulation speed between the models with and without abstraction.
4.3 Collision Avoidance
In the Collision Avoidance domain, the agent flies from one side to the other in 10 (width) x 5 grid. The episode ends when the agent reaches the last column, where it has to avoid colliding with moving obstacle. This obstacle has a 20% chance to stay stationary and otherwise randomily moves either up or down. The agent can decide to move up, down, or stay level. We increased the complexity of the original Collision Avoidance (Katt et al., 2019; Luo et al., 2019) by adding additional factors: Speed (slow, fast), Traffic (low or high amount of traffic), Time of Day (day, night), and Obstacle Type (3 types, e.g,, helicopter, plane). These influence the agent's forward movement and the obstacle's behavior, fig. shows the resulting dynamics. Only the obstacle's transition function is uncertain and the agent receives noisy observations of the obstacle. We evaluate the abstractions ko, k1, and kg, which is equivalent to the full model kug- The rastioation ko includes the factors v, y, and Obslacle Y. The abstraction kn additionally includes the factors Speed and Obstacle Type, if Obstacle Type has a connection to Obstacle Y.
Results We again test the effectiveness of two levels of abstraction under a fixed number of simulations. One of the benefits of abstraction is a smaller and (therefore) faster model. Another benefit is an increase in statistical strength through the removal of factors. The lines in fig. 6 show the simple moving average of the return per episode, and the shaded arcas show the 95% confidence interval.
We see that abstraction ko learns significantly faster than both kn and kinf, both with a fixed number of simulations and with a fixed thinking time. The abstraction ko allows for faster learning of the transition function of Obstacle Y since removes the (possible) parents Speed and Obstacle Type. When Speed and Obstacle Type are parents of Obstacle Y in the sampled graph structure, 2 retains these connections. As a result, bn learns the transition function of Obstacle Y at rate comparable to kinf-
18

---

Published in Transactions on Machine Learning Research (06/2025)
X
Fully observable
Partially observable
Speed
Speed
Unobservable
Traffic
Traffic
Time Day
Time af Day
Obstacle Type
Obstacle Type
Obstacle
Obstaclo
Y
Reward
Figure 5: Ground truth graph representing the dynamics of the Collision avoidance problem.
Collision (750 simulations)
Collision (2ms thinking time)
-50.
25.0
27.5
277.
opisode
opisode
33.0
-32.5
-35.0
-37.5
-37.5
-40.0
-4..0
k1
k1
k.im inf
42.5
k.in inf
100
200
100
200
500
episodes
episodes
(a)
(b)
Figure 6: Performance in the Collision Avoidance domain, a) with fixed thinking time, b) with a fixed number of simulations.
In k1, Time of Day and Traffic are removed. However, since their transition functions, along with that of Speed, are considcred known, this does lcad to greater statistical strength learning Speed. The impact of Time of Day and Traffic also less pronounced, as they only influence indirectly through Speed. Nevertheless, h tends perform slightly better than knf- This not due faster simulations; in this domain, any speed up is minimal, and similar results observed even with fixed number of simulations. One potential advantage of removing Time of Day and Thaffic is that it reduces the branching factor in the tree, there will be no separate observations for these factors. This focuses the tree search by eliminating the need to consider these factors, albeit at slight cost to model accuracy.
4.4 Room Configuration
In the Room Configuration domain, the task of the agent is configure items in (width) grid satisfy teacher's preferences. Fach tile contains configurable item with two settings. The teacher is
19

---

Published in Transactions on Machine Learning Research (06/2025)
Room Configuration DBN
Example of full model (lgy). retained in particle fitter
Examples of abstranted models (bs Agl used for planning. cormssuuading full model retained the particle filter
X
Swechh
Switth
Switths
Swildhy
Swesty
Swatthy
Switth
Switth
Starchh
PApPY
Happy
Happy
Happ?
Switll
Fully observabre
HaDpy
Happy
Happy
H1007
Pirisly desernablee
(b)
(6)
Figure 7: a) Ground truth graph representing the dynamics the Room Configuration domain for the switch action, b) example full model in the particle filter, c) examples of two abstract models.
Room Configuration, 400 simulations
Room Configuration, 10 ms thinking time
40
40
35
35
return per episode
30
return per opicode
30
25
25
20
20
15
15
10
episodes
# episodes
(a)
(b)
Figure 8: Performance in the Room Configuration domain, a) with a fixed thinking time, b) with a fixed number of simulations.
concerned only with the configuration of three specific items, but the agent does not initially know exactly which ones. The reward modeled via a fully observable Happy factor, which takes on the same value the reward. The agent must learn which configuration factors affect Happy. Small rewards penalties are given when changing item settings, and large reward is received once all desired configurations are set. The agent receives noisy observations of its location and has imperfect knowledge of movement success. We evaluate the abstraction kg and the full model kin--
We test learning of the reward function and the advantage of abstraction when only factors that (the agent believes) are irrelevant to the reward are abstracted away. The lines in fig. 8 show the moving average of the return per episode, and the shaded areas show the 95% confidence interval. We can see that the agent learns how to perform well in 10 episodes, after which the performance remains the same.
Results
The abstraction ko performs more simulations (455) than the full model kad (365) within fixed amount of time (10ms). This computational advantage allows kn to outperform the full model, as shown in fig. 8b.
20

---

Published in Transactions on Machine Learning Research (06/2025)
Figure 8a further demonstrates that there is no performance difference between the two models when the number of simulations is fixed. These results show that the agent can quickly learn the structure of the reward and that abstraction can increase performance through its increased simulation speed.
5 Related Work
The FBA-POMDP a factored version of the tabular BA-POMDP (Ross et al., 2011). The infiittePPMDP approach (Doshi- Velez, 2009) is a non-parametric Bayesian approach. This approach requires no knowledge of the state space. However, it assumes hicrarchical Dirichlet Process prior, for which providing an informative prior can be difficult. BRL in continuous POMDPs typically makes Gaussian assumptions, such as in Dallaire et al. (2009), where Gaussian processes are the model of choice. To extend our approach to continuous POMDPs, DBNs that work with continuous variables (Grzegorczyk & Husmeier, 2011) could be investigated. Alternatively, constructing different levels abstraction in a continuous domain could done through varying levels of discretization.
The BA-MDP (Duff, 2002), and the respective solution methods (Poupart al., 2006; Ross & Pineau, 2008; Vien et al., 2013), are the fully observable counter-part to the (F)BA-POMDP. In this setting (BRL for MDPs), work has been done on exploring applications of Deep RL (Hoang & Vien, 2020; Zintgraf et al., 2021). This line of work solves the (casier) fully observable problem, and how to extend these methods to POMDPs is unclear.
Other approaches make use of recurrent networks for dealing with partial observability to generalize deep RL to POMDPs (Dung et al., 2008; Hausknocht & Stone, 2015; Zhu al., 2017; Meng et al., 2021). However, these networks are general-purpose, requiring many samples. This realization has motivated RI-specific architectures designed to capture history efficiently (Jaderberg et al., 2019; Ma et al., 2019). Deep variational methods are another approach that can be efficient (Igl et al., 2018; Tschiatschek et al., 2018). However, none of these methods allow for encoding prior knowledge or tackling the exploration problem, to which the FBA-POMDP framework provides an elegant solution.
In the last two decades, there have additionally been many different approaches to (not deep or Bayes) learning in POMDPs, e.g., McCallum (1996); Shani et al. (2005); Azizzadenesheli et al. (2016); Liu & Zheng (2019); Bennett & Kallus (2024). However, these also do not allow for encoding prior knowledge tackling the exploration problem.
Planning with abstractions has been studied before, mostly in the context of MDPs. The method by Dearden & Boutilier (1997), that our approach is based on, applied abstraction to factored problems. We extend this work to the partially observable BRL and planning sctting and introduce a mechanism to automatically create multiple levels abstraction based on the structure of the problem. Another line of work has focused on building abstractions during the tree search (Hostetler al., 2014; Anand et al., 2016). Hostetler et al. (2014) also provide results for doing the tree search using abstraction function. However, this means the simulations themselves need to be done using the full model. Chitnis et al. (2021) instead first learn abstraction, which they then use for planning. Rather than being given an abstraction, their goal is to learn one. We investigate the effects of an abstraction method on learning efficiency and performance. He et al. (2020) do planning in the partially observable setting and construct an abstract model before the tree search. The key difference with our approach is that we do not assume access to simulator of the real environment. Instcad, we learn abstract dynamics while acting in the real-world.
Our work is closely related to posterior sampling approaches in causal RL, particularly the work by Mutti et al. (2024). Their method maintains prior distribution potential factorizations of F-MDP and performs posterior sampling reinforcement learning accordingly. Our approach differs significantly in several aspects. First, we exlend the methodology from fully observable scenarios (F-MDP) to partially observable ones (F-POMDP). Their approach explicitly notes that exact solutions for the sampled F-MDPs are required, a condition generally computationally intractable and even more prohibitive in the context of F-POMDPs. In contrast, our method circumvents this exact-solution requirement by employing an anytime planning algorithm (FBA-POMCP) within the "planning as learning" paradigm.
21

---

Published in Transactions on Machine Learning Research (06/2025)
6 Discussion
A limitation of the FBA-POMCP method is that it does not plan beyond the current episode. By not planning for future episodes, it does not consider the value that knowledge obtained in the current episode can have for future episodes. Approaches that quantify information gain (Zhang et al., 2020; Ambrogioni, 2021; Liu et al., 2021) and those that plan for long horizons (Grover et al., 2020) could address this limitation, and future work could explore combining these stralegies.
A difficulty of applying abstractions within FBA-POMCP lies in marginalizing the belief. As discussed in section 3.3, when aggregating counts for approximate abstractions, it is unclear what the best solution is, since this is generally unknown beforehand and can depend on the policy. Even for fixed policy, marginalization may lead to a belief that misrepresents the true (abstract) dynamics. For example, in the corridor problem, marginalizing away the Butlon factor leads to misrepresented abstract dynamics because marginalizing it away combines the situations where the button is in the non-pushed state with those where it in the pushed state, implicitly resulting in a belief that at each step there is a probability that the button is in the pushed state. This is a misrepresentation since the button starts in the non-pushed state and, since it is marginalized away, the agent will not learn to push the button, it will always be in the non-pushed state. Such situations can make it more difficult for the agent to learn. An idea could be to use knowledge about the starting position and the abstracted model in the marginalization. For instance, if the Bullon factor is removed from the model, we could keep the counts for when it is in the non-pushed state and ignore the counts for the pushed state since it is always in the non-pushed state at the beginning of an episode.
In the Corridor experiment, we aimed to make the results more interpretable by showing how the agent's 's behavior changes during learning, across the different models. This helped clarify the sources of the observed differences in return per episode, as well as the adaptations the agent makes over time. The behavior of the smaller abstract models is casier to understand than that of the full model, and this improved interpretability offers an additional motivation for using abstraction and could be an interesting perspective for future research.
The Corridor experiment also shows that abstraction does not always help, and can in fact be detrimental. When crucial information is removed, it can make learning impossible. In general, the usefulness of abstrac- tion depends how much value (or information) is lost. If the loss in value is too great, more simulations will not help to achieve a better performance. On the other hand, if there is no loss in value the loss in value is relatively small, abstraction can help improve performance by making learning easier and by speeding up simulations during planning.
Combining learning rastractions with guarantees is challenging. In fact, whether it was possible to bound the value loss of based RL using a given n-approximate model-similarity abstraction was an open question until recently (Starre et al., 2023). What can say is that theoretically, for any abstraction, there exists some 17 such that the bound in eq. (21) holds, even if this bound becomes vacuous at higher values However, it is challenging to estimate or verify the actual value of in practice. This motivates abstraction selection (Ortner et al., 2014; Jiang et al., 2015) as an important direction for future work, allowing agents to adaptively switch between representations over time.
Given the challenge of determining whether a specific abstraction will be beneficial, abstraction selection could be viable approach. This can be particularly challenging in RL, where the problem is often not fully known. With abstraction selection, the algorithm would choose which abstraction to select during learning. For instance, selection could be done by deriving value loss bounds for specific abstractions (Dearden & Boutilier, 1997) and using these to make decision. Alternatively, the problem of abstraction sclection could be viewed as a non-stationary multi-armed bandit problem, where at each episode we select a (abstract) model. The problem is non-stationary since the models the agent learns change each episode with the experience it obtains, and thus the policy and the expected reward can also change. Multi-armed bandit methods that deal with such non-stationarity could be used (Garivier & Moulines, 2011; Cheung et al., 2019; Trovo et al., 2020).
22

---

Published in Transactions on Machine Learning Research (06/2025)
Regarding the quality of the abstraction, represented by 7, we can consider different quantities of problem to determine whether yj is small. For example, in the context of approxinate abstractions in MDPs, we can consider approximate model similarity or approximate Q" abstractions (Abel et al., 2016). In an approximate model similarity abstraction, the size of 7 depends on how close the transition functions and rewards of the grouped states are. For approximate Q' abstractions, it depends on the maximum difference the Q" values of the grouped states. Extending these notions to F-POMDPs requires accounting for the observation function and the factorization structure, making such extensions non-trivial. Nevertheless, existing work on approximate abstractions in MDPs provides valuable insights: results indicate that 7 remains small when little information is lost through abstraction. In our setting, this suggests that yj is small when the abstraction primarily removes largely irrelevant factors.
Our abstraction approach has been developed within the framework of FBA-POMDPs. However, the pro- posed abstraction method general and leverages only the structural properties of the problem, making it potentially beneficial for a broader range of F-POMDP algorithms. An interesting direction is investigate how Thompson Sampling (Thompson, 1933), particularly ils adaptation to POMDPs (Bai el al., 2014), could be combined with factored representations and our abstraction framework. Such combination may reduce the dimensionality of the sampling space and further improve scalability.
7 Conclusion
We proposed combining learning and online planning for BRL for FBA-POMDPs with abstraction. We empirically showed that this combination significantly improves learning, scalability, and performance, using intuitive and straightforward form of abstraction. This happens through several effects. First, we have shown that abstraction improves performance by increasing the simulation speed. Moreover, we have shown that abstraction improves performance even with a fixed number of simulations through greater statistical strength. With an abstract model, the agent takes different actions since does not need to explore the dynamics of less relevant factors. Finally, the abstraction method allows FBA-POMCP to learn in very large 1025.
problems with state space up to [S]
To the best of our knowledge, this is the first work to explore abstraction in BRL for POMDPs, represcnting initial step in investigating this combination. In the future, abstraction could also be further incorporated into FBA-POMDP by directly maintaining belief over which factors should be part of the model.
Acknowledgments
This project received funding from the European Research Council (ERC) under the European Union's Horizon 2020 rescarch and innovation programme (grant agree- ment No. 758824 INFLUENCE).
erc
Dounc
References
D. Abel, D. Hershkowitz, and M. Litlman. Near optimal behavior via approximate state abstraction. In ICML, 2016.
Luca Ambrogioni. Knowledge is reward: Learning optimal exploration by predictive reward cashing. arxiv preprint XrXt::210.00818, 2021.
Ankit Anand, Ritesh Noothigattu, Parag Singla, et al. Oga-uct: On-the-go abstractions in uet. In Proceedings of the International Conference on Aulomaled Planning and Scheduling, volume 26, 2016.
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of pomdps using spectral methods. In Conference on Learning Theory, pp. 193-256. PMLR, 2016.
Aijun Bai, Feng Wu, Zongzhang Zhang, and Xiaoping Chen. Thompson sampling basod monto-carlo plan- ning pomdps. In Proceedings of the International Conference on Automated Planning and Scheduling. volume 24, pp. 29 29-37, 2014.
23

---

Published in Transactions on Machine Learning Research (06/2025)
Andrew Bennett and Nathan Kallus. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. Operations Research, 72(3):1071-1086; 2024.
Craig Boutilier and David Poole. Computing optimal policies for partially observable decision processes using compact representations. In Proceedings of the National Conference Artificial Intelligence, pp- 1168-1175. Citeseer, 1996.
Craig Boutilier, Thomas Dean, and Steve Hanks. -heosiin-theoreiccc planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1-94, 1999.
Cameron B Browne, Edward Powlcy, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlf- shagen, Slephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Ai in Games, 4(1):1-43, 43, 2012.
Wang Chi Cheung, David Simchi-Levi, and Ruíhao Zhu. Learning to optimize under non-stationarity, In The 22nd International Conference on Artāficial Intelligence and Statistics, pp. 1079-1087. PMLR, 2019.
Rohan Chitnis, Tom Silver, Beomjoon Kim, Leslie Kaelbling, and Tomas Lozano-Perez. Camps: Learning context-specific abstractions for efficient planning in factored mdps. In Conference robot learning, pp. 64-79. PMLR, 2021.
Elena Congeduti and Frans A Oliehoek. A cross-field review of state abstraction for markov decision pro- cesses. In 34th Beneluz Conference on Artificial Intelligence (BNAIC) and the 30th Belgian Dutch Con- ference on Machine Learning (Benelearn), 2022.
Patrick Dallaire, Camille Besse, Stephane Ross, and Brahim Chaib-draa. Bayesian reinforcement learning in continuous pomdps with gaussian processes. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2604-2609, IEEE, 2009.
Tim De Bruin, Jens Kober, Karl Tuyls, and Robert Babuška. Integrating state representation learning into deep reinforcement learning. IEEE Robolics and Aulomation Letlers, 3(3):1394-114 1401, 2018.
Thomas Dean, Robert Givan, and Sonia Leach. Model reduction techniques for computing approximately optimal solutions for markov decision processes. In Proceedings of the Thirleenth conference on Uncerlainty in artificial intelligence, 1997.
Richard Dearden and Craig Boutilier. Abstraction and approximate decision-theoretic planning. Artificial Intelligence, (9(1-2):219-2) 283, 1997.
Finalc Velli- The infinite partially obscrvable markov decision process. Advances in neural information processing systems, 22:477 485, 2009.
Michael O'Gordon Duff. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002.
Le Tien Dung, Takashi Komeda, and Motoki Takagi. Reinforcement learning for pomdp using state classi- fication. Applied Artificial Intelligence, 22(7-8):761-775) 2008.
Bela Frigyik, Amol Kapila, and Maya R Gupta. Introduction to the dirichlet distribution and related processes. UWEE Technical Report (UWEETR-201000000), 2010.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International conference on algorithmic learning theory, pp. 174-188. Springer, 2011.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 147(1-2):163 223, 2003.
Divya Grover, Debabrota Basu, and Christos Dimitrakakis. Bayesian reinforcement learning via deep, sparse sampling. In International Conference on Artificial Intelligence and Statistics, pp. 3036-3045. PMLR, 2020.
24

---

Published in Transactions on Machine Learning Research (06/2025)
Marco Grzegorezyk and Dirk Husmeier. Non-homogeneous dynamic bayesian networks for continuous data. Machine Learning, 83:355-419, 2011.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-poliey maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pp- 1861-1870. PMLR, 2018.
Matthew Hausknecht and Peter Stone, Deep recurrent q-learning for partially observable mdps. In 2015 aaai fall symposium series, 2015.
J Hc, M Suau de Castro, and FA Olichock. Inffuenco-uumeente online planning for complex environments. Advances in Newral Information Processing Systems, 33, 2020.
Tai Hoang and Ngo Anh Vien. Bayes-adaptive deep model-based policy optimisation. arXiv preprint arxiv:2010. 15948, 2020.
Jesse Hostetler, Alan Fern, and Tom Dietterich. State aggregation in monte carlo tree search. In Twenly Eighth AAAI Conference on Artificial Intelligence, 2014.
Maximilian Igl, Luisa Zintgraf, Tuan Anh Le, Frank Wood, and Shimon Whiteson. Deep variational rein- forcement learning for pomdps. In International Conference on Machine Learning, pp. 2117-2126. PMLR, 2018.
Max Jaderberg, Wojciech M Czarnocki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human-level performance in 3d multiplayer games with population-based reinforcement. learning. Science, 964(6443):855--88)) 2019.
Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforcement learning. In International Conference on Machine Learning, pp. 179-188, 2015.
Rico Jowsch and Oliver Brock. Learning state representations with robotic priors. Autonomous Robots, 39:407 428, 2015.
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101 1998.
Sammie Katt, Frans A Oliehoek, and Christopher Amato. Learning in pomdps with monte carlo tree search. In International Conference on Machine Learning, pp. 1819-1827. PMLR, 2017.
Sammic Katt, Frans A Olichock, and Christopher Amato. Bayesian reinforcement learning in factored pomdps. Tn Proceedings of the 18th International Conference on Aulonomous Agents and MulliAgent Systems, pp. 7 7-15, 2019.
Sammie Katt, Hai Nguyen, Frans A Oliehoek, and Christopher Amato. Baddr: Bayes-adaptive deep dropout rl for pomdps. In Proceedings of the 21st International Conference on Autonomous Agents and Multiogent Systems, pp. 723 731, 2022.
Levente Kocsis and Csaba Szepesvári. Bandit based monto-carlo planning. In European Conference on Machine Learning, pp. 282-293. Springer, 2006.
Jonathan Lee, Alekh Agarwal, Christoph Dann, and Tong Zhang. Learning in pomdps is sample-efficient with hindsight observability. In International Conference on Machine Learning, pp. 19733-18773, PMLR, 2023.
Lihong Li, Thomas J Walsh, and Michael I. Littman. Towards a unified theory of state abstraction for mdps. Al & M, 1(2):3, 2006.
Evan Z Liu, Aditi Raghunathan, Percy Liang, and Chelsca Finn. Decoupling exploration and exploitation for rentrrreinfore learning without sacrifices. In International conference on machine learning, pp. 6925-6933 PMLR, 2021.
25

---

Published in Transactions on Machine Learning Research (06/2025)
Y. Liu and J. Zheng. Online learning and planning in partially observable domains without prior knowledge. Proceedings of the ICML 2019 Workshop on the Generalive Modeling and Model- Based Reasoning for Robotics and A1, 2019.
Yuanfu Luo, Haoyu Bai, David Hsu, and Wee Sun Lee. Importance sampling for online planning under uncertainty. The International Journal of Robotics Research, 38(2-3):162-181, 2019.
Xiao Ma, Peter Karkus, David Hsu, Wee Sun Lee, and Nan Ye. Discriminative particle filter reinforcement learning for complex partial observations. In International Conference on Learning Representations, 2019.
Andrew Kachites McCallum. Reinforcement learning with selective perception and hidden state. University of Rochester, 1996.
Lingheng Meng, Rob Gorbet, and Dana Kulić. Memory-based deep reinforcement learning for pomdps. In 2021 IEEE/RSJ internalional conference intelligend robols and systems (TROS), pp. 2021.
IEEE,
Kevin P Murphy. Machine learning: probabilistic perspective. MIT press, 2012.
Kevin Patrick Murphy. Dynamic Bayesian networks: representation, inference and learning. University of California, Berkeley, 2002.
Mirco Mutti, Riccardo De Santi, Marcello Restelli, Alexander Marx, and Giorgia Ramponi. Exploiting causal graph priors with postcrior sampling for reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024. URL http:://ppaarrreeooo.ecooorrr//e
Ronald Ortner, Oclaric-Ambryy Maillard, and Daniil Ryabko. Selecting near-optimal approximate state representations in reinforcement learning. In International Conference Algorithmic Learning Theory,
pp. 140-154. Springer, 2014.
Tan Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advonces in newral information processing systems, 29, 2016.
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, pp. 697 704,704,40 2006.
Stéphane Ross and Joelle Pineau. Model-based bayesian reinforcement learning in large structured domains. In Conference on Uncertainty in Artificial Intelligence, volume 2008, pp. 476. NIH Public Access, 2008
Stéphane Ross, Joelle Pineau, Brahim Chaib-draa, and Pierre Kreitmann. A bayesian approach for learning and planning in partially observable markov decision processes. Journal of Machine Learning Research, 12(5), 2011.
Stuart J. Russell and Peter Norvig. Artificial Intelligence: a modern approach. Pcarson Education Limitod London, UK, 2016.
Guy Shani, Ronen I Brafman, and Solomon E Shimony. Model-based online learning of pomdps. In Machine Learning: ECML 2005: 16th European Conference on Machine Learning, Porto, Portugal, October 3-7, 2005. Proceedings 16, pp. 353 553-364. Springer, 2005.
David Silver and Joel Veness. Monte-carlo planning in large pomdps. In Neural Information Processing Systems, 2010.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 57977587) 2016.
Rolf AN Starre, Marco Loog, Elena Congeduti, and Frans Olichock. An analysis of bodell-based reinforce- ment. learning from abstracted observations. Transactions Machine Learning Research, 2023.
26

---

Published in Transactions on Machine Learning Research (06/2025)
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biomelrika, 25(3/4):285-2) 294, 1933.
Sebastian Thrun. Monte carlo pomdps. In Advances in Neural Information Processing Systems, volume 12, pp. 1064-1070, 1999.
Francesco Trovo, Stefano Paladino, Marcello Restelli, and Nicola Gatti. Sliding-windww thompson sampling for non-stationary settings. Journal of Artificial Intelligence Research, 68:311 08:311-364, 2020.
Sebastian Tschiatschek, Kai Arulkumaran, Jan Stühmer, and Katja Hofmann. Variational inference for data-efficient model learning in pomdps. arXiv preprint 1rrXi:1805.000 2018.
Ngo Anh Vien, Wolfgang Ertel, Viet-Hlug Dang, and TaeChoong Chung. bayesian reinforcement learning. Applied intelligence, 39(2):345-353 3533, 2013.
Monte-carlo search for
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data. Advances in Neural Information Processing Systems, 34, 2021.
Jin Zhang, Jianhao Wang, Hao Hu, Yingfeng Chen, Changjic Fan, and Chongjic Zhang. Learn to effectively explore context-based meta-rl. arXiv preprint Xiv:2000 08170, 2020.
Pengfei Zhu, Xin Li, Pascal Poupart, and Guanghui Miao. On improving deep reinforcement learning for pomdps. ai:::1100400000 2017.
Luisa Zintgraf, Sebastian Schulze, Cong Lu, Leo Feng, Maximilian Igl, Kyriacos Shiarlis, Yarin Gal, Katja Hofmann, and Shimon Whiteson. Varibad: Variational adaativ deep via meta-learning. Journal of Machine Learning Research, 22(289):1-39, 2021.
27

---

Published in Transactions on Machine Learning Research (06/2025)
Algorithm 5 Sequential Importance Sampling
Algorithm 6 Initialize Particle Filter
1: Input: (8s; te: ==o current (weighted) filter
1: Input: Péu prior over initial state
a, o: action and observation
n: number of desired particles
2: for i 1e....,, do
2: for i O,..., n do
3: s ~ p(11s a; G. Xi)
3: (s,, G₁ Xi) ~ Pso
w! f mi x p a; Gi)
uy <
X U(x,, Si, Si,a, 0):0)
end for
end for
6: return
{8t. Gi, Xi, xi, wi)
return
{s/ Gi X,, W
Normalize & re-sample
A Extension Belief tracking in the FBA-POMDP
The belief, the posterior over the current state, is a probability distribution over the POMDP state and its distribution E A x D)) given the observed history h, = (og, (0o,0),..,,0--..... 9,-1, Unfortunately, the computation of the belief update is intractable most problems. Thus, the belief is often approximated with particles instead (Thrun, 1999). A particle filter represents distribution through particles, which this case represent F'BA-POMPP states, specifically each particle is weighted FBBA-POMP state (w, 8, G,x) with (unnormalized) weight w R+
There are numerous sampling mechanisms for updating the belief given new action-observation pair (Thrum, 1999). Here, we focus on sequential importance sampling (SIS). SIS consists of two operations: propagation and re-weighting (see algorithm 5). First, the proposal distribution propagates a particle by sampling its next value from the FBA-POMDP transition function p(s'|s, a). Then, the likelihood the particle generating the received observation p(olš, a, š') used to re-weight the particle (recall equation 3). The initial belief (particle filter) is initialized by sampling from the priors over the POMDP state and the DBNs describing the dynamics (see algorithm 6).
Specific to the FBA-POMDP, the belief over the topologies can deteriorate: the number of unique graph structures is determined (and limited) by the initial particle filter, as topologies do not get updated during the belief updates. When that happens, Katt al. (2019) ro-invigorate the belief with a Settropoois-Hasttngge Aithin-Gibba sampling procedure (Murphy, 2012).
B Algorithms
Algorithm shows the main loop of the FRA-POMCP algorithm (Katt al., 2019). The Simulate that is uses is shown in algorithm The AetionyActioSeleeettie selects the action that has the highest value. In case of lie, it randomly selects of the actions with the highest value. Algorithm 9 shows the Slep function when abstractions are used.
Algorithm 7 FBA-POMCP
Input: B: particle filter with hyper-states š num sims: number of simulations to do.
2: An +
// The emply history (i.e., now)
3: for i 1,..., num sims do
4: // First, we root sample a hyper-state:
$~B
// 'Samle from belief
Simulate($, 0, ho)
end for
8: a Greedy-ActinnSeeetionnn)) return
28

---

Published in Transactions on Machine Learning Research (06/2025)
Algorithm 8 Simulate
Input: 8 (s, G. x): hyper-state
d: search depth
h: simulated history.
2: IsTerminal == max depth then
3: return
end if
a UCTactionSellccion(())
~~ R(s,a)
8',0 + a))
8: h' + a))
9: if 1/ E Tree then
10: r -+ ++R+ Simulate(s',
11: clsc
12: ConstructNode(())
13: r- R RollOut(5', h!)
14: end if
15: (...)
Update statistics in nodes
16: return
Algorithm Step (with abstraction)
Input: 8: abstracted hyper-state
a: simulated action.
// Recall that 5 = (5, G, X), with containing current state
s',0 o (-s,)))
// Sample next state and observation from abstracted counts.
4: 8' < G.))
5: 5' G.X)
6: return 800
C Proof
We restate the Lemma from section 3.4 and give proof sketch:
Lemma 1. The result of applying the abstraction method, described in Algorithm 2 and Section 8.3, to the original FBA-POMDP results in another FBA-POMDP, the abstract FBA-POMDP.
Proof. First, define the observation space and function, followed by the state space for different levels of abstraction. The reward function does not require changes since, during abstraction, the models in the particles always keep the factors that are believed to be part of the IR set.
As detailed in section 3.3.4, the abstract observation space is enhanced by including a "not observed" option for all observation variables. This addition addresses scenarios where the observation function depends state factors that are abstracted away; in such cases, the observation function returns "not observed", Otherwise, the observation space and function remain unchanged.
For the state space, we distinguish abstraction level ko from other abstraction levels. For ko, only the factors in the set IR are included, while higher abstraction levels can include additional factors depending on the topology.
For level kg: the state space $ derived by aggregating states based on the distinct values of the remaining factors. Transition functions are adjusted for the new state space through the marginalization procedure described in section 3.3.
29

---

Published in Transactions on Machine Learning Research (06/2025)
Table 6: Fixed experiment settings,
Parameter
Corridor
Cracky Pavernet
Collision
Room Conf
0.95
0.95
0.95
0.95
# of particles in belief
500
500
500
10000
# of episodes
100
500
500
50
# of runs
100
100
10000
1000
Horizon (H)
20
12
20
13
UCT constant
5
1
500
10
Reinvigoration
Yes
No
No
Yes
log-liiel threshold
-500
N/A
N/A
-500
State factors
5
[23, 83]
15
320
x 107, 6 x 1025
6000
196608
For higher abstraction levels, the belief specifies the factors that are relevant. For example, for abstraction level h1, factors that directly influence the IR set are also considered relevant. Similar to ku, factors that are never considered relevant are removed. For state factors included in only some models, the abstract state space is enhanced by adding a "not relevant" value. This value ensures transitions default to "not relevant" when the factor is not present in a model. Transitions are then adjusted for the new state space through the marginalization procedure. The observation function is also adjusted to return 'not observed' for factors that return "not relevant".
Combining these transformations, obtain a fully specified FBA-POMDP after abstraction.
In practice, implementing the "not relevant" value is unnecessary, as only factors included in the simulated particle affect observations and actions during tree scarch.
D Extended Experiment Details
D.1 Experimental Setup
In the experiments, we investigated various levels of abstraction across different domains and considered both a fixed amount of simulations and a fixed amount of computation time. For cach level of abstraction (including the full model) and each of the different settings, we ran a separate experiment. Due to the stochasticity in the runs, we conducted up to 10000 runs for each experiment. In the figures, we report the moving average of the returns over a window of 10 (#=t"ytatt with the shaded areas indicating the 95% confidence interval. To avoid cluttering the figures with markers, placed only 5 markers per line, spaced evenly along the x-axis.
The settings of the experiments, and some specifics of the environments, are detailed in table 6. In the table, y denotes the discount factor, the UCT constant is the exploration constant, and the log-likelihood threshold is the threshold below which reinvigoration triggered. The log-likelihood is obtained during the belief update, and a low log-likelihood can indicate the belief does not adequately represent the observed data. The parameters were chosen to maintain a reasonable total run time. Because of this, ran the experiments in the Cracky Pavement Gridworld and the Collision avoidance domains without the invigoration step. We show in appendix E that the effect of abstraction is orthogonal to the effect of reinvigoration.
We performed the experiments with a fixed number of simulations on three different machines: Intel(R) Xeon(R) Gold 6130 CPU @ 2.10GHz with 384GB RAM, Intel(R.) Xeon(R) Gold 5218 CPU @ 2.30GHz with 190GB RAM, and AMD EPYC 7452 32-Core Processor CPU & 2.0GHz with 256GB RAM. For the experiments with a fixed amount of computation time, we used (2 cores of) an AMD EPYC 7452 32-Core Processor CPU @ 1.5GHz with 512GB RAM. The software is written in C++.
30

---

Published in Transactions on Machine Learning Research (06/2025)
D.2
Domain Descriptions
D.2.1 Corridor
The Corridor domain is the domain described in the running example in section 2.1, where there are 8 different Persons that can be present, Each person has a slightly different probability of opening the door, such that the probability that the person opens the door during an episode approximately between 0.0125 and 0.1. In this domain, we assume prior knowledge of all observation functions and the locations of the start, boots, button, door, and goal. In addition, we assume the structure of the transition functions of the factors Button, Boots and Person are known, in other words, the prior includes only models where the parents of these factors are correctly specified.
What is unknown is the structure of the transition function of the x-position, for the actions left and right. For this transition, the prior includes the following combinations of factors as parents for the x-position transitions, 1) x, 2) z and Boots, 3) x, Boots, and Door, and 4) x, Boots, Door, and Button. Each of these combinations is assigned the same probability in the prior. The transition function of the door is also not fully known, with the prior specifying 50% chance of Button being prosent as parent. The prior is initialized oplimistically, and so the agent initially overestimates its chances of success and the probability that the person that is present will open the door. It has to learn the correct structure and transition probabilitios.
We consider the abstractions kn, ki and the full model kint- The abstraction ko only includes the factor x. Abstraction k1 includes x and, depending on the structures included in the belief, can also include the factors Boots, Button and Door.
D.2.2 Cracky Pavement Gridworld
The Cracky Pavement Gridworld is a grid world as shown in fig. 3a. The DBN of the domain is shown in fig. 3b. The state space is factored into the x and y locations, Rain, and several extra binary factors. These extra factors could be global (e.g., light conditions) or local (e.g,, presence of a chair in a specific location). In reality, only x, y, and Rain influence the movement of the agent, as can be seen by the incoming edges of x and y. The "Trap" and "Vendor" tiles depicted in fig. do influence the movement of the agent but are not included as separate factors because their dynamics are already captured by x, y, and Roin. Their interaction is described in the next paragraph.
The agent is initially located at "Start" and is rumning low battery, so it has to move to a charging station at one of the "Goal" locations. The agent only observes its x and location and does so with noisy sensor. For both r and y, the agent makes the correct observation 90% of the time. If an incorrect observation occurs, a randomly selected adjacent location is returned. At the edges, the probability of receiving the correct observation increases to 95%. The agent can move in all four directions, but the movements can fail. The chances of movement failure are influenced by a global factor called Rain which represents whether the tiles are dry wet. The Rain factor is initialized randomly, and every timestep there is a 5% chance that the rain condition changes. On normal tiles, actions succeed 95% of the time when there is no rain and 66% of the time when it is raining. However, on the Trap tiles with cracked pavement, moves succeed only 10% of the time. Additionally, when it is not raining, a vendor with a cart occupies the Vendor tile, making it harder to move past with only a 10% success rate for moving. Conversely, during rain, the Vendor tile is vacant and functions like a normal tile. Therefore, to behave optimally, the agent should traverse the Vendor tile when it is raining and circumvent it when dry.
In this domain, we assume prior knowledge of all observation functions, the transition functions of Rain and the extra binary factors, and the start and goal locations. Additionally, we assume that it is known that the z and factors both (at Ieast) depend on each other. However, there is no prior knowledge of the trap locations and the vendor locations, meaning that none of the possible count tables in the belief space specily different movement probabilities on these locations. Some of the graph structures in the belief space include Rain and/or extra binary factors (three in fig. 3b) as parents of and y, implying the agent does not know whether or not these factors influence its movement. The extra binary factors are initialized randomly and have 20% of changing at each step. In this problem, the agent has to learn that x, y, and Rain are the
31

---

Published in Transactions on Machine Learning Research (06/2025)
only relevant factors for its movement. This task is complicated by the interaction between the trap states and several uninformative factors, as the agent may mistakenly attribute its inability to move on trap states to the presence of some of these uninformative factors.
As shown in table 6 on page 30, we run the experiments with two different amounts of extra binary factors: 20 and 80. The total amount of state factors is 23 and 83, respectively, since both settings also have the X,Y, Y,, and Rain factors. Scalability in the number of factors is very hard and important because the size of the state space, and the possible graph structures, grow exponentially with the mumber of factors. With 20 and 80 extra binary factors this domain has state space of approximately 5 x 10" and 6 x 102s states, respectively. Factored representations are needed to find solutions for problems of such sizes. Flat learning methods like Bayes-Adaptiv POMCP (Katt et al., 2017) are not feasible here, even in the simple case of 20 extra binary factors. This is because representing the transition table for just action, a table of size |S|? requires more than 9 million GB per particle.
We consider the abstractions ña, ki, and the full model kint- The abstraction kn includes only the factors x and y since they are the ones that directly influence the reward (fig. 3b). Abstraction k also includes the parents of and y. We scale the number of extra binary factors to test the speedup and to see how it affects the performance.
D.2.3 Collision Avoidance
In the Collision Avoidance domain, the agent flies from one side to the other in a 10 (width) x 5 grid. The episode ends when the agent reaches the last column, where it has to avoid colliding with a moving obstacle. This obstacle has a 20% chance to stay stationary and otherwise randomly moves either up or down. The agent can decide to move up, down, or stay level.
We increased the complexity of the original Collision Avoidance (Katt et al., 2019; Luo et al., 2019) by adding additional factors. These additional factors influence those in the original problem. Figure 5 shows the resulting dynamics. We added the factors Speed (slow, fast), Traffic (low high amount of traffic), Time of Day (day, night), and Obstacle Type (3 types, e.g., helicopter, plane). Obstacle Type and Time of Day are fully observable and do not change during the episode. The agent receives a noisy observation of the obstacle (accurate around 80% of the time). The agent has an 85% chance to move one cell forward. If the Speed is high, it has a 15% chance to move forward two columns. If the Speed is low, it has a 15% chance to stay in the same columi.
The Speed is influenced by the Traffic. When the amount of Traffic is low, there is a 90% chance that the Speed changes to (or stay at) high and 10% chance that the Speed changes to (or stay at) low. This is reversed when the Traffic is high. The Traffic is influenced by the Time of Day in a similar way, when it day there is 90% chance that the Traffic changes to (or stay at) high and a 10% chance that the Traffic changes to (or stay at) low. This is reversed when it is night. The Time of Day is randomly chosen at the start of an episode, with a 50% chance of either day or night.
We assume prior knowledge of all transition and observation functions, except for the transition probabilities of the obstacle. There are four different graph structures for the obstacle transition function to which the prior assigns a positive probability. These structures include: 1) the structure where Obstacle Y is only influenced by itself; 2 and 3) the structures where it is influenced by itself and either Speed or Obstacle Type; and 4) the structure where it is influenced by itself, Speed, and Obstacle Type. Each structure has a 25% probability.
We consider the abstractions ka, ki, and k2 which is equivalent to the full model hinf The abstraction ko includes the factors x, y, and Obstacle Y. The abstraction kı additionally includes the factors Speed and Obstacle Type, if Obstacle Type has connection to Obstacle Y.
D.2.4 Room Configuration
In the Room Configuration domain, the task of the agent is set up a classroom in a desirable way for a teacher. We model this environment as 4 (width) 3 grid, where each tile contains configurable item
32

---

Published in Transactions on Machine Learning Research (06/2025)
Cracky Pavement Gridworld, size 1, 2000 simulations
return per episode
0.3
0. reinvigoration, normalized
0.2
1, reinvigoration, normalization
k iiiff, reinvigoration, normalization N/A
200
400
600
800
1000
1200
1400
episodes
Figure 9: Comparison with invigoration for longer number of episodes.
with two settings. The agent can change the configuration of these items. The teacher concerned only with the configuration of three specific items and happy once these are configured correctly.
The reward function is (largely) unknown to the agent in this domain, as the agent does not initially know configuration factors that influence the reward. To address this, we model the reward with state factor called Happy, which takes on the same value as the reward and is fully observable. While Нappy is fully observable, the agent does not know exactly which configuration factors influence it. That is, the prior belief assigns a non-zero probability to multiple sets of parents of Happy. Therefore, the agent must learn which configuration factors are relevant to the reward. The Happy factor has four different states: neutral (0 reward), slightly unhappy (-1), slightly happy (+1), and very happy (100). The agent receives reward when it performs the switch action, and this reward depends on its location and the status of the configurable items. Specifically, the agent receives small reward penalty (+1) when it changes the configuration of item to the correct or incorrect setting, respectively. Once it sets the configuration of all three items the teacher desires, it receives a large reward (100).
While the configurations of the items are fully observable, the agent receives noisy observations of its own location. For both x and y, the agent makes the correct observation 95% of the time. an incorrect observation occurs, randomly selected adjacent location is returned. At the edges, the probability of receiving the correct observation increases 97.5%. Movement actions have a 95% chance of moving in the intended direction, whereas the switch action to change the item settings is always successful. The agent has prior knowledge of the observation function and the transition function for switching. Additionally, all the possible initial belief states underestimate the probability that the move action is successful.
We consider the abstraction ky and the full model kit- The abstraction ky keeps the factors connected to the reward. The structures in the prior belief always include x, y as parents of Happy. The prior belief is defined such that assigns non-zero probability only to structures where the abstract models ką and ko are identical. Thus, in the experiment, we only kn-
E Further Experiments
Here, we demonstrate that abstraction can improve performance when we use the invigoration step from FBA-POMCP, and that kj and the full model kn can eventually outperform kg- We conducted 100 runs for each setting and report the simple moving average of the return per episode, with the shaded areas showing the standard error.
33

---

Published in Transactions on Machine Learning Research (06/2025)
We ran an experiment with invigoration over larger number of episodes, shown in fig. 9. Initially, ko outperforms kn and kint However, with enough data, the 11 and kinf models become accurate enough to surpass kn in performance. The 11 model matches the performance of kinf because the number of simulations is fixed.
For larger problem sizes and with fixed thinking time instead of a fixed number of simulations, is expected initially outperform kigt. Additionally, ko should show an even greater initial improvement over kinf; and it could take even longer for kint to surpass the performance of ko-
34


Reviews:
[{"review_id": "hFEoaazJrL", "reviewer": "Reviewer_5AP2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* This paper is impressively ambitious---it attempts to solve the very challenging problem of online planning in large POMDPs, all while learning factored abstractions suitable for Bayesian RL. \n* The paper is very well written: even though I am not super familiar with Bayesian RL, the background section gave me enough context to follow along. Similarly, although I am not familiar with FBA-POMDPs, I enjoyed learning about them.\n* The problem of marginalizing certain variables in the abstract DBN was well motivated and well explained. \n* The experimental section was thorough: results, error bars, evaluation metrics and computational resources were all clearly expressed. Furthermore, the trade-off inherent in using more abstract models was well studied. Furthermore, they successfully solved moderately large POMDPs using the proposed techniques.\n\nWeaknesses:\n* The biggest weakness was that I discovered more assumptions as I kept reading the paper. For e.g., from the background section, I was expecting the DBN and the CPTs to all be learned autonomously, but different experiments used varying degrees of domain knowledge. Although this was explicit in the experiments section, a brief note explaining what parts of the POMDP are assumed vs learned in the main text would be helpful.\n* There were no other POMDP baselines. What about PBVI? Particle filtering + RL? Having some common baselines would further improve the experimental section. \n* Some of the assumptions made by the algorithm seemed quite extreme: for e.g., \"Assumption 1\" and the normalization factor in Equation 15, which if I am not mistaken, would not only require domain knowledge about which variables constitute the state, but also how many possible values they can take on (also doesn't apply to continuous domains). \n* The discussion in Sec 3.4 seemed superfluous. Unless I missed something, the authors simply state that if \"good\" abstractions are given to the agent, it can achieve bounded value error. But does the proposed algorithm discover such an abstraction? What sort of state abstraction does it learn (in the taxonomy of Abel et al which the authors cite)? How do we know that the value function learned with the learned abstractions have bounded error?\n\nDespite these weaknesses, I enjoyed reading this paper and believe that it is an interesting approach towards doing RL in POMDPs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper approaches the POMDP problem by combining factored state abstractions and Bayesian RL. They do so by representing the problem using a factor graph (or DBN); parts of the DBN are known and others are unknown. Over time, the agent updates its beliefs about the unknown parts of the DBN representation of the problem. The factored model is then used by a POMCP-style planner to obtain a belief conditioned policy. Experimental results ablate the importance of abstraction towards solving large POMDPs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Be more upfront about what parts of the POMDP are assumed to be given in the Background and Methods section. \n2. Consider adding common POMDP baselines. \n3. Improve the theoretical claims made in Section 3.4\n\nFor more details on these changes, please refer to the \"weaknesses\" portion of my review.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7fBPVzqHC7", "reviewer": "Reviewer_q3iN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While abstraction is an essential subject in RL, I genuinely have a hard time following the paper. I only managed to read up to page 10. \n\nThe paper is highly cluttered and hard to follow and understand. The authors are highly encouraged to rewrite the paper with a well-defined flow and well-defined, well-defined notation and concepts. Please mathematically define everything in a concise manner, including the concept of abstraction. \n\nPlease also have a senior person read the paper, to avoid cluttered language, e.g., \n\"After retrieving a subset of state factors, we have to construct the abstract model.\" no, you don't \"have to.\" \n\"We explore 2 first ideas.\" what \"2\" first ideas? From what ordered set of ideas? Why 2, not two?\ntitle of 3.3.1, \n\"Before considering the case of CCTs, we treat the case of probability distributions.\" please use the terms carefully without clutter. \nThe use of \"will\" in many places. \n...\n\nThe first time the abbreviation BA-POMCP is used, it is not defined.\n\n\"in section 2.2, which will turn out to be a (belief-space) Partially-observable Markov decision process itself.\" This has been known for a very long time. \n\nThe authors have already defined the POMPD abbreviation; there is no need to have it redefined in 2.1. \n\nIn line 36 of page 3, there is an x on the left-hand side but no x on the right-hand side. \n\nUp to the place I have read, the paper relies on the graphical model, and there is no use or relevance to DBNs. Why bring DBN in?\n\nIn the line above eq 1, why do we have the mentioned equality for the R? Is there no uncertainty about the reward function? Please make sure it is clarified in the draft. \n\nIn the second line of \"Action selection in the FBA-POMDP,\" the authors talk about high-dimensional problems. That is not even the setting of this work; there is no dimension here; what do the authors mean? \n\n\"The simulation traverses to a leaf by picking actions according to UCB.\" How is it done?? The paper mentioned is for bandits. \n\nDoes the agent have access to counts? How? Isn't it POMDP?\n\nWho provides the abstractions? Are these given? If so, that is a very strong assumption. \n\nIn Eq 4, I don't follow the equality. Please distinguish between random variables and their realization. What is that summation over? Collection of random variables Y?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study abstraction in POMDP. \nThe paper is highly cluttered, making it hard to understand the contribution.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please make the paper concrete and concise, with clear definition of all the terminologies used.", "broader_impact_concerns": "I defer the answer for later.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qPFOmjsfaz", "reviewer": "Reviewer_9cu2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written and very detailed (sometimes even too detailed, more on that below);\n- The paper tackles a general framework of Bayesian RL for Factored MDPs, which technically subsumes a wide range of domains and learning algorithms;\n- The paper provides various interpretable empirical results to support the proposed abstractions.\n\nWeaknesses:\n- The writing is very extended and not clearly focused on the core contributions of the paper;\n- While the framework is general, it is known to be impractical in many practical scenarios. The method here is indeed striving to make the approach more practical, but the experiments are bound to synthetic domains with categorical factors;\n- The theoretical corroboration is nice but leaves out the most interesting question: How abstraction affects optimality (aka the $\\eta$ value in the paper).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims at scaling Bayesian RL to (possibly large) factored POMDPs through abstractions, which filter out factors that do not have direct dependencies with the reward.  Coarsely, the abstractions work as follows: First are considered only the features that affect the reward directly; then, the parents of these features, and so on and so for to obtain different degrees of abstractions. The paper provides a small theoretical corroboration and an empirical evaluation in illustrative, discrete domains to show that: Abstractions reduce the size of the model; Abstractions improves the overall performance by speeding up learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Instead of requesting changes, I am using this space to report some questions I had while reading (which may be addressed in a revised manuscript or in the discussion) and some suggestions on the presentation.\n\nQuestions:\n1) The abstractions are here proposed for Bayesian-adaptive approach to Factored POMDPs. However, the way abstractions are constructed is general. Can they provide benefit to other algorithms for Factored POMDPs? An interesting instance is Thompson sampling.\n2) The way abstractions are built, the increasing degree of abstraction allows to consider factors that affect the reward less directly. Long-term dependencies could escape the short chain of dependencies considered with smaller $k$. An approach to target this could be to model the factors dependent with the value of a policy instead of the reward. However, this can easily increase the complexity of the model.\n3) Developing Proposition 2 further, can we say anything about when $\\eta$ is expected to be small?\n\nSuggestions: I am providing here below some suggestions on how the presentation of the paper may be tweaked. Clearly, those are mostly a matter of taste and they are not critical for my recommendation. I am reporting them anyway in case they can be useful for future versions of the manuscript.\n\nThe paper feels a little bit unfocused and over-detailed, e.g., it takes almost 8 pages before the way abstractions are built is described and only after the discussion it was clear to me that the aim of the paper is to extend the work of Dearden & Boutillier to POMDPs (abstractions are essentially similar to theirs, aside from partial observability issues). Instead, a lot of space is dedicated to present the background (which is non-standard to be fair) and various details that shall mostly belong to the appendix (such as machines used for computation and extended empirical details).\n\nPerhaps, the authors may consider restructuring the paper in these terms: Presenting the idea as an extension of the work by Dearden & Boutillier to Factored POMDPs (in general, without tying it to Bayes-adaptive methods) and focusing the text on abstractions and additional challenges of partial observability, possibly leaving details of the setting to prior works. I do not see particular reasons why this paper could not fit into a \"short submission\" (12 pages by TMLR standard) more centered on the core contribution rather than the general background.\n\nAnother aspect that I found interesting but not fully developed is the interpretability of the results. It is very nice to be able to go through the experiments and understand how the policy is changing while learning. Perhaps interpretability could also be mentioned as a motivation for abstractions.\n\nFinally, some works on *causal RL*, where causal factors on the transitions dynamics and/or reward are studied, could be mentioned in the manuscript. Some pointers are:\n- Zhang et al. 2020, Invariant causal prediction for block mdps;\n- Tomar et al. 2021, Model-invariant state abstractions for model-based reinforcement learning;\n- Gasse et al. 2021, Causal reinforcement learning using observational and interventional data;\n- Feng et al. 2022, Factored adaptation for non-stationary reinforcement learning;\n- Mutti et al. 2023, Provably efficient causal model-based rl for systematic generalization;\n- Mutti et al. 2024, Exploiting causal graph priors with posterior sampling for reinforcement learning.\n\nThe latter, especially, deals with extending Thompson sampling for priors over factors topology for Factored MDPs, which may have some interesting connections with this paper.", "broader_impact_concerns": "the paper can be categorized as fundamental research. The broader impact of the results can be hardly assessed at this stage of research.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)