Information-guided Planning: An Online Approach for Partially Observable Problems
Authors: Matheus Aparecido Do Carmo Alves
Amokh Varma
Yehia Elkhatib
Leandro Soriano Marcolino
Venue: NeurIPS 2023 poster (2023)
Keywords: Information-guided planning
Planning under uncertainty
Sequential decision making
TL;DR: IB-POMCP is a novel algorithm that performs an online and information-guided planning process under uncertainty to solve sequential decison making problems.

Abstract: This paper presents IB-POMCP, a novel algorithm for online planning under partial observability. Our approach enhances the decision-making process by using estimations of the world belief's entropy to guide a tree search process and surpass the limitations of planning in scenarios with sparse reward configurations. By performing what we denominate as an *information-guided planning process*, the algorithm, which incorporates a novel I-UCB function, shows significant improvements in reward and reasoning time compared to state-of-the-art baselines in several benchmark scenarios, along with theoretical convergence guarantees.

Information-guider Planning: An Online Approach for Partially Observable Problems
Matheus Aparecido do Carmo Alves Lancaster University
Amokh Varma Indian Institute of Technology Delhi, India
Lancaster, United Kingdom
a. ves.rrramaaee@@ ancaster. ac.uk uk
amokhvarma@@maill. com
Yehia Elkhatib
Leandro Soriano Marcolino
University of Glasgow
Lancaster University
Glasgow, United Kingdom
Lancaster, United Kingdom
yehia. ellkhatibeglasgoo..ce ac. uk
1. maaroolioo@lancateeee. ac uk
Abstract
This paper presents IB-POMCP, a novel algorithm for online planning under partial observability. Our approach enhances the decision-making process by using estimations of the world belief's entropy to guide a tree search process and surpass the limitations of planning in scenarios with sparse reward configurations. By performing what we denominate as an information-guuide plamning process, the algorithm, which incorporates a novel I-UCB function, shows significant improvements in reward and reasoning time compared to state-of-ther of-the-art baselines in several benchmark scenarios, along with theoretical convergence guarantees.
Introduction
Decision-makes making agents increasingly being used under uncertainty in nontrivial systems [77. Based on the available information, such agents must evaluate potential decisions in the current environment to build robust plan that either accomplishes the task leads to better situation. Consider, for instance, a scenario in which drones are deployed to rescue people in a hazardous environment. Drones need to quickly identify critical locations where they can offer support and save lives. If no clear target is found, they must rapidly formulate plan based on their current knowledge and observable information to find area in need of assistance from their current position.
The above context describes a partial observability problem that recurrent in the literature 2 The Partially Observable Monte-Carla Planning (POMCP) [32] algorithm is commonly suggested as a method to address these problems because it enables agents to perform planning in an online manner while handling uncertainty 6 36 38. However, several tfate-of-the-an solutions that rely on POMCP often struggle when rewards are delivered sparsely in time or outside their reasoning horizon. For example, in foraging, there may be clear target spot from the current observation and/or estimated map so far. Here, we find a fundamental academic challenge: How can we improve agent performance when rewards are delivered sparsely in time or out of their reasoning horizon?
Every time an agent makes an observation the world, it gains information that can be used to improve its internal planning process. Based on this, some works improve the traditional planning process by handling the lack of prior information using the approximation
the world's dynamic models [16 27]. embedding supportive planning methods within the tree 7 extracting non-explicit
information from the observations [6] [6), enhancing the method's inner calculations [ g 26 or
employing neural networks-based techniques improve the search quality [18 37
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Overall, these strategies can improve search quality within a defined simulation horizon by using extensions of traditional partially observable models and enabling the integration of additional knowledge into planning. However, such knowledge may not be available to agents beforehand (e.g.. conditional observation probabilities), or may demand significantly more computational resources to perform the task (e.g.. time and memory). While it is important to note that incorporating more knowledge benefits efficiency in terms of objective accomplishment, it does not resolve challenges in sparse-reward scenarios, as most of the solutions remain reward-driven.
Hence, we present Information -ased POMCP (IB-POMCP), an online planning algorithm that uses novel information framework to boost the decision decision-making process under partial observability even when no rewards are available in the reasoning horizon. Our framework refines the traditional UCBI action selection strategy by implementing our proposed Information guided UCB (I-UCB) function, which is capable of leveraging entropy and estimating information gain, using both real-world and internally generated observations to identify promising states in the search process that leads the agent to quickly accomplish its objective. Its application together with our new particle filter reinvigoration strategy, which considers the current system's 's entropy to calibrate the reinvigoration, indicates that this approach may lead the agent to act hybridly when solving a partially observable problem by better weighing the exploration, exploitation, and information levels within the tree. We ran experiments across five benchmarks and compared them with offte-o--thearr baselines, obtaining significantly higher average rewards (up to 10 times) while performing faster reasoning (up to 93%).
2 Related Work
In the current sate-of-thheant POMCP 32 remains a relevant solution due to its adaptability and problem-solving capability across the most diverse domains B 23 are tailored to specific problems, leaving room for improvement, especially when handling sparse reward scenarios. Our approach addresses this gap by shifting POMCP's weward-based planning to our cefffommation-guideee planning strategy", capable of leveraging observation space entropy (information) and guiding the agent promising spots from where it solves such scenarios.
24 41). However, many proposals
Other methods suggest approximating the latent world functions to handle the lack of knowledge [9 However, these approaches are directly bounded by the belief in space dimensionality, which grows exponentially and hence requires exponentially more resources as the complexity of the problem increases [17]. We propose the extraction of information using only the observations received from the simulations, improving the reasoning without requiring significantly more resources.
Some studies recommend belief-dependen POMDP models to improve POMCP's reasoning capa- bilities 44 21). Under certain assumptions, these models have shown great efficiency when solving problems with large action and observation spaces. A recent advancement is p-POMCP (36), an efficient online planner that boosts the POMCP's search process by estimating belief-dependent rewards. However, this method relies explicit access to the observation and transition function, struggling while reasoning under time constraints. TB p-POMCP (36) tries to handle scenarios with limited time to reason, penalising efficiency in order to do so. IB-POMCP can improve planning using less information and without significant penalties for reasoning time.
fime-constrained problems are prevalent in the evaluation of online planning algorithms. In real-time strategy games, a common strategy is to use macro and micro predefined coordination scripts to support the decision-making [25] 40 Even though they handle several levels of coordination, these methods still require behavioural templates to plan. Similar problems arise in the multi-agent swarm research (8 where they avoid developing a complex planning process in order to save time (using, for example, Flat Monte Carlo approaches). We propose the execution of efficient planning under partial observability from scratch and without penalising the planning quality.
The Upper Confidence Bound (UCB1) 20 a relevant algorithm in the literature for evaluating and selecting actions in online planning solutions and is recurrently used inside Monte-Caue -Call decision- making frameworks [5 29 35). While we acknowledge the existence of other action selection methods available in the literature, such as the Thompson Sampling method [3] and the PUCT algorithm 33), in this paper, we focus on augmenting the POMCP's capabilities by modifying the UCB1. Differently from PUCT (AlphaGo) [33], for example, our proposed I-UCB well-fits partially observable scenarios while enhancing POMCP planning capabilities through an entropy-based perspective, without relying on pre-trained models large amount of data.

---

Recently, MENTS and ANTS improved the Monte-Carlo Tree Search (MCTS) performance using maximum entropy policy optimisation networks [8] 37. In contrast to both works, we focus our study on partially observable models and, instead of directly optimising latent functions, we improve planning by emhedding knowledge into the search process. Furthermore, both methods rely on prior problem-specite
knowledge and data to train neural networks, including information on the maximum episode length, which helps them handle issues like sparse rewards. However, we assume that the agent must reason under a limited number of steps (often lower than necessary to accomplish the problem) and execute the problem from scratch, carrying no knowledge between executions.
Finally, although we focus on improving POMCP, our contributions can also benefit other algorithms, such as DESPOT-based solutions [34]. DESPOT's main focus is on filtering large observation space to plan using a sparse upproximation of the problem, hence, a smaller reasoning space. However, the algorithm still struggles large action spaces, and/or sparse reward scenarios where the optimal policy could be long (requiring many steps). Our proposal addresses POMDPs featuring sparse rewards an efficient manner while running the search process from scratch.
3 Background
Markovian Models - The Markov Decision Process (MDP) is a mathematical framework to model stochastic processes in discrete-time flow. The model specifies that each process is composed of a set of states S, a set of actions A, a reward function R. : S x A - R, and a transition function T. On the other hand, the Partially Observable MDP (POMDP) extends the MDP representation to problems in which the agent cannot directly access the current state. Instead, the agent receives an observation z Z. determined by observation probabilities Z = P = St+1 = s; 0, = a). The belief function B(h) is a distribution over the state space S, which describes the conditional probability of being in particular state b E S given the current history h, B(h, b) = P(s = b he). where the history h E H is a sequence of action-observattin pairs h₂ {ag. 2g.... . ae, 3 The decision process follows policy π (h, a) = P(a++1 = a a//h),, while choosing actions.
Monte-Carlo Tree Search (MCTS) MCTS algorithms aim determine the optimal action a" for a given state s by simulating the world steps within a tree structure. Each node in the Monte-Carlo tree T is represented by (s, V. .A) i.e., tuple with state 8, value V(s, a), and visitation count (sss a) for each action a E A. The value of the node represents the expected cumulative reward for the simulated states. The number of visits the state s is represented by (s) EnE A (ss a). The simulations are divided into two main stages: search and rollout. Each state in the search tree is viewed as a multi- armed bandit taking actions usually chosen by the Upper Confidence Bound (UCBI) I) algorithm. UCBI is keol- algorithm that tries to increase the value of less-explored actions by attaching a bonus inversely proportional the number of times each action is tried, following
[o)) The scalar cs the exploration constant responsible for weighting the exploration value within the UCBI function. With a correct definition of c, the value function converges in probability to the optimal value, V(s, & (s,a).
the equaten- UC a) == V(ss, a) + eV (s.a)
Partially Observable MC Planning (POMCP) - POMCP an extension of MCTS for partially observable problems. Analogously to it, each node is represented by a tuple (h, (1h). (N)h,, and the algorithm divided into the search and rollout stages. In contrast, POMCP uses an unweighted particle filter Fú. approximate the belief state at each node h. This strategy requires Monie- Carlo simulator G. which can sample a state 8', reward r and observation = given a state-action pair. Recursively down the tree, all sampled information is added to particle filter F. At the end of the search stage, the best action is chosen and a real observation is received from the environment. Considering the current particle reinvigorating process [32] which is responsible for updating and boosting the new root's particle filter belief state approximation. After that, we continue the planning procedure (starting the search process) as described above. We refer the reader to Silver and Veness 2010) for further detail.
pair, we move to the new root node and perform the
Shannon entropy in Information Theory A traditional approach to measure uncertainty in stochastic processes to use Shannon's 's Entropy function H(X) = - -E= P(a:) log( P(::)), where X is discrete random variable and v; are the possible outcomes from X. The core idea is to find a reliable measure for "information", ", that is, to calculate the degree of surprise of an event given the available space of possibilities. If an event often occurs, the information inside the event is likely
3

---

not "novel". Hence, there is no "surprise" when it occurs. On the other hand, if an event rarely occurs, the "surprise" is greater. Comparing both situations, we can follow events with higher surprise levels to explore the space of possibilittis, and safely follow events with lower surprise levels to exploit the environment, hence, we can adapt an agent's s behaviour according to the entropy of the current state.
Information--ased Partially Observable Monte Carlo Planning
Algorithm Outline Our algorithm starts with the (i) initialisation of our tree structure, where we create our root and calculate the probability of stepping into this node given our current knowledge. Since the initial knowledge about the problem assumed be none, we can not calculate this probability, hence, we initialise it as O. Subsequently, we (ii) initialise the particle filter of our root node, generating possible states from which we can simulate the agents' actions and search for solution to the target problem. Initially, the beliefs are generated through a uniform distribution.
where we sample state from our current belief to perform multiple rounds of simulation. However, unlike the typical approach, we propose the implementation of an adaptive exploration coefficient and of our novel I-UCB function instead of the usual UCB1. Therefore, at every iteration of our search (before starting simulation), we first perform our (iii) exploration coefficient adaptation, adjusting it using the entropy (level of information) estimated over the set of observations collected through the simulations. Then, with the updated coefficient in hands, we start our (iv) simulation with the I-UCB function. While choosing actions, our proposal searches for solutions and takes actions based on observations' entropy besides the collection of rewards. At the end of each simulation, we re-update the exploration coefficient based on the information gained during the path traversal. When we finish the search, we (v) select the best action based on the estimated rewards, entropy, and the number of visits of each action's 's node to determine the most promising path to follow in the real environment.
Our search process is iterative, commonly found in the literature 33 39 2].
After taking an action and receiving a new real observation from the environment, restart the IB-POMCP algorithm. However, the initial steps are slightly changed to maintain the knowledge and update the current information, i.e., perform online planning. Unlike the first iteration, now (i) update the rool node by traversing the tree based on the action taken and the most recent observation from the environment. Consequently, we recalculate the probability of stepping into the new root node using the information available in the tree. With the probability in our hands, we now (ii) update the particle filter of our root node by reinvigorating our belief, generating new states using the uniform distribution while maintaining promising states for simulation. Then, after performing these updates, we restart the search and repeat the whole process. Now, let us discuss these steps in detail.
(i) Root Initialisation and Update - This step is responsible for maintaining the tree structure coherent with the world and the information gained while performing online planning. Consider as the tree T's root node, h2 as the history of the root (our current history), a as the action taken by the agent in the real world and z as the most recent observation received from the real world (after the agent's 's action). As in POMCP, this step considers three possible procedures:
i does not exist, we create root node t using the current history his else; Update: if T exists and the nodes h,a and hęaz also exist, we walk in the existing tree, traversing the nodes that correspond to the actions taken by the agent and the most recent world observation 2, and update the root, i.c., the node haaz becomes the new v, hence, h = h-az, clse;
Initialisation:
Re-initialisation: T exists but, node hęa hçaz does not exist, the tree is re-initialised. That is, we create a new node (h, V(h),N ,N(h),, with as the current history, Vhh) = 0, (h) = 0 and Fú is empty. Afterwards, simulations already made in the agent's head are discarded and we restart the algorithm.
assign this new node our new root of T, which means that all other
In contrast to POMCP, we estimate the current probability P(=lhra), in this step, when finding the observation z after taking the action a considering our history hr. Overall, we aim to use this probability to enhance the Particle Filter Update (see step (ii) procedure by weighting its diversification and reinvigoration levels according to the agent's 's uncertainty when stepping into the new root which would be the same calculating the agent's "surprise" on finding the received observation in the real world after taking the chosen action. However, we consider that a compact representation of transition T or observation probabilities Z may not be available for complex problems. Hence, we propose the approximation of this probability using the knowledge within our A((haaz) particle filter F. (without requiring POMDP explicit model) by P(zlhaa) ~ P(z(hea) = "V(haa)

---

where (h,az) and N (haaa are the number of visits of node h,az and h,a, respectively (the new root node and its parent). If he is empty no new root node is found, P(z]hea) = 0. Note also that ((haz) & (ha), wh E 'T and, consequently. ([[aa))/(((a)) E [0, 1].
(ii) Particle Filter Initialisation and Update- This process is responsible for initialising the particle filter of the root node F, (if it empty or does not exist) or performing the particle reinvigoration process based on the probability P(z)(b,a) calculated in the Root Update process (step (i)). Directly, the initialisation is made through the sampling of k particles (which generate the observation z) from the uniform distribution Ug On the other hand, the update considers the P(=lhta) as the weight that balances the particle reinvigorating process over F... The idea is diversify (or boost) the new root's particle filter as reliable approximation of the belief state function. If the probability of stepping into this new root is high, i.c., P(z h,,a) is high, we assume that the particles in the new root's particle filter will well approximate the real world, since through the simulations we recurrently found the observation 2 after taking the action a from the last root node h. In contrast, when this probability is low, we diversify the new root's particle filter Fr by uniformly generating particles that may better represent the real world using U₂ instead of Fr. Consequently, coherent with the above rationale, we reinvigorate the new root's particle filter F. by maintaining L (==haaa)))] particles sampled from itself, i.e., Fras. and sampling new [6[1 P(=[h,a)) particles from the uniform distribution Ug. This update on the new root's particle filter may offer a better start for the algorithm when performing the search process since the sampling of belief states may consider enhanced set of particles through our uncertainty- guided reinvigoration process. We kindly refer the reader to Appendix A for further diseussion and pseudo-code to implement this procedure.
(iii) Updating the Tree Exploration Coefficient - To explain how we update our tree exploration coefficient, we first introduce the (a) adaptation made to the traditional exploration coefficient, then we present our (b) modified entropy function, which is used in the update, we explain how to calculate it and, in the end, we show our (c) strategy to normalise the entropy in the online planning context.
(a) Exploration Coefficient Adaptation Before the actual tree simulation process, IB-POMCP first adjusts the value of our tree's 's exploration parameter based on the estimated entropy for the current system (the tree) in the root level with history h,- Directly, our approach considers the replacement of the traditional constant by the function (1 - ahh))) E [0, 1], which we define as:
(hh.)= = e eln(A(hh) EN (h,)))
((hh)) (hh max=1
N(.)) H.(h))
Our insight is to use a to augment the current uncertainty level in the tree's search policy. On the left-hand side of the multiplication, we design a function that represents the chance of finding new information by exploring a node. which decreases as the number of visits to the node increases. e is the Euler's constant, which will be used as our amortisation factor for (n(N(h.)) (b,)))/(h,,) Applying both together, we can describe a function that slowly decreases and maintains, in the infinity and under some assumptions, theoretical guarantees for belief approximation (see Section 55). The right- hand side of the multiplication expresses the "general surprise trend", which is calculated through
the division between the actual cumulative entropy Ex(hh) Hhe) and the estimated maximum
cumulative entropy (h+) max 1=1 (h,,) (he), which is the multiplication of the total number of visits to the node and the maximum entropy. By multiplying both sides of the equation. we can estimate the current uncertainty of our system, in this case, of our tree. In addition to improving reasoning, we discard the need for prior knowledge about the problem of adjusting and fixing the tree constant c. Note that we adjust (h,,)) for each traversal on the tree, i.e., from the root t to some leaf.
(b) Entropy Calculation We adapt Shannon's 's Entropy equation to measure the level of information in the IB-POMCP's search process based on the collection of observations of our agent while performing Simulations (see step (iv)), which is designed as H(h) = E.ez (z( (z)),, where (x()) is the probability of finding the observation 2 E 2 by simulating actions from the node with history h. We use 2, which is an estimated set of observations, in the calculation of the entropy because we consider that compact representation of the full observations space Z may not be available.
In order to build Ž as reliable estimation of Z, we collect all the observations found during all traversals within the tree and save them first as the multisel 7m avoiding losing information, e.g., the frequency of the observations and then we translate it the set Z when necessary.
5

---

Each node has its own estimated multiset of observation Z Every time we visit a node h, we update the z using the collected observation information, which is saved and pack-propagated as Z On the other hand, Z is the multiset that saves the observations from a single traversal starting from the node at the tree level t to the maximum length of the path D. Therefore, each node h has its own multiset that saves all possible observations to be found by performing a simulation from it. Formally, we can define Z = U (h) " where Z is the back propaaroe Z," at i-th visit to the node, and ZV; 1 U 24, Vt = 0, 1, ..., D. Note that Z 0, Vt > D. Let's put it as an example:
Consider = ho as the root node, D = and a single traversal in the tree. Under the back- propagation perspective, we start our update from the last node visited, related to 2 Following our definition, - = {2443} ) and, since it is a leaf node, only 2++3 will be included in 2 as new possible observation to be found from node hg. Now, in 2g we will add the 2t+2 to our back- propagation multiset 7 and, consequently, we will add {#1+3; #e+22 } to h2 We repeat this process
until we reach ho. where we include all found observations 2.TT Zift U {za, 22, 21, 203 the root multiset 2n Figure illustrates this example and our proposed observation back- propaaaaoaatio procedure. Figures la and id present high-level perspective of the process, showing only the observation nodes of the tree to facilitate visualisation. Figures [c
a closer perspective of the process as a one-step execution. The red particles are states and the blue ones are observations.
he
No
2
US
2
Obec. Rev3
hgf
has
Fine
2
Flom
Ziis
{m
2
(a) Simulation procedure from (b) One-step simulation
(c) One-step back- propagation (BP)
(d) BP through the observation nodes of the tree
a high-level perspective
Figure 1: Illustration of IB-POMCP's search process.
With Z in hands, we now can approximate (z( by calculating the frequency of the observation in Z following (2) ~ (z())) प.. Exegy [(>'==)- Therefore, our final entropy function (m)))((P(())). We use this defined entropy to calculate the current entropy of the system. However, since IB-POMCP plans in online manner and the ž is updated at each visit to the node, we propose the estimation of our tree's 's entropy using the update-equation:
will be H(hh- = - E.eg
Haraj (h) = Hlv()-1(h)+ (H())) (h)))-(())
A(hh)
where N(h) is the number of visits the node h, H(h) is the above defined entropy calculation. and H4, (h), i = 1,2....V(A) is the estimated entropy at the visit i. Note that, by following this final definition for the entropy, we can also calculate a (Equation [ and update it in an online fashion.
(c) Entropy Normalisation Another issue that arises is that, since we may not have access to the true observation distribution in advance, our current approach will result in entropy calculations that are not standardised under the same image function. This problem occurs because the size of the set Ż grows every time an observation never found before is delivered by the environment. As a consequence, the maximum value for the entropy also grows, and nodes that receive higher number of different observations will calculate higher values for H(h), which can create bias by including these overestimated values in the decision-making process. Therefore, we propose its normalisation posteriori, following: (h) :=
(hrra(h)) where (h) represents the entropy calculated at the
max, 200 (A))))
j-th visit to the node h. This approach guarantees (k( E [0, 1], Vh, i.c., for all nodes. Moreover,

---

H((h) = 1 when (h)) = 0 by definition, since we consider that when there is no information, the uncertainty is maximised, hence, the entropy is also maximised.
(iv) Simulation After adjusting our a function, we start the simulation process. While expanding the tree, propose modified version of UCB1 to guide the tree search process based the information level of each node, the I-UCB function, which follows:
I-UCB(h, a, V(ha) (1- (n())//(((NN))NNNN)) + (ha)
(3)
Our proposal intends to guide the expansion and planning process based on entropy updates that occur within the tree, defining what we denote as the informatiionguddel planning process. In this type of planning, a trade-off between exploration and exploitation still exists, but now we also bring information value to the discussion, Our main novelty here moves past the traditional idea, where the more we explore, the better we can exploit the rewards, thereby improving the agent's s performance. Instead, we expand the discussion and enhance the algorithm capabilities by introducing an information-gail perspective to the tree-planning process using entropy calculations.
Intuitively, our action selection function considers that (a) if the system uncertainty is high (hence, a value is high), we weight the action selection based on the advantage of information gain (which may expand the tree in depth). trying to decrease the entropy value and accumulate knowledge, or; (b) if the system uncertainty is low (hence, a value is low), we weight the action selection in the advantage of the exploration gain (which may expand the tree in breadth), trying to increase the entropy value and increase the number of possibilities to reason over. Therefore, I-UCB performs adaptive planning that also depends on the system entropy, besides the upper confidence estimations.
Another direct advantage of the application of I-UCB instead of UCBI is that our method rarely fails to deliver an action justified by metrics, that is. rarely delivers a randomly chosen action as the best one. Usually, this issue arises in problems where rewards are sparsely distributed over a long horizon of actions, which can lead to several ties in the Q-values (e.g., at zero). Proposing solution that works under these conditions requires (a) to increase the reasoning horizon of the solution, which usually leads to the expenditure of significantly more computational resources, or (b) the capability to handle it within the available reasoning horizon, which is non-trivial task. IB-POMCP solves this problem by following a non-trivial solution considering (a) the inclusion of a novel metric for evaluation the system entropy, which frequently is non-zero since the observation distribution is diverse and: (b) the adaptive value of alpha, which often promotes an action branch to find (at least) a non-zero value (reward or entropy) or to be frequently visited during the reasoning process.
(v) Best action selection we decide the best action by picking the action with the highest score using Obest = argmaa..e (1 (ha) + (ha)). there a tie, we break it using the number of visits for each possible node. If it persists, we run random policy to select the "best" action. Because of the proposed entropy calculation (and in contrast to POMCP), IB-POMCP has the ability to choose actions even without experiencing non-zero rewards while planning.
Lastly, considering the above discussion on adapting and inserting a inside I-UCB, consider scaling a value to be within an interval [4, 1- q] x] C [0. 1]. 0 < < 0.5, as a practical enhancement. This strategy allows our method to avoid ignoring part of the I-UCB result by multiplying one term by zero. This step will not be considered in the theoretical analysis.
Sgpoithmm/sseud-ccode To highlight the difference between POMCP and IB-POMCP, present the complete pseudocode of our algorithm in Appendix
5 Theoretical Analysis
In this section, we analyse IB-POMCP's capability to plan optimally in partially observable finite horizon problems and e-optimally for infinite horizon partially observable problems. For the complete proofs see Appendix B
We start with the following assumption:
Assumption Given a generic POMDP represented by the tuple (S, R, T, H. the R is bounded and there exists a positive maximum reward value Tmaa E R.
'BB POMCP's implementation publicly available GitHub: http:///gittbbccommmmmooaaaaaaap
7

---

Under this simple assumption and to establish the IB IB-POMCP's planning capabilities, we must examine our action selection procedure, specifically through the application I-UCB, Consequently, we first analyse how the a coefficient behaves and impacts the IB- IB-POMCP's search process:
Lemma (c(h) E [0, 1] converges to O as the number of visits (h) approach the infinity.
Theorem For any non-empty history h + 0 E H and Va E A, as Nh)) - co. N(ha) - co, we have that all states b in B(h, b) which P(s = b h) > 0 will be simulated infinitely many times.
Using the previous results, we can show the convergence for a finite horizon:
Theorem IB-POMCP's nodes converge to the optimal value for a fixed horizon D as the number of search iterations goes to infinite (i.e. (h+,) + oo).
We now move on to the infinite horizon case. Consider (he) as the optimal value function for the root and VL (h+) as the optimal value function for the root for finite horizon D. We find that:
Theorem 3 Given any there is finite horizon D the problem, such that (V* (h+) (1h+)-V/ VD (h+) where by represents the root of the tree.
Given the previous results, prove the following for the convergence in the infinite horizon:
Corollary IB-POMCP converges to c-optimal actions at the root (h+) in y-discounted infinite horizon scenario.
Results
Evaluation Settings We define five well-known domains as our benchmarks. See Appendix C for more information. (i) The Tiger (TO) environment presents an agent must choose between two doors: one hides treasure; the other, a liger. The agent can decide which door to open or listen to before making the final decision. (ii) The Maze (M0-M3) environment [3), which is an Active Localisation Problem in which an agent navigates through toroidal grid and tries to localise its own position by collecting local information. The reward is based on the entropy of the current belief. (iii) The RockSample (R0-R3) problem (3) considers that a robot has navigate through grid- world and maximise the number of good rocks it picks up and analyses instead of bad rocks. If it picks up (samples) bad rock, it gets negative reward. Otherwise, it gets positive reward and the good rock becomes bad. (iv) The Tag/LaserTaag (LTO-LTI) environment [34], where an agent is trying to find and tag targel opponent agent that intentionally moves away. The agent only knows its own position but can observe the target's position they are in the same position (Tag) or using an 8-directional laser (in LaserTag) If the agent successfully tags the target it is rewarded, otherwise it is penalised. (v) The Foraging (FO-F4) problem is a famous scenario to evaluate online planning algorithms 2 30 that presents an agent that collects items displaced in rectangular grid world. All experiments were implemented using AdLeap-MAS (9] because it implements all five environ- ments and enables the quick execution of our experiments. Each run was performed in a single node of performmeee cluster containing 16 cores of Intel Ivy Bridge processors and 64 GB RAM.
Baselines In this work, we compare IB-POMCP against: (a) POMCP 322 since it is relevant state-of-art proposal and represents the basis of this work; (b) p-POMCP 36 representing our main competitor in terms of using information theory to perform the online planning procedure, and (c) TB POPOC 36 as a faster alternative to P-PMMCP that employs an explicit POMDP model.
Metrics Two different evaluation metrics were used: (i) the average reward (R) across the experiment's 's mean reward; and (ii) the average planning time (t) spent by the agent to plan the next actions. Mean results were calculated across 50 executions. Every experiment ran independently; thus, no knowledge was carried from one execution to another. The calculated errors ErEr represent the 95% confidence interval of two-sample t-test. Note that results and baselines separated into two categories (i) Quick Planning: grouping methods that perform the decision decision-making process within reasonable time window; and (ii) Long Planning: presenting the P-POMSP's results (without time constraints). We separated them to make their understanding easier.
Finally, we refer the reader to Appendix D to information about our hyperparameters set.
8

---

Benchmarks study - All results are presented in Table ! of our method, analysing our limitations while discussing the outcome for each environment.
In addition, we highlight the pros and cons
Table I: Summarized results. The bold underlined values in Quick Planning highlight the best result with statistical significance across all Quick Planning baselines for the respective metric.
Quick Plansing
Long Planaing
POMCP
POMMUP
PEFOMCP
(-POMCP
Problem
R Ere
Err (500)
Err
Err
(sec)
(seC)
(sec)
Tiger (TO)
-4.25 10a
0.00 0.01
-0.16 x 1
0.20 1 0.00
-0.52 x 10a
0.11 0.01
-0.21
10
1:45 1 0.01
+0.15
+0.03
MazeCross (MO)
1.11 x 10-2
2.47 0.02
1.12 x 10
3,00 = 0.00
1:23 x 10
2:43 0.01
1.19
10
26.16 0.05
+0.08 x 10-2
+0.07 x 10
+0.04 10
+0.07 10
MazeHoles (MI)
1.58% x 10
3.72 + 0.00
1.32 10
4.00 0.00
3.80
3.60 +
48.41 2.82
+0.50 10-2
+0.46
10-2
+0.86
+0.44
ManeDois (M2)
1.20 x 10
2.59 1. 0,02
0.79 x 10
3.00 1 0.00
2.99 x 10
2.55 0.02
1.25
10
36,71 1.39
10.28 x 10-2
10.15 x 10-2
10.85 10
1:0:20 10-2
MazeGridX (M3)
0.99
0.32
10 80 10
10.15 x 10-2
10.02 10
10:30
1002
RockSample22 (KO)
0.06 x 10
2.08 d: 0.03
0.03 x 10
=: 0.00
0.07 10
2.33 0.01
0.00 10
2,70 0.43
10.01 x 10
10.01 10
10.01 10-1
10.01 10-1
RockSampls40 (RI)
x.12 10"1
2.08 0.03
0.11
0.16
2.40
2.77 0.32
#0.01 x 10-1
20.02 x 10
20.01 x 10
10.01
10
RockSamplo44 (R2)
0.07 x 10
4.67 + 0.00
0.06 x 10
5.00 + 0.000
0.09 10
5.10 6.10+00.00 0.06
0.04 10
23.18 3.10
10
10.01
10.00
RoekSample17 (R3)
-0.04 x 10
4.72 +
00.06 x
5.00 0.00
0.00
5:11 0.05
-0.00
10
25.40 3,28
10.02 x 10"1
10.02 x 10
10.01
10
10.00
10
Tog (LTO)
-0.47% x 10-1
1,22 0.20
-0.65 10
3.00 1 0.00
-0.56 10
0. 0.86.10.14
-0.65
10-1
11:23 1.52
x 10-1
10.09
10.10
LaserTag (LT))
-0.90 x 10-1
4.72 1. 0.08
-0.88 x 10
3.00 1 0.00
-0.92
10
5.11 1 0.06
-0.96
10
19:11 1.02
#0.06 x 10-1
#0,09 x 10
+0,06 x 10
+0.51
10
TheCoridor (FO)
1.29 x 10
0.96 1: 0.06
4,36
10
1.00 0.00
6.89
0.87 1 0.10
5.15 10-2
6,18
+0.51 x
+0.38
+0,28
+0.18
10
U-staped (F1)
0.70 x 10"
3.67 #: 0.02
0.53 x 10
3.00 :: 0.00
5.10 x 10
2 2.00 0.1.9
5.30
10-2
37.36 1.29
+0.34 x 10-2
+0.03 x 10
+0.14 10
+0.31
10
U-obstacles
1.17 x
1.67
5.50
1,88 0.08
0.37
+0.34 x 10-2
+0.23 x 10
+0.34 10
+0:45
10-2
Warchouse (F3)
5.20 x 10-2
3.02 1 0.11
4.42 x 10
3.00 0.00
10.73 x 10
2.91 0.225
8.59
10
20,00 0.67
10:45 x 10-2
1:100 x 10-2
10.41 10
1.0.96
10-2
TheOffice (F4)
0.43 x
0.72 10
0.00
2.34
1.88 0.08
10-3
15:44 0.37
10.21 x 10-2
10.11 x 10
10.27
10
100.17
10
In the Tiger domain, TB p-POMCP presents the best average reward among the Quick Planning methods (p < 0.01). IB-POMCP still outperforms POMCP, showing significant improvement in terms of reward (p- < 0.01). For this specific problem, since the action "listen" generates variation in the entropy, IB-POMCP keeps performing it repeatedly until other action value outcomes the "listen" value in the best action selection procedure (Section 4 step (v)), a circumstance which leads our method to reduce its average reward collection. Hence, when facing problems where seeking spots of high uncertainty produces small penalties, IB-POMCP may collect penalties until it significantly decreases the uncertainty and chooses another path.
In the Maze domain, we observe that IB-POMCP presents a significantly better average reward in out of 4 proposed scenarios (p S. 0.015), except for M3, for which POMCP presents a better result. Note that reducing uncertainty leads to increasing reward; i.c. the faster an agent can access areas with high uncertainty, the higher its received reward. IB-POMCP's results match our expectations (given the developed rationale throughout our methodology) since we build it to, besides tracking the rewards available in the scenario, often seek paths that lead to spots with high entropy in order to decrease uncertainty, what increases reward in this scenario. In terms of time, we present significantly faster reasoning in all scenarios (p 0.01). Investigating why IB-POMCP runs faster than POMCP, we found that our eeormatiionguudeer planning leads the algorithm to perform more transitions during the rollout phase than while performing the simulation inside our actual search tree, with rate #roliout #simulation 1.61, whereas POMCP presents a rate of 1.28. Because rollout transitions run faster than simulation transitions inside the tree, we can save time by performing them frequently.
In the Rock Sample problem, we can see that IB-POMCP shows a significant improvement in terms of reward collection (p Σ 0.02) in 3 out of 4 scenarios except for the simplest scenario RockSample22 (RO), which presents a p-value of p < 0.11. In terms of reasoning time, POMCP is slightly faster than all Quick Planning methods in 3 out of 4 scenarios (p 0.01), except for RockSample17 (R3).
In Tag, IB-POMCP presents significant improvement terms of reward collection and reasoning time against all baselines (p < 0.04). As in the Maze, we believe that IB IB-POMCP is faster because it simulates transitions in rollouts more often (in ratio of #rollout
1.7 against 1.61 for POMCP).
#simulation

---

In LaserTag, we have a tie between all methods, with no statistically significant difference spotted across metries (p 0.32 for reward collection and p 2 0.06 for reasoning time).
Finally, in the Foraging domain, our proposed method significantly outperformed all the baselines (p 0.01). The Foraging problem represents most complex scenario, and empirically shows how IB-POMCP can overcome the necessity of adjusting the reasoning horizon to perform planning in settings that deliver rewards sparsely. The only reward available in these scenarios comes from the collection of tasks. Consequently, while attempting to solve task, the number of actions that the agent needs to plan and execute in sequence may approach or exceed the reasoning horizon size. In this case, the probability of experiencing this reward is low, and algorithms that only follow the reward in planning will rarely obtain it in their simulations; hence, they fail to plan effectively.
Overall, we experimentally demonstrated that our novel proposed method can significantly improve the performance of our agent and its planning capabilities without penalising the reasoning time. We also demonstrated that our proposal can improve the decision- process by using only the information generated during the tree search process and, in contrast to p-POMCP, without relying on the explicit representation of latent functions (c.g., the observation function).
Ablation study To evaluate the impact of our proposed modifications and enhancements, performed an ablation study over our method. We consider 2 different variations of IB-POMCP that partially implement its key points in this experiment: (a) the Information-guided Particle Reinvigoration POMCP (IPR-POMCP), which implements the modifications to the particle filter reinvigoration process (explained in Section 4 steps (i) and (ii)); and (b) the I-UCB POMCP, which implements the proposed modifications to the search and simulation process (explained in Section 4 steps (iii) and (iv)). We consider 4 different scenarios, one for each environment presented in Table T to run our experiments. The results are depicted in Figure Both additional methods proposed for the study are available in our repostorry together with the complete code of this work.
Tiger (TO)
(b) MazeDots (M2)
(c) U-obstacles (F2)
(d) TheOffice (F4)
Cumulative Reward
PONEP POMER UCB-FOMCT
8 10 2
on
Reration
Itaration
Iteration
Figure 2: Ablation study of IB-POMCP in four different scenarios.
By analysing the graphs, it is clear that the I-UCB and implementation of information -oniidd particle reinvigoration process for the Tiger. Maze, and Foraging problems directly enhance the reasoning capabilities of our planning method, which is translated here in terms of reward collection. For the Tiger and Foraging problems, diversifying the set of particles (I-UCB POMCP) alone presents improvements for POMCP; however, it has less impact than including entropy in the search process (IPR- POMCP) On the other hand, in the Maze environment, both approaches present similar improvements for the POMCP algorithm. However, when combined, they significantly improved upon the baseline results. Our intuition behind these results is that the IPR-POMCP proposal is responsible for delivering better set of particles and better initial estimation of the current state to the agent before simulating actions, whereas I-UCB continually guides and affects the planning process from the beginning of the simulations until the decision of the best action.
Conclusion
In this study, we propose IB-POMCP, novel algorithm for planning under uncertainty that is capable of aggregating information entropy into a decision-making algorithm using our modified version of the UCB function, J-UCB. We present the theoretical properties for convergence under certain assumptions, which are supported by empirical results collected in five different domains. Overall, we increase the reward collection by up to 10 times in comparison with TB p-POMCP (U-shaped, FI), in addition to reducing the reasoning time by up 93% compared to p-POMCP (MazeHoles).
10

---

Acknowledgments and Disclosure of Funding
We gratefully acknowledge the financial support provided by PhD studentship from the Faculty of Science and Technology (FST) at Lancaster University, United Kingdom. We also thank FST for granting us access their High-End Computing Cluster (HEC 3.0), which was pivotal this research. We extend our sincere gratitude to Dr Mike Pacey for his expertise and assistance provided correctly setting up HEC 3.0 and running our experiments. Our special thanks go to Dr Ronghui Mu for providing insightful comments and feedback on an earlier draft of this paper.
References
[1] D. Agudelo-Españha S. Gomez-Gonzalez, S. Bauer, B. Schölkopf, and J. Peters. Bayesian online prediction of change points. In Conference on Uncertainly Artificial Intelligence, pages 320-329. PMLR, 2020.
[2] S. V. Albrecht and P. Stone. Reasoning about hypothetical agent behaviours and their parameters. In Proceedings of the 16th Conference on Autonomous Agents and MultiA gent Systems, AAMAS '17, page 547-555, Richland, SC, 2017. International Foundation for Autonomous Agents and Multiagent Systems.
[3] Amini, M. Palhang, and Mozayani. POMCP-based decentralized spatial task allocation algorithms for partially observable environments. Applied Intelligence, 12(10):12133-2260 2023.
[4] M. Araya, O. Buffet, V. Thomas, and Charpillet. A POMDP extension with belief-dependent rewards. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23, 2010.
[5] A. Bai, F. Wu, 7. Zhang, and Chen. Thompson sampling based monte-carlo planning in POMDPs. In International Conference on Automated Planning and Scheduling (ICAPS), page 29-37. AAAI Press, 2014. ISBN 9781577356608.
[6] A. Baisero and C. Amato. Unbiased asymmetric reinforcement learning under partial observ- ability. In International Conference Autonomous Agents and Multiagent Systems (AAMAS), pages 44-52, 2022.
[7] S. Barrett, A. Rosenfeld, S. Kraus, and P. Stone. Making friends on the fly: Cooperating with new teammates. Artificial Intelligence, 242:132-171 2017.
[8] S. R. Chowdhury, R. Oliveira, and F. Ramos. Active learning of conditional mean embeddings via bayesian optimisation. In Conference on Uncertainty in Artificial Intelligence, pages 1119-1128, PMLR, 2020.
[9] M. A. do Carmo Alves, A. Varma, Y. Elkhatib, and I.. Soriano Marcolino. AdLeaa-MAS: An open-source multi-agent simulator for ad-hoc reasoning. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1893-1895, 2022.
[10] D. Fox. Adapting the sample size in particle filters through kid-sampling. The international Journal of robotics research. 22(12):985-100) 2003.
[11] M. Ghavamzadeh, S. Mannor, J. Pineau, A. Tamar, et al. Bayesian reinforcement learning: A survey, Foundations and Trends in Machine Learning, 8(5-6):359 483, 2015.
[12] M. Gini Multi-robot allocation of tasks with temporal and ordering constraints. In AAAI Conference on Artificial Intelligence, 2017.
[13] A. Guez, D. Silver, and P. Dayan. Efficient Bayes-adaptive reinforcement learning using sample-based search. International Conference on Neural Information Processing Systems, 25, 2012.
[14] A. Hayashi, D. Ruiken, T. Hasegawa, and C. Goerick. Reasoning about uncertain parameters and agent behaviors through encoded experiences and belief planning. Artif. Intell., 280(C), Mar. 2020. ISSN 0004-3702.

---

[15] M. Hoerger and H. Kurniawati. An on-line POMDP solver for continuous observation spaces. In International Conference on Robotics and Automation (ICRA), pages 7649. IEEE, 2021.
[16] S. Katt, F, A. Oliehoek, and C. Amato. Learning in POMDPs with Monte Carlo Tree Search. In International Conference on Machine Learning (ICML), pages 1819-1827, 2017.
[17] S. Katt, F. A. Oliehock, and C. Amato. Bayesian Reinforcement Learning in Factored POMDPs. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2019.
[18] P. Kozakowski, M. Pacek, and P. Miloš. Planning and learning using adaptive entropy tree search. In International Joint Conference on Neural Networks (IJCNN). IEEE, 2022.
[19] H. Kurniawati, D. Hsu, and W. S. Lee. SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Robotics: Science and systems, 2008.
[20] T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22 22, 1985. ISSN 0196-8858.
[21] M. Lauri and R. Ritala. Planning for robotic exploration based on forward simulation. Robotics and Autonomous Systems, 83:15-31, 2016.
[22] L. Marcolino and L. Chaimowiez. No robot left behind: Coordination to overcome local minima in swarm navigation. In International Conference on Robotics and Automation (ICRA), pages 1904-1909. IEEE, 2008
[23] G. Mazzi, D. Meli, A. Castellini, and A. Farinelli. Learning logic specifications for soft policy guidance in POMCP. arXiv preprint arXiv:2303.08 172, 2023.
[24] J. Mern, A. Yildiz, Z. Sunberg, T. Mukerji, and M. J. Kochenderfer. Bayesian optimized Monte Carlo planning. In AAAI Conference on Artificial Intelligence, volume 35. No. 13, pages 11880-11887, 2021.
[25] R. O. Moraes, J. R. Marino, I. H. Lelis, and M. A. Nascimento. Action abstractions for combinatorial multi-armed bandit tree search. Artificial Intelligence and Interactive Digital Entertainment Conference, 2018.
[26] L. Niss and Tewari. What you see may not be what you get: UCB bandit algorithms robust to e-contamination. In Conference on Uncertainty in Artificial Intelligence, pages 450-459, PMLR, 2020.
[27] G. Papoudakis, F. Christianos, and S. Albrecht. Agent modelling under partial observability for deep reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
[28] L.. Pelcner, S. Li, M. Aparecido Carmo Alves, L. Soriano Marcolino, and A. Collins. Real- time learning and planning in environments with swarms: A hierarchical and a parameter-based simulation approach. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), page 1019-1027, 2020.
[29] Riccio, Capobianco, and D. Nardi. Loop: Iterative learning for optimistic planning on robots. Robotics and Autonomous Systems, 136: 136:103693, 2021.
[30] E. Shafipour Yourdshahi, M. do Carmo Alves, A. Varma, L. Soriano Marcolino, Ueyama, and P. Angelov. On-line estimators for ad-hoe task execution: learning types and parameters of teammates for effective teamwork. Autonomous Agents and Multi-Agent Systems, 36(2):45, 2022.
[31] D. Shah, Q. Xie, and Z. Xu. Non-asymptotic analysis of Monte Carlo Abstracts of the SIGMETRICS/Peffoomacc Joint International Conference on Measurement and Modeling of Computer Systems, pages 31-32, 2020.
Tree Search. In
[32] D. Silver and Veness. Monte-carlo planning in large POMDPs. In Neural Information Processing Systems, pages 221222112,, 2010.
12

---

[33] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550
(7676):354-339, 2017. 2017.
[34] A. Somani, N. Ye, D. Hsu, and W. S. Lee. DESPOT: Online POMDP planning with regulariza- tion. Advances in neural information processing systems, 26, 2013.
[35] Z. N. Sunberg and M. J. Kochenderfer. Online algorithms for POMDPs with continuous state, action, and observation spaces. In International Conference on Automated Planning and Scheduling, 2018.
[36] V. Thomas, G. Hutin, and O. Buffet. Monte Carlo information-oriented planning. In European Conference On Artificial Antelligence, 2020.
[37] C. Xiao, Huang, Mei, D. Schuurmans, and M. Müller. Maximum entropy Monte-Carlo planning, Advances in Neural Information Processing Systems, 32, 2019.
[38] A. Yadav, R. Noothigattu, E. Rice, L. Onasch- Vera. L. Soriano Marcolino, and M. Tambe. Please be an influencer? contingency-wware influence maximization. International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), page 1423-1431, 2018.
[39] E. S. Yourdshahi, T. Pinder, G. Dhawan, L. S. Marcolino, and Angelov. Towards large scale ad-hoe teamwork. In International Conference on Agents (ICA), pages 44-49, IEEE, 2018.
[40] W. Zhou, B. Subagdja, A.-H. Tan, and D. W.-S. Ong. Hierarchical control of multi-agent rein- forcement learning team in real-time strategy (RTS) games. Expert Systems with Applications, 186:115707, 2021.
[41] M. Zuccotto, A. Castellini, and A. Farinelli. Learning state variable relationships for improving POMCP performance. In ACM/SIGAPP Symposium on Applied Computing (SAC), pages 739-747, 2022.
13

---

A Algorithms
In this section, we provide the pseudo-code of the particle filter update step (Algorithm D.. and for IB-POMCP's main routine (Algorithm 2 To clarify our approach better and support the text presented in the main paper. both algorithms highlight the differences between our approach and POMCP 32
See Section 3 in the main paper for further details about our rationale and methodology.
Algorithm 1 Particle Filter Update. The starred lines (with a light grey background) highlight the differences between POMCP and our proposal, IB-POMC, Union considers reperition here.
1: procedure PARTICLEPLLTERUPDATEEE
P(z]ha),A)
2:
B + Fr. Fr + 0
b B is a copy of Fe
*3:
while |F < P(zlhajkk do
*4:
b n~ L,, F
Adding P(z]ha)k particles to the new F,
*5:
while FF k do
*6:
Un Fr.Fr t FeUb
>> Adding (1 P(=[ha)) particles to the new F,
*7:
return F,
Algorithm]] [ Particle Filter Update- Details and Further Discussion: We save some space here with the intention of assuring the reader's understanding of the novelty that lies on our particle filter update proposal. Our method employs a dynamic threshold derived from the dynamic value of P(z]ha) (or specifically, 1 1-P particle filter). Unlike some traditional approaches which use a fixed value for that threshold, or some other state-of the contributions, which mostly rely on additional knowledge and expensive calculations [17 14 10, IB-POMCP does not need an explicit true distribution of observations, transition function or training data in this process by using our proposed P(z[he probability.
P( P(2)ha) that determines the ratio of uniform samples in the reinvigorated
It is important to note that the action selection process within the planning phase has direct impact on the P(=[hra) value. Therefore, the strategy used to choose actions for simulation during planning will affect the particle filter, since affects the dynamic threshold P())h,a). Hence, note that the I-UCB equation used in the search tree also has an impact on belief tracking.
Our suggested algorithm investigate the impact of this proposal (Ablation study in Section o IPR-POMCP, employs our dynamic threshold and shows significant improvement to the conventional POMCP, which follows a standard particle reinvigoration paradigm (with fixed parameter for reinvigoration). Hence, just using the dynamic threshold P(=)haa) improves results. Furthermore, the ablation study indicates that combining the dynamic threshold with the I-UCB equation yields more favourable results and that using solely the I-UCB equation without the dynamic threshold (IUCB-POMCP baseline) results in worse outcomes than the full IB-POMCP approach. Hence, both the dynamic threshold and the I-UCB equation important to improve results, and their simultaneous application produces even greater enhancements than when employed individually.
What is perhaps still left open is whether the I-UCB equation leads to better ((=)h,a) values than the UCB equation. Since our approach takes the estimated entropy into consideration for action selection we believe that I-UCB may lead to better threshold values.
For example, in cases where node possesses high entropy and no reward in the reasoning horizon, the I-UCB equation could prioritise visiting more often than the UCB equation would, increasing the P(z[hta) value for that particular node (note that it will not imply in worse probability estimation because the entropy is based on the estimation of observations and the particle filter gives the probabilities of states). The high entropy indicates that the node accommodates a more diverse set of particles in the particle filter and hence sampling particles from a uniform distribution during particle reinvigoration (to increase diversity) becomes less useful. Hence, the implications of the I-UCB equation appear favourable as it leads to fewer particle samples from the uniform distribution in this case (as we use the ratio P(z)hra)). On the other hand, if a node has low entropy, the particle filter may easily get biased to a small set of states. In this case, I-UCB would lead higher number of particles sampled from the uniform distribution than the UCB equation in the particle reinvigoration,
14

---

since it would have a lower P( haa)) value in I-UCB. Therefore, we believe that I-UCB should be better than UCB for defining the dynamic threshold P(z[haa), and hence better in belief tracking.
Algorithm IB- P8-POMCP's Planning. The starred lines in a light grey background highlight the difference between POMCP and our proposal. We suggest the reader to Silver and Veness (2010) [2] for further details. y is the historical discount factor, depthmas is the maximum depth for the tree, and 2/h represents the last observation found (associated with node ht)
1: procedure SEARCH(h:)
procedure SIMULATE(S, h, d, Q) 2: if < depthmas then
2: while T limeout() is False do
3: if F. then ~ Us
*3: return O, {
4: else Fr
4:
if é T then If node is not in the tree Expund Node(1i)
a: clu(N(he)) XNihe H4(h+) N(ha) N(hh))
"5:
5:
M0he
max Hithe)
return Rolloul (s, le, (z}
*6:
Simulate(s, Ne, 0,
t argmaz I-UCB(N,
"7:
return arg max (1- (1a) aeA
acA 2,)) G(s,a)
8:
*9:
r' 2741 - Simulate(s haz, 1,0)
1: procedure EXPAND (NDE(())))(
10:
Fr + Fr, U1$)
2: for A do
11:
((h) < <N(h))
T(ha) <- (ha, (ma(ha), Nincs(aa) 0)
12:
((ha) +- --((ha) +
13:
V(ha) V(ha) + R ((ha)ha)
N(ha)
1: procedure ROLLOUT(s, h, d,
H.(h) (Hi) (11(AA)
2: if < depthmuz then return 0
#14:
A(h)
3: 0 (ho
*15:
R +-r
4: 2,), ((),a)
*16:
2 t 2% UZZ
return "Rollout(s' haz, d + 1)
*17:
return R. Z,4
B Detailed Theoretical Analysis
In this section, offer comprehensive theoretical analysis of our proposed method. In addition to the assumption, lemma, theorems, and corollary presented the main paper, our complete analysis encompasses all proofs, along with definition (Definition 1) and lemma (Lemma 2).
Definition An estimated (s) is said to be c-optimal if (v(s) (*)) actions taken from the result of e-optimal value function estimations are known as e-optimal actions.
From the literature,
Assumption Given a generic POM DP represented by the tuple A, T, H,), the R is bounded and there exists a positive maximum reward value Tman E R.
Lemma a<h) [0, converges matically, lim a<h) 0.
the number of visits (h) approach the infinity. Mathe-
Proof: Considers equation for root node with history h:
((h) eIn(A(()) INO Hi(h)
N(h) ((h)maxX,(()
i=1
First, we can re-organise the equation as follows:
a(h) eln(N(h)) ΣVO Ha(h) eln(N(h)) ΣNTh H.(h)
N(h)
A( max H.(h)
N(O) N/(h22 max; H.(h)
Analysing the limit over the new expression, find that:
15

---

lim cln(N(h)) Σ Hi(h) 0
N N(h)
max;=1 Hi(h)
((h)
by following the rationale:
(1h) Hi(h)) S (h max Hh) 0 05 eln(N(())) ((h)) max Hi(h)
A(h))
N(h)²
max ((h)
(h)
Therefore, since we know that:
lim cl((N(h)) (h)) max; H.(h) ((h))
N(A)
N(h22 max; 1=1 Hi
(16)
cln()(h)) (())2
N(M) ((()) 0, by L'Hopital's Rule NNh))2
using the sandwich theorem, we find that (<hh) - 0 as (h)
Now, we introduce Lemma 2, which will be used as key result that supports Theorem 1. other words, will use Lemma 2's proof reach contradiction later in order to prove Theorem 1.
Lemma 2 Assume action a; that is taken finite number of times and aj that is taken infinitely dur- ing IB-P TB-POMCP's 's search for any node h. There 3 t" > t' such that I-UCB, (ha,) 2 1-UCB,' (ha,), where t' is finite iteration number after which 0g is never taken.
Proof: Let us assume that there exists iteration time & that is greater than l' where ag is never taken again for simulation. Consider the expression I-UCB, (ha:) (ha;), which is equal to:
I-UsB,(has) - -I-UCB((ha,) =
(haa)) - (((ag) +
[
(1 (1-o /N((ha;) (Ne(hay)
+ +a((h)
He(hay) - Hha(aa))
Trivially, (Nei)
(Nar) as NN(hha) -
since
(Nl(kag) 0 and
(h,,),
Na(ha)) will be constant under our assumption. Note also that (Ni(ha.) N4- After then (i.e. L (*),
(h,,), is increasing
and will become positive at some time 1" when No- (haj))
the term [In(N((h)]( [Ne(ha.) (Nilbar) ) will diverge to 00
co. oc, In(A(()))
Further, note that, in a single time step, the maximum difference in rewards is bounded by Tiaaz therefore V:(,);) (haa))
-Tmex I-- (This is because [baa)))) V:(ha;)] S T-y, as shown in Theorem 3 and this implies that -fmas S Ve(ha;) - Vi(hay) < T-2 and T-V
-h- T
Emas
or (FL (ha:)) 2 -1 as 0 S (h)) S and 0 s Hl) I 1. Therefore, 3t" where
I-UCB, (haz)) I-UCB, (hag) IV
O.
Theorem For any non-empty history h + 0
H and Va A, as (()) 0o, N(haa) oo, we have that all states b in B(h, b) which P(s = b h) > 0 will be visited infinitely many times.
Proof:
Let us assume that not all actions are taken infinitely many times. There must exist at least
one action E A that is taken finite number of times and, hence, 3 t' after which the action a, will never be taken. Now, consider any action a, that is taken infinitely many times as N(h) - so. In Lemma 2, we show that 3 t" >> l' such that:
I-UCB (ha.) > I-UCB,r (ha,,
16

---

We know that the second term in I-UCB grows faster for a, than aj, as seen from the I-UCB function, since (hh,) is constant for t > t'. Consequently, we reach a conclusion that is chosen over aj again after L'. This further means that for all actions os which a; is preferred over ag. Therefore, at some point, the action a, has to be chosen over all others. This is a contradiction our original claim. Therefore, all action E A are taken infinitely many times and, hence, all states will be visited infinitely many times.
find such finite time instant after
Theorem 2 IB-POMCP's nodes converge to the optimal value for fixed horizon D as the number of search iterations goes to infinite (i.e., (h,))) + oo).
Proof: We adapt the proof from the UCT convergence in Shah al. 2020 and POMCP convergence in Silver and Veness 2010 We induct over the depth of the tree, starting from the leaf up to the root. From Theorem 1, the leaf nodes will have an unbiased estimation of the expected reward rh = E (R(b, a)), Va E A. Note that we are using ri as the expected reward given h, which is different from an immediate reward r = R(b, a) given a state b. Similarly, any state at level D has simple UCB-liks problem since each state visited infinitely many times and the one-step rewards have an unbiased estimation. In detail, consider the leaves at level [h] = D, as (h,)) oo = NVhh) oc, + 0, and in the absence of children's entropy H (ha) (as it is the leaf node and has no children), r% converges unbiasedly V h E H. E A. Consequently, V(h) - V (h) since it single decision process, akin to multi-armed bandits. Now, we assume convergence for all levels from the leaves up to |h'l = |h| + 1, and as we know r% = =E.E P(st blh)rg. As we know, the value function satisfies:
V' (h)
max a
TA +
Σ
P(h+41 1 M,a; = ha))
From hypothesis, the v"(h') must converge and moreover, through the sampling process, the value function must converge for level |h| [32 Consequently, by backward induction, the whole tree's values must converge.
Theorem Given any (h+)) c, where h represents the root of the tree.
there is a finite horizon D for the problem, such that |V> (he)
Consider x" and TD to be the optimal policies for the infinite and finite horizon problem, respectively. Also, assume that e an arbitrary, positive real number. Now, let the value functions for these problems be y" (h,, and Vi (he). For the root t, we can find that:
Proof:
yP
(h+) - VD(h+)l <
Σ 7hh Traax
1 1-7 Tmar S C
k== 0
since calculate D = log,
<(1-2)
also ensure that the relation holds.
Tmaz
Corollary IB-POMCP converges to e-optimal actions at the root (he) in a d-discounted infinite horizon scenario.
From Theorem 6, we can always find depth D such that the value function of the finite- horizon problem arbitrarily close to the infinite-horizon problem. From Theorem 5, we know that converge the optimal value in finite horizon POMDP. Therefore, since 0 as (ha))) + oo, IB-POMCP will converge to optimal actions by choosing D appropriately.
Proof:
C Benchmark Domains and Scenarios
All environments used were obtained from the literature. The Tiger problem is well-known standard
problem (36). For the Maze domain, we based our design on Thomas et al. 2020 [36] For the RockSample problem, we designed our own scenarios but based the implementation on Thomas et al. 2020 36 For Tag and LaserTag, we used the scenarios proposed by /Soaaii al. 2013 For
Foraging 22. we proposed our own configurations for each scenario.
17

---

Tiger Environment: The Tiger problem is a classical benchmark where an agent must choose between two doors:
one hides a treasure; the other, a tiger. The objective find out which door hides the treasure. The agent can decide which door to open or wait and listen to the tiger (with certain probability of mishearing behind one the doors) before making the final decision.
The agent has a 15% probability of mishearing the tiger. A maximum of 20 actions are allowed per experiment. Choosing the right door gives the agent reward of +001,, the wrong door -1, and the listening action penalises the agent with -0.01 reward. Thus, each agent could try to listen to the tiger 19 times before making the final decision open either the left or right door.
This is an Active Localisation Problem where an agent navigates through a toroidal grid and tries to localise its own position by collecting information about its current position. The reward based on the entropy of the currett belief. There is a change of 15% to miss observe the colour of the cell. The belief follows Bayesian Update process. Figure | iilussrates the scenarios.
Maze Environment:
(a) Maze Cross This is 5x5 scenario in which black cells are positioned to ease the agent's localisation problem. Figure illustrates the scenario's configuration.
(b) Maze Holes - Thhis is an 8x8 scenario, which requires the agent to reason one step in advance to search for the missing black cell in this regular configuration. Figure [b illustrates the scenario.
(c) Maze Dots - This is 6x6 scenario, identical to Maze Hole except that black cells are separated by several white cells. I
illustrates the scenario.
(d) Maze Grid-X This is 3x3 scenario, with an upper white triangle and bottom black triangle for the localisation. Figure T icillustrates the scenario.
000
SN
boo
(a) Maze Cross.
(b) Maze Holes.
(c) Maze Dots.
(d) Maze Grid-X.
Figure 1: Maze environment scenario's configuration.
The context of this problem illustrates a rover exploring an unknown planet. The rover's objective is to earn rewards by both sampling rocks in the environment and leaving the planet with the samples. While the positions of the rover and the rocks are known, not all rocks hold scientific value, which are referred to as "good" rocks. Given the cost associated with rock sampling, the rover is equipped with a noisy long-range sensor, enabling to assess a rock's potential scientific value before deciding whether approach and sample it. The environment a grid map of size N x N with I rocks. The POMDP model for RockSSamle((N) (N,, k) follows: The state space is combination of k features, where Positions represent the rover's location {(1, 1), (1, .)... (N,N)) N)). and & binary features, RockT RockType;, ype;, indicating whether each rock is "Good" "Bad". There is terminal state (portal) the top-right corner of the map. The rover has choice of k + 5 actions: (North, South, East, Wesl, Sample, Check), Check,). The first four are deterministic single-step motion actions. The Sample action involves sampling the rock at the rover's current location. If the rock is determined to be "Good", the rover receives reward of +1, and the rock transitions "Bad". signifying no further benefit from sampling. If the rock is "Bad", penalty of -1 is delivered to the agent. Moving into the exit portal yields reward of +0.0001. All other actions have no associated cost or reward. Each Check; action employs the rover's 's long-range sensor to observe Rock, yielding noisy observation of either "Good" or "Bad". The noise the long-range sensor reading is influenced by the efficiency n. which decreases exponentially exp(-0.2 Fuclidean. SrniddeanDDstaaeeerroo probability of being "Good" or "Bad". Figure shows the four scenario configurations used.
RockSample Environment:
function of Euclidean distance from the target, following 1) Rock;)). Initially, every rock is assumed to have an equal
18

---

(a) RockSample22 - This scenario is set on a 5x5 grid, featuring 2 good rocks and 2 bad rocks. The rover initiates its mission from the middle of these rocks and must locate each specific good rock among the bad rocks. Figure 2a illustrates the scenario's configuration.
(b) RockSample40- - In this 5x5 scenario, there are 4 good rocks initially placed in the environ- ment, with no bad rocks present. In contrast RockSample22, the rover's goal here is to collect more rewards as there are more good rocks available. The rover starts its journey from the centre of these rocks. Figure 2b illustrates the scenario's configuration.
(c) RockSample44- This 10x 10 scenario features good rocks and bad rocks. The rover's starting point is the bottom-left corner of the map. Similar to RockSample22 but larger scale, the rover's challenge is locate each specific good rock among the bad rocks to optimize its reward. Figure 2 illustrates the scenario's s configuration.
(d) RockSample17 - In this 10x 10 scenario, there's ' only good rock and bad rocks, and the rover begins its journey in the bottom-left corner of map. Unlike RockSample44, the expectation here is for the rover to collect fewer rewards. However, if the rover finds the only good rock available, it can significantly improve performance terms of reward collection. 2 illlssttes the scenario's 's configuration.
Ooo
o0o
(a) RockSample22.
(b) RockSample40.
(c) RockSample44.
(d) RockSample
Figure 2: RockSample environment scenario's configuration.
Tag and LaserTag Environment: In the Tag scenario (Figure Baj. the agent's primary objective is to locate and tag target that actively moves away. Both the agent and the target navigate within grid featuring 29 possible positions. While the agent is aware of its own location, it can only observe the target's ' position when they occupy the same spot. The agent has the option either stay in its current position move to any of the four adjacent positions, incurring cost of -0.1 for each move. Additionally, it can opt to execute the tag action, wherein receives a reward ++1 for a successful tag but receives a penalty of -1 if it fails to tag the target.
LaserTag (Figure 3b) an augmented version of Tag, where an agent acting in 7x11 grid world containing randomly placed obstacles. The agent's behaviour and that of its opponent align with the rules established in Tag. However, LaserTag, there's key distinction: the agent possesses prior knowledge of its initial location. Additionally, the agent is equipped with laser system capable of providing distance estimations (in cells' units) directions. The laser readings are generated from normal distribution centred around the agent's s true distance from the nearest obstacle in each direction, with standard deviation 2.5 units. These readings are then discretised into whole units, resulting in observation comprising set of 8 integers. Figure illustrates the scenarios.
(a) Tag.
(b) LaserTag.
Figure 3: Tag and Laser'Tgg scenarios' configuration.
19

---

This is common problem used for evaluating online planning algorithms [7.. This domain presents an agent that must collect boxes displaced in a rectangular grid- world. The problem is defined over partial observability and the agent does not know how the tasks are distributed. The problem ends when the agent collects all boxes. reward of +1 delivered to the agent every time a box is collected. The radius and the angle of vision (integer numbers) for the agents are, respectively, 20% of the diagonal dimension in the environment in 10 environment, so our vision radius will 0.2v2000 2. Additionally, agents have memory, i... after seeing (in the real world) a state or position in the environment, they will sample the next possible world configuration considering this information. Moreover, obstacles block the agent's 's vision, hence, it can not see tasks across the walls. Figure illustrates the scenarios.
Foraging Environment:
cells' unit and 90 for example, if we have 10
be radius 0.2 0.2 4iim. + Vdim 0.2vI00 I00 + 100
(a) The Corridor
This is a simple (20, 2) scenario, where the agent starts in the left part of corridor with box at its side and another at the end of the corridor. The idea here is to test the agent's capability to find isolated reward spots. Figure 4a illustrates the scenario.
U-Shaped - complex version of The Corridor, the U-shaped a 15 15 scenario, where the agent starts at the tip of a U-shaped corridor with box at the beginning, one in the middle and another at the end. The idea here is test the agent's capability perform simple planning, but facing sparse rewards collection. Figure 4b) illustrates the scenario.
(c) U-Obstacles A complex 20 x 10 scenario, where the agent needs to collect the boxes distributed in a room, but there are obstacles (U-shaped walls) that block its vision. This scenario is commonly used to study local minima issues that emerge in robotic navigation problems [22]. The idea here
test the agent's capability to perform planning with sparse reward collections, and the vision is blocked by obstacles. Figure 4c illustrates the scenario.
(d) The Warehouse - This scenario is our largest in terms of dimensions, 20 x 20. The agent's objective is locate specific reward spots (groups of boxes). These reward clusters situated at considerable distances from one another. Consequently. the agent cannot observe multiple reward clusters from single position, making planning more challenging. Figure 4d illustrates the scenario.
(e) The Office Our most complex 15 x 10 scenario, where the agent needs to collect the boxes distributed in office. The idea here is to test the agent's capability to perform complex planning when tasks are distributed in different rooms and its vision is blocked by walls. The agent needs to enter each room finish the problem. Figure 4e illustrates the scenario.
D Hyperparameters
We used a single hyperparameter set for all Monte-Carlo Tree Search-based methods:
Historical weight/Discount factor: 7 = 0.95
Maximum depth for the tree: 20
Maximum number of simulations: 250 (per search)
For p-POMCP and TB p-POMCP specific hyperparameters, consider the following:
Small bag size: |8]
10
* TB p-POMCP runs within the same time window of IB-POMCP's average planning time.
Finally, considering IB IB-POMCP practical enhancement, we applied g = 0.2, hence a E [0.2, 0.8).
20

---

(a) The Corridor.
(b) U-shaped.
(d) The Warehouse.
E
(c) U-Obstacles.
CE
(c) The Office.
Figure 4: Foraging environment scenario's configuration.
21


Reviews:
[{"review_id": "Kn5gR3VwBX", "reviewer": "Reviewer_QZzo", "summary": "The paper proposes several improvements to the POMCP algorithm. The improvements introduce adaptive sample size, entropy regularized tree exploration and action selection.", "questions": "Belief state particle set reinvigoration involves estimating of the observation given the action.  In all domains used for evaluation, the probability of an observation given the state is given, so this probability can be estimated from the particle state itself rather than from action-observation statistics. How accurate is your estimate compared to the particle set estimate? How does plugging in particle set based estimate affect performance of the algorithm?", "limitations": "The authors do not discuss limitations of their proposed algorithm. I suspect that the advantage of the algorithm is limited to toy domains only.", "rating": 3, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 1, "strengths": "The research considers an important problem of online planning in POMDP --- dealing with sparse rewards. A few improvements to POMCP are proposed, theoretically analysed and empirically evaluated. ", "weaknesses": "1) The authors' view on MCTS planning is partial and may be misleading. The authors argue that MCTS is based on UCB1. It is not, UCB1 is just option, there are others. One example is Thompson sampling, https://dl.acm.org/doi/10.5555/3038794.3038799 . Also, AlphaZero does not use UCB1, just as an illustration.\n\n2) The idea of adapting particle set size based on the entropy / KL divergence is nice and useful, but not novel: https://journals.sagepub.com/doi/10.1177/0278364903022012001 . Particle set size should be adapted based on diversity, either intrinsically or extrinsically estimated. \n\n3) The algorithm is not compared with DESPOT, https://papers.nips.cc/paper_files/paper/2013/hash/c2aee86157b4a40b78132f1e71a9e6f1-Abstract.html, the much better performing POMCP variant. There are follow up research publications on DESPOT in the last 10 years, too. DESPOT exhibits much better performance.\n\n4) The domains on which the algorithm is evaluated are very small and are NOT the domains on which POMCP, DESPOT and variants are evaluated for performance in the literature (Tag, LaserTag, RockSample just to name a few examples). I  am not convinced that estimates and modifications in the proposed POMCP variant scale well beyond the toy domains included in the evaluation. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback and detailed review.\n\n### 1.“Authors argue that MCTS is based on UCB1. UCB1 is just an option”\n- To avoid confusion, we will clarify that UCB1 is an option by writing that it is \"widely used\" and adding some variations in the Related Works, such as PUCT (AlphaZero) [1] and the Thompson Sampling-based approach mentioned in this review.\n- Although there are variations, **UCB1 is still a very important algorithm** in the current state-of-the-art for MCTS and ongoing research [2,3,4].\n- E.g., PUCT [1] was inspired by UCB1. It slightly modifies the traditional equation, removing the log function and adding a neural network bias multiplication. This idea modifies the original proposal but still follows the same idea of maximising the upper bound at each node.\n\n### 2.“Adapting particle set size using entropy/KL divergence is not novel”\n- IB-POMCP does not adapt the particle set size, it modifies the sampling strategy according to an approximation of our uncertainty $\\tilde{P}(z|h_r a)$ when updating the root, as presented in Section 4 (i) Root Initialization and Update.\n- The manner in which IB-POMCP incorporates these principles into the POMCP framework is novel and different from KLD strategies.\n- Unlike KLD, IB-POMCP does not need reliable true distribution or training data for optimisation. **Our information-based search eliminates this requirement** by using the search result to approximate our variable which weights the particle filter’s update.\n- Calculating the KL distance, hence the likelihood between distributions requires more computing power than our proposal. **We improve performance without sacrificing reasoning time** (supported by our results). Our sampling strategy uses the above approximation to do so.\n\n### 3.\"The algorithm is not compared with DESPOT\"\n- POMCP is still a relevant reference in the literature and supports new solutions, as we do [6,7,8,9].\n- We focus on improving POMCP, however, **our contributions can also benefit other algorithms**, including DESPOT-based solutions.\n- We do not compare our results directly with DESPOT, but we do compare our approach against competitive and more recent algorithms: rho-POMCP and TB-rho POMCP [5], both have demonstrated promising results and share the same base algorithm with IB-POMCP (POMCP).\n- DESPOT’s main focus is on filtering a large observation space to plan using a sparse approximation of the problem (smaller). However, **the algorithm still struggles** in large action spaces, and/or **sparse reward scenarios** where the optimal policy could be long (require many steps). Our proposal addresses POMDPs featuring sparse rewards in an efficient manner and hence is focused on solving a different research problem than DESPOT.\n- DESPOT-based algorithms still require the definition of good default policies to run the solution. They also need $D$ and $K$ parameters to be set beforehand, and it would be problematic in the sparse reward case if no or almost no rewards are seen within the $D$ parameter (depth). **Our algorithm, however, can handle this kind of situation**, running the search process from scratch and still leading the tree to expand towards promising high entropy subtrees, even when no rewards are observed in the planning horizon.\n- DESPOT will be added to our related work discussion.\n\n### 4.\"The domains are very small and are NOT the domains evaluated in the literature.\" and “I suspect that the advantage is limited to toy domains only.”\n- Our domains also present relevance in the literature and have been frequently used as benchmarks [9, 10, 11], presenting their own complexity and specific challenges.\n- Tag/LaserTag and RockSample **do not feature the sparse rewards** in their proposal. Instead, rewards are delivered from any state upon performing the \"reward collection\" action (as in the Maze).\n- For the study of sparse reward, we chose the Foraging environment (details in our Tech. Appendix, Section 3).\n- We also emphasise that our domains complexity is not comparable to simple toy problems. In fact, they are similar to the LaserTag and some of our scenarios are even larger/more complex than this traditional benchmark.\n    - Our Foraging Warehouse scenario, for example, which has dimensions $20\\times20$ and $|Z|$ in the order of $10^19$, showcases the scalability of IB-POMCP while surpassing the traditional LaserTag ($7\\times11$ with $|Z|$ in the order of $10^6$) as presented in the referred DESPOT's paper.\n\n### 5.\"authors do not discuss limitations\"\n- We carefully presented the limitations alongside the discussion of our results.\n- We separate the analysis by domain and provided insights into why we performed better and when we might encounter challenges.\n\n[1] Silver, D. et. al. Mastering the game of Go without human knowledge. In Nature 2017\n\n[2] Sunberg, Z. et. al. \"Online algorithms for POMDPs with continuous state, action, and observation spaces.\" In  ICAPS 2018\n\n[3] Hoerger M. et. al. \"An On-Line POMDP Solver for Continuous Observation Spaces\". In ICRA 2021\n\n[4] Riccio, F. et. al.. \"LoOP: Iterative learning for optimistic planning on robots.\" In RAS 2021\n\n[5] V. Thomas et. al. Monte Carlo information-oriented planning. In ECAI 2020\n\n[6] Amini, S. et. al. POMCP-based decentralized spatial task allocation algorithms for partially observable environments. In Appl Intell 2023\n\n[7] Mazzi, G. et. al. Learning Logic Specifications for Soft Policy Guidance in POMCP. In AAMAS  2023\n\n[8] Zuccotto, M. et. al. Learning state-variable relationships for improving POMCP performance. SIGAPP 2022\n\n[9] Mern, J. et. al. Bayesian Optimized Monte Carlo Planning. In AAAI 2021\n\n[10] Yourdshahi, E et al. \"On-line estimators for ad-hoc task execution: learning types and parameters of teammates for effective teamwork.\" In AAMAS 2022\n\n[11] Schwartz, J. et .al. \"Bayes-Adaptive Monte-Carlo Planning for Type-Based Reasoning in Large Partially Observable, Multi-Agent Environments.\" In AAMAS 2023"}, {"review_id": "7FYy3agPUf", "reviewer": "Reviewer_zmgm", "summary": "This paper proposes a novel approach for online planning under uncertainty. It leverages the information entropy to guide a tree search process. ", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* This paper is welled structured.\n* The paper conducts both empirical and theoretical analysis.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your assessment and for considering our paper for acceptance. \nWe are delighted and encouraged by your positive evaluation and enthusiasm for the work we propose. "}, {"review_id": "ysgSimQun3", "reviewer": "Reviewer_JP1G", "summary": "This paper presents IB-POMCP, a novel algorithm for online planning under partial observability, that uses entropy estimation to guide the tree search. The main concept is to replace the traditional explore-exploit balancer (UCB1) with (an IUCB score) which is a weighted mixture of value, exploration score, and entropy score. This idea is motivated by the failure modes of other algorithms tackling POMDP problems: poor performance in the case of sparse rewards and especially sparse rewards that are often delivered outside of the algorithm's planning horizon. IB-POMCP is compared against POMCP and TB rho-POMCP on 3 tasks: Tiger, Maze, and Foraging. The experiments show a clear advantage of IB-POMCP. There is also an ablation study which gives even more insight into the method.", "questions": "1. The tiger environment has a limit of 20 actions. What exactly happens when the agent chooses to listen 19 times in a row? In the 20th step, the action space is different and consists of only choosing the door to open or can the agent listen again?\n2. In practice: can the entropy of the whole tree behave non-monotonically over time? If yes, how often it happens?\n3. line 159: how exactly is the tree re-initialized?", "limitations": "There is little about the limitations of the method. I would like to know for example: can IB-POMCP be used on any POMDP? How the resources needed to solve a task with IB-POMCP depend on the problem's complexity? What is the worst-case scenario performance? What is the memory-usage?", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The experiments are carefully made (with confidence intervals) and clearly show the advantage of the method over baselines. Also, there is a time comparison, which shows another desired property of IB-POMCP: it is usually faster than baselines. There is an exhaustive discussion of the results. The paper contains an ablation study, which compares the effect of two different aspects of IB-POMCP:\na) information guided particle reinvigoration\nb) U-UCB score\nIt is demonstrated that both of the above contribute to the effectiveness of IB-POMCP and there is an interesting comment about these results.  \nThe paper is well-written, images are helpful. There are mathematical theorems guaranteeing theoretical convergence to optimal solution or near optimal (with a limited planning horizon). Mathematical formulas are explained via insightful comments. The main ideas of the paper is clear simple and easy to uderstand.", "weaknesses": "It is impossible for me to describe the scientifically important weaknesses of this paper since it is far outside my area of expertise. I can only provide minor weaknesses:\n\n1. The paper assumes a reader has a lot of prior knowledge in the area of POMDP. It is a problem or not depending on the desired reader. As a person who is not familiar with the topic, I like to have more preliminary comments.\n2. Notation may be not entirely clear for a person not familiar with the topic, i.e.  line 169, what exactly means: \"haz\"?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful feedback and acceptance of our proposal. Your thorough review demonstrates the depth of your evaluation and the meaningful consideration.\n\n### 1.”The paper assumes a reader has a lot of prior knowledge in the area of POMDP.” and “Notation may be not entirely clear for a person not familiar with the topic.”\n- In the revised version, we will *carefully review the notation* to make it more **accessible and understandable** (Sections 3-4), particularly for those new to the topic.\n\n### 2.Line 169: what is $h_{r} az$? \n- In the current text, we say “$a$ is the action just taken by the agent in the real world, $z$ the real observation received from the environment, $N(h_raz)$ the number of visits of $h_raz$ node, the new root”. We will add a clarification presenting “the number of visits of the node with history $h_raz$” instead of “the number of visits of $h_raz$ node”.\n\n### 3.”The tiger environment has a limit of 20 actions. What exactly happens when the agent chooses to listen 19 times in a row? In the 20th step, the action space is different and consists of only choosing the door to open or can the agent listen again?”\n- When the agent chooses to listen 19 times in a row, it receives a reward of $-19$ (since each listen delivers a $-1$ reward). And after the 20th step, the agent can listen again. The action space is still the same.\n\n### 4.”In practice: can the entropy of the whole tree behave non-monotonically over time? If yes, how often it happens?\n- In fact, *the tree entropy behaves in a non-monotonical way*. However, noticing that it may cause problems in the estimation, **we have designed our approach to effectively handle this situation**. The proposed alpha equation (Equation 1) ensures that the entropy values monotonically decrease as we approach infinity, which *aids in the convergence of our entropy and updates the tree knowledge*. This mechanism is akin to the entropy update within the IB-POMCP tree and the utilization of UCB1/I-UCB equations. By incorporating this method, we can effectively manage the non-monotonic behaviour of the tree entropy.\n- Regarding the frequency of changes in the entropy trend, it depends on the size of our observation space and how often we can visit different states within our reasoning horizon, hence, depends on the internal policies of the tree.\n\n### 5.”line 159: how exactly is the tree re-initialized?”\n- The re-initialisation of the tree occurs with the creation of a new root node for the tree. We create a new node $(h, V(h), N (h), B(h))$ with $h$ as the current history (sequence of actions and observations collected from the world) $V(h) = 0$, $N(h) = 0$ and $B(h)$ is empty. This new node will be considered as the new root. It means that all other simulations already made in the agent’s head are discarded and we re-start the process using the created node. We refer the reader to [1] for further detail (reference also in the paper).\n- We can add the above explanation in the text to better clarify the tree re-initialisation process.\n\n### 6.”There is little about the limitations of the method. can IB-POMCP be used on any POMDP?\n- Yes, IB-POMCP can be used on any POMDP. Additionally, we provide theoretical guarantees to its application  (Section 5).\n- Besides that, we can say that all we need is a black-box simulator to sample transitions given a state and an action, since we are based on POMCP, so even an explicit model of the POMDP is not needed.\n\n### 7.“How the resources needed to solve a task with IB-POMCP depend on the problem's complexity?” and “What is the memory-usage?”\n- IB-POMCP's planning complexity is comparable to POMCP.\n- In terms of time, in most studied cases (see Result section, line 357, for insights on this analysis), we could perform similarly or faster than POMCP.\n- In terms of memory, IB-POMCP will require more memory to allocate the observation multi-set. But, it is still small and it does not impact reasoning time.\n\n### 8. What is the worst-case scenario performance? \n- We believe that our worst-case performance is comparable to POMCP, hence, UCT, being  $\\Omega(exp(exp(. . . exp(1) . . .)))$ [1].\n\n[1] Silver, D. et. al. \"Monte-Carlo planning in large POMDPs.\" In NeuRIPS, 2010."}, {"review_id": "c4DTZlC36D", "reviewer": "Reviewer_hPBV", "summary": "The paper presents an extension to the POMCP algorithm for online planning under partial observability, called Information-Based POMCP (IB-POMCP). The distinguishing feature of IB-POMCP is that it uses information entropy to enhance the tree search procedure. One effect of this extension is that IB-POMCP is better able to handle sparse rewards, performing its search based on which branches of the tree are likely to yield higher information gain, unlike previous methods which consider only exploration of the tree. \n\nThe first modification to POMCP is that when an action is taken in IB-POMCP, new particles are sampled after an action is taken, depending on how unlikely the resulting observation is. If an observation is received that had a high probability, then the particles in the new b root node are expected to capture the belief well. On the other hand, if the probability is low, then more new particles are generated from a uniform distribution. The intention of this is to improve the algorithm’s starting point at each step. \n\nThe second modification is the introduction of a new exploration coefficient which is recalculated at each iteration of the search - replacing the alpha coefficient from UCB1 with a new version for I-UCB. The I-UCB alpha coefficient captures information about visit counts similar to UCB1, but includes an additional term which favours nodes with high entropy. The idea of this term is to seek information gain during the search procedure, where the entropy is estimated from the set of observations seen so far. This is a more nuanced search procedure than standard UCB1, which only considers the number of times each node has been visited, but not the distribution of observations received.", "questions": "* Please argue for the significance of the contribution presented in the paper. How is this a substantial step from the state-of-the-art?\n* Unclear to me why $\\alpha(h_\\tau)$ (Equation 1) is defined only at the root node rather than at every subsequent node - is this to make the algorithm simpler, or is there an actual justification for why this is preferable or doesn’t matter?\n* Line 351-354 is a bit of a long-winded sentence and unclear what is meant by the final bit - “often seek paths that lead to spots with high entropy in order to decrease uncertainty”, what uncertainty is being decreased here?  \n* Line 369 what is meant by “without penalising reasoning time”? Is this just saying that IB-POMCP performs well without taking longer to plan than other methods, or something more specific?", "limitations": "The experiments section might be strengthened by the addition of another baseline which uses some sort of latent world model (e.g. SARSOP?). It would be interesting to see a comparison with a model that does better than IB-POMCP on performance but requires much more computation time to do so. This would provide a concrete justification for the claim in Lines 51-55 that such modelling is too computationally intensive.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents an approach to planning for partially observable problems that makes a clear original contribution to the literature on planning under partial observability.  \n\nThe authors justify the benefits of their information-guided approach to POMCP-style planning in a manner that makes intuitive sense. The paper also provides a strong experimental justification for the approach, evaluating against relevant baselines in standard domains, as well as providing an ablation study that justifies the individual components of their algorithm. The experiments cover a good range of domains, and the intuition behind the results is explained fairly well. \n\nThe paper is overall well structured and written, and presents its key ideas in a clear and logical manner.", "weaknesses": "After discussion, I believe that I was a bit too negative regarding the substantiality of the contribution, so I'm increasing the score. Please do not that the section with the theoretical results needs improvement. I think adding intuition and discussion around those results is more important than adding a new domain to the experiments.\n\n---------\nMy main concern with the paper is the incremental aspect of its contributions. The two improvements over POMCP are (i) adding some standard tricks to the particle filter so that it tracks the belief more accurately, and (ii) a new action selection equation which simply considers entropy of the belief as an extra term. This is a bit on the light side. I’d expect a strong theoretical analysis and justification of Equation (3) to bring the significance of the contribution up. Furthermore, the technical section is simply a listing of results without any context or intuition - not enough insight is given to the reader.\n\nOther issues:\n\n* Equation 2 could do with more justification/explanation of how the update works.\n* Line 128 the terminology “the probability of stepping into this node” is unclear and needs further explanation at this point in the text. It made sense to me only after I got up to Section 4(ii). \n* Figure 1 caption should explain in more detail what is being shown (e.g. “bright red dots represent X, faded red dots represent Y, blue dots represent Z”). This is mentioned in the text in Line 232 but more detail would be helpful to clarify the diagram. \n* Following from the above, I think the authors should make a clearer distinction between the (online) planning phase and action execution. For example, I don’t think it’s clear from the paper that one *only* updates the belief after executing an action, and the POMCP tree keeps histories as nodes but does not do any explicit belief update.\n* Lines 264-270 could do with a clearer explanation of the terms “information gain” vs “exploration gain”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank your feedback and comments towards acceptance.\n\n### 1.“Argue for the significance of the contributions.”\n- **Weak constraints to run**: we refined action selection (via I-UCB) and proposed a novel framework (IB-POMCP) that *does not demand prior data collection or the modelling of latent functions*.\n- **Handles sparse rewards**: IB-POMCP is the pioneer in leveraging entropy to estimate information gain using both real-world and internally generated observations, allowing it to identify promising states even *when rewards are not* readily *available* or *sparse* within the planning horizon.\n- **Light-weight framework**: we *enhance planning without increasing reasoning time*. Our novel approach potentially impacts AI and decision-making by improving uncertainty planning capabilities while maintaining efficiency.\n \n### 2.”My main concern with the paper is its incremental aspect.”\n- IB-POMCP and I-UCB are not incremental; rather, they represent a **well-connected and innovative approach** to enhancing POMCP planning and reasoning. \n- Our approach significantly improves the belief tracking in the particle filter, surpassing standard techniques in the literature by **(i)** using our refined weight coefficient, $\\alpha$ ; **(ii)** using our I-UCB equation for tree expansion, and; **(iii)** using our novel strategy to update the root’s particle filter based on tree search result.\n- Our method delivers accurate and efficient planning, *demonstrated empirically and theoretically*.\n- Incorporating entropy-based weight factors into the action selection equation and particle update is a unique and novel contribution. This drives informed decisions and substantial performance improvements, even in scenarios without available rewards within our reasoning horizon. *Each individual contribution is combined in a non-trivial and novel manner*, and their combined effect, as showcased in the Ablation Study results (Section 6), significantly enhances the overall performance.\n\n### 3.”The authors add some standard tricks to the particle filter to track belief more accurately”\n- Our particle filter update proposal *does not implement any existing method or trick to improve the belief’s track*. Our proposed solution is the result of our information-guided search process, hence the I-UCB implementation, another novel solution in the paper.\n- Refer to answers (1) and (2).\n\n### 4. “The new action selection equation simply adds the entropy as an extra term.”\n- The addition of our extra term required the *mathematical design and tuning of a **non-trivial** part of the equation*. This process required the study of how observations behave inside the tree search framework and the proposal of an equation that handles the estimation in a way to improve performance.\n- Also, refer to answers (1) and (2).\n\n### 5.”What is meant by “without penalising reasoning time”?”\n- We mean that IB-POMCP performs well without taking longer to plan than other methods. The reasoning time considers the whole search process until the algorithm delivers the best action to the agent.\n\n### 6.“I’d expect a strong theoretical analysis of Equation (3)”\n- Our complete theoretical analysis (Technical Appendix) shows IB-POCMP convergence to epsilon-optimal action based on the analysis of Eq 3.\n- Lemma 1 addresses the alpha coefficient convergence in order to show, in Lemma 2, that Eq 3 converges for a finite number of iterations.\n- The consequence of the convergence of Eq 3 is our Corollary 1. \n\n### 7.”Experiment section might be strengthened by another baseline (e.g. SARSOP?). It would be interesting to see a comparison with a model that does better than IB-POMCP on performance but requires much more computation time to do so.”\n- SARSOP is an off-line planner already compared to POMCP in the original POMCP paper, where it was shown that POMCP achieves similar results with a significantly reduced computational time.\n- $\\rho$-POMCP doesn't take as much time as SARSOP, and it is a more recent algorithm, serving to present the suggested comparison. Besides, it demands additional knowledge to run than IB-POMCP (transition and observation function probabilities).\n- $\\rho$-POMCP and IB-POMCP share the same base algorithm (POMCP), but our approach stands out in its ability to handle scenarios with sparse rewards. We demonstrate competitive results in terms of reward collection (refer to Table 1).\n\n### 8.”Why $\\alpha(h_r)$ is defined only at the root node?”\n- To clarify, $\\alpha$ is defined at the root because we update it at the root’s level. However, its calculated value is used in the action selection of all nodes.\n- This decision was made after exploring various approaches and collecting preliminary results. Updating $\\alpha$  solely at the root showed better results than updating it for every node in the simulation path.\n- Our update strategy considers the complete simulation’s information to update $\\alpha$ (all rewards and observations collected through the simulation path). Hence, our update occurs after **all this information is backpropagated** to the root.\n- Updating $\\alpha$ for all nodes in the simulation path significantly enhances computational efficiency ($100$ updates in a tree with depth $10$ and $100$ simulations, would be $1000$ updates in the worst-case scenario for the all-nodes approach).\n \n### 9.”“Often seek paths with high entropy in order to decrease uncertainty”, what uncertainty is being decreased?”\n- The system’s entropy is being decreased. In Maze, the agent must seek cells that maximise entropy to maximise the reward collection. As demonstrated in the results, IB-POMCP finds these cells frequently and then collects the higher reward (reducing the entropy).\n- We can make it clearer by refining the text.\n\n### 10. Minor issues\n- We will fix all the minor points mentioned in your review: figure caption, term clarification, etc. \n- Regarding Equation 2, we will add further detail in our supplementary material.\n"}]

Author rebuttal:
We thank all the reviewers for their valuable feedback. In this global response, we summarise all the major points  of our work based on this rebuttal phase’s feedback.

### Novelty 
- **Particle filter update** 
   - Our root's particle filter update strategy is based on the behaviour of tree search-based algorithms for POMDPs.
    - Unlike traditional methods, we augment belief tracking by approximating the uncertainty of transitioning into the current belief state given the real action and the real observation received from the world, denoted as $\tilde{P}(z|h_r, a)$ (Line:169).
    - Notably, this is a lightweight approach and adaptable to various tree search-based solutions, making it a versatile enhancement strategy. 
- **Traditional methods**
    - Our particle resampling strategy is guided by the framework's execution, driven by $\tilde{P}(z|h_r, a)$, which hinges on I-UCB, being fundamentally different from the traditional resampling strategy in the literature. Our Ablation Study (Section 6) showcases the critical role of this connection in performance enhancement.
    - Distinguishing ourselves to other entropy-based methods, such as KLD, our particle filter update operates independently of extensive entropy or likelihood computations or the need for prior knowledge to define target distributions.

- **$\alpha$ function proposal:**
    - The $\alpha$ value, updated at the root level, influences action selection across all nodes.
    - Our update strategy integrates complete simulation information to adjust $\alpha$, aggregating all rewards and observations obtained throughout the simulation path. This update occurs after the entire observation (information) set is backpropagated to the root.
    - The backpropagation of observation is a novel strategy to maintain all observations (information) aggregated since the beginning of the search process, at the root node level. 
    -  Addressing the challenge of estimating entropy in these algorithms, while handling unknown distributions and looking for the optimal actions, the novel $\alpha$ function adeptly manages the scenarios information to prevent problems (like preventing entropy overestimation due to expanding observation space (Line:248)), without relying on extensive computations or prior knowledge.

- **I-UCB design:**
    - I-UCB represents a novel variation of the traditional UCB function that smartly incorporates the concept of information gain into the tree search process.
    - Using the $\alpha$ function, I-UCB balances the trade-off between exploitation, exploration, and information value in an original and sophisticated manner
    - I-UCB can guide the search process and allow the algorithm to identify promising states even when rewards are not available or distributed sparsely within the planning horizon. This is novel since most of the UCB variants are focused on strategies that enhance the planning/search process based on rewards optimisation.

### Relevance/Significance
- **POMCP and UCB:** While our study centers on the enhancement of POMCP and the UCB equation, its applicability readily extends to diverse planning frameworks. It's noteworthy that both POMCP and UCB are still significant references in the literature [1,2,3] and consistently yielding impactful advancements in the field [4,5,6].
- **Weak constraints to run:** We refined action selection (via I-UCB) and proposed a novel framework (IB-POMCP) that *does not demand prior data collection or the modelling of latent functions*.
- **Handles sparse rewards:** IB-POMCP leverages entropy to estimate information gain using both real-world and internally generated observations, allowing it to identify promising states even *when rewards are not* readily *available* or *sparse* within the planning horizon.
- **Light-weight framework:** we *enhance planning without increasing reasoning time*. Our novel approach potentially impacts AI and decision-making by improving uncertainty planning capabilities while maintaining efficiency.

### Theoretical Analysis
- We provide the complete theoretical analysis of our proposal.
- In our Technical Appendix, we show that IB-POCMP convergence to epsilon-optimal action under a finite number of iterations.
- We analyse the convergence for the $\alpha$ function and I-UCB equation. 
- All the theoretical guarantees are supported by our empirical results.

### Baselines and benchmarks
- We emphasise the our domains complexity comparing to traditional benchmark, presenting specific challenges and enabling different analysis. 
    - The Maze problem allows us to study how IB-POMCP handles uncertainty and approximates belief to the actual world, as it involves self-localization challenges. 
    - On the other hand, the Foraging environment enables us to explore how IB-POMCP deals with reward sparsity while planning under uncertainty.
- Our benchmark scenarios are far from toy problem complexity.
    - Our Foraging Warehouse scenario, for example, which has dimensions $20\times20$ and $|Z|$ in the order of $10^19$, showcases the scalability of IB-POMCP while surpassing the traditional LaserTag ($7\times11$ with $|Z|$ in the order of $10^6$) as presented in the referred DESPOT's paper.

[1] Sunberg, Z. et. al. "Online algorithms for POMDPs with continuous state, action, and observation spaces." In  ICAPS 2018

[2] Hoerger M. et. al. "An On-Line POMDP Solver for Continuous Observation Spaces". In ICRA 2021

[3] Amini, S. et. al. POMCP-based decentralized spatial task allocation algorithms for partially observable environments. In Appl Intell 2023

[4] Mern, J. et. al. Bayesian Optimized Monte Carlo Planning. In AAAI 2021

[5] Yourdshahi, E et al. "On-line estimators for ad-hoc task execution: learning types and parameters of teammates for effective teamwork." In AAMAS 2022

[6] Schwartz, J. et .al. "Bayes-Adaptive Monte-Carlo Planning for Type-Based Reasoning in Large Partially Observable, Multi-Agent Environments." In AAMAS 2023


Meta-review: This paper presents a novel extension of POMCP for online planning in POMDPs. The approach (IB-POMCP) uses belief entropy to guide search, improving the handling of sparse rewards. 

Online planning in POMDPs is a very difficult problem and while there has been work in the area, developing scalable and well-performing methods is still an open problem. This paper builds on the popular POMCP and UCB methods, making the approach widely applicable. 

Where there was some concern about the experimental results and the generality of the method, the approach improves performance while maintaining strong guarantees. Furthermore, the author response with additional clarifications and experiments was very helpful. These responses were helpful for better understanding the novelty and significance of the method, understanding the theory, and confirming improved performance on other standard domains. The paper should include these updates in any final version.
Decision: Accept (poster)