Paper deep dive
Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics
Masafumi Endo, Kohei Honda, Yuu Jinnai, Ryo Yonetani
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/20/2026, 4:53:21 AM
Summary
This paper introduces the Orienteering Problem with Uncertain Time-Varying Rewards (OP-UTVR), a novel variant of the orienteering problem where rewards are stochastic and time-varying, unlike traditional formulations that assume static or known rewards. The authors propose three planning algorithms: One-Step Planner (greedy), Offline Planner (static long-horizon), and Adaptive Online Planner (replanning with observations). Theoretical analysis shows that the Adaptive Online Planner achieves near-optimal performance and outperforms the Offline Planner as reward stochasticity increases. A mobile service robot benchmark is introduced, simulating a robot navigating among pedestrians in indoor environments to maximize interaction rewards.
Entities (8)
Relation Signals (7)
OP-UTVR → isvariantof → Orienteering Problem
confidence 98% · We present the orienteering problem with uncertain time-varying rewards (OP-UTVR), a novel variant of the orienteering problem (OP).
Adaptive Online Planner → solves → OP-UTVR
confidence 95% · We address this problem using three planners... Adaptive Online Planner also plans the entire path but replans at each visited location
Mobile Service Robot Benchmark → implements → OP-UTVR
confidence 92% · We further introduce a mobile service robot benchmark for OP-UTVR
Adaptive Online Planner → outperforms → Offline Planner
confidence 90% · Theorem 3 suggests that the advantage of adaptation grows with reward stochasticity.
Mobile Service Robot Benchmark → uses → IR-SIM
confidence 90% · We build our benchmark on IR-SIM (Han et al. 2026), an open-source multi-agent crowd navigation simulator.
Mobile Service Robot Benchmark → usesdatafrom → HM3D
confidence 88% · Test environments come from the HM3D (Ramakrishnan et al. 2021) and Gibson (Xia et al. 2018) datasets
Mobile Service Robot Benchmark → usesdatafrom → Gibson
confidence 88% · Test environments come from the HM3D (Ramakrishnan et al. 2021) and Gibson (Xia et al. 2018) datasets
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We present the orienteering problem with uncertain time-varying rewards (OP-UTVR), a novel variant of the orienteering problem (OP). While most existing OP formulations assume rewards to be known in advance, practical applications involve uncertain and time-varying rewards, as with shifting customer demand for delivery agents. OP-UTVR relaxes this assumption by allowing agents to estimate reward dynamics from observations and forecast future rewards. This enables informed routing decisions despite stochastic reward changes and inevitable prediction errors. We address this problem using three planners that differ in planning horizon and online adaptivity, and derive theoretical bounds on their performance under reward stochasticity. We further introduce a mobile service robot benchmark for OP-UTVR, where a robot navigates among pedestrians in indoor environments. Experiments reveal trade-offs between planning horizon and adaptivity, and demonstrate the effectiveness of long-horizon planning with online adaptation.
Tags
Links
- Source: https://arxiv.org/abs/2608.18672v1
- Canonical: https://arxiv.org/abs/2608.18672v1
Trouble viewing inline? Open PDF directly →
Full Text
57,700 characters extracted from source content.
Expand or collapse full text
Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics Masafumi Endo Kohei Honda Yuu Jinnai Ryo Yonetani Abstract We present the orienteering problem with uncertain time-varying rewards (OP-UTVR), a novel variant of the orienteering problem (OP). While most existing OP formulations assume rewards to be known in advance, practical applications involve uncertain and time-varying rewards, as with shifting customer demand for delivery agents. OP-UTVR relaxes this assumption by allowing agents to estimate reward dynamics from observations and forecast future rewards. This enables informed routing decisions despite stochastic reward changes and inevitable prediction errors. We address this problem using three planners that differ in planning horizon and online adaptivity, and derive theoretical bounds on their performance under reward stochasticity. We further introduce a mobile service robot benchmark for OP-UTVR, where a robot navigates among pedestrians in indoor environments. Experiments reveal trade-offs between planning horizon and adaptivity, and demonstrate the effectiveness of long-horizon planning with online adaptation. 1 Introduction Rewards in the real world are often dynamic and inherently uncertain. Imagine a taxi driver targeting a high-traffic area. Passenger demand shifts with commuting patterns, yet individual trajectories of potential riders remain stochastic and unknown. Handling uncertain reward dynamics matters even more in disaster response; it is crucial to locate those stranded within affected zones, where the probability of successful rescue diminishes over time due to the highly uncertain dynamics of the environment. We are interested in enabling mobile agents that can plan and execute an effective path to collect such uncertain time-varying rewards across multiple destinations. A natural starting point for these selective routing problems is the orienteering problem (OP; Tsiligirides 1984, Tsiligirides 1984), where the objective is to find a sequence of locations to visit that maximizes accumulated rewards under resource constraints. While the OP has inspired a variety of related applications, such as persistent monitoring (Yu, Schwager, and Rus 2016), unknown terrain exploration (Peltzer et al. 2022), or search-and-rescue operations (Jorgensen and Pavone 2024), existing work assumes that rewards are static or follow dynamics known to the agent (Ma et al. 2017; Cao et al. 2024). These assumptions rarely hold in practice and create a performance gap when actual rewards vary and deviate from expectations. This gap motivates the main contribution of this work: a novel variant of the OP named orienteering problem with uncertain time-varying rewards (OP-UTVR). Unlike existing OP variants with static or known time-varying rewards, OP-UTVR captures two challenges arising from reward uncertainty: 1) Rewards vary stochastically over time, like a crowd of potential taxi riders moving in an apparently random manner; and 2) agents are only allowed to ‘predict’ such time-varying rewards for a limited time horizon, which inherently involves prediction errors relative to actual rewards. To solve the proposed OP-UTVR, we investigate three planning algorithms that leverage reward prediction differently, and theoretically characterize their performance. Specifically, One-Step Planner greedily selects the next location based on predicted immediate rewards. Offline Planner predicts time-varying future rewards until the time limit, and plans an entire path that maximizes the accumulated rewards. Finally, Adaptive Online Planner also plans the entire path but replans at each visited location, using updated observations to adapt to reward uncertainty. We prove that Adaptive Online Planner achieves near-optimal performance under accurate reward estimation, with its advantage over Offline Planner growing as reward stochasticity increases. As an evaluation benchmark for OP-UTVR, we develop a mobile service robot benchmark that simulates a robotic agent navigating among moving pedestrians in indoor environments reconstructed from real-world 3D scans (Ramakrishnan et al. 2021; Xia et al. 2018). Figure 1 illustrates the motivating application of this benchmark, where the robot aims to maximize rewards given by pedestrian interactions for service activities such as greeting or advertising. This task naturally induces uncertain time-varying rewards: rewards change as pedestrians move, while their intentions remain unknown and future motion grows increasingly unpredictable. Our comprehensive evaluation reveals trade-offs among the three planners between planning horizon and adaptivity to uncertain pedestrian movements. The results demonstrate the effectiveness of integrating long-horizon planning with adaptive replanning through runtime observations. Figure 1: Motivating application: Service robot benchmark for OP-UTVR. A robot plans a path to maximize pedestrian interactions within a time budget T. Vertices are gathering spots, with colors indicating visitor density (red, green, blue, white from high to empty). Rewards change as visitors move, a setting that traditional OP cannot handle. 2 Preliminaries The OP addresses selecting and ordering vertices to visit, to maximize collected rewards under a time budget. We review the classical formulation and its extension to known time-varying rewards to differentiate them from OP-UTVR. 2.1 Orienteering Problem with Static Rewards An instance of OP is defined by tuple (,ℰ,v0,r,d,Tmax)(V,E,v_0,r,d,T_max). Here, V is the set of vertices and ℰE is the set of edges with e(v,v′)∈ℰe(v,v ) connecting vertices v,v′∈v,v . Each vertex has an associated static reward (profit) r:→ℝ≥r:V _≥, while each edge has an associated travel time d:ℰ→ℕd:E (i.e., discrete time steps). Starting from the initial vertex, v0∈v_0 , the agent moves between the vertices along the edges to collect the rewards while consuming travel times. The objective of OP is to find a path, i.e., a sequence of distinct connected vertices, V=(v0,v1,…,vn−1)V=(v_0,v_1,...,v_n-1) that maximizes the total rewards Rtot(V)R_tot(V) within the time budget TmaxT_max as follows: Rtot(V) R_tot(V) =∑i=0n−1r(vi) = _i=0^n-1r(v_i) (1) s.t.∑i=0n−2d(e(vi,vi+1))≤Tmax. .t.\; _i=0^n-2d(e(v_i,v_i+1))≤ T_max. (2) Since rewards are static and certain, the optimal path can be planned entirely in advance. This assumption holds in applications such as tourist trip planning (Vansteenwegen, Souffriau, and Van Oudheusden 2011), where the value of each location is predetermined. 2.2 Extension to Known Time-Varying Rewards Prior work extends the OP to handle time-varying rewards, where the reward at each vertex depends on the visit time. Formally, we consider a reward function that maps a combination of vertex and time to a reward: rtv:×ℕ→ℝ≥r_tv:V×N _≥. The objective is to find a path V=(v0,v1,…,vn−1)V=(v_0,v_1,…,v_n-1) with corresponding visit times (t0,t1,…,tn−1)(t_0,t_1,…,t_n-1) that maximizes: Rtot(V)=∑i=0n−1rtv(vi,ti). R_tot(V)= _i=0^n-1r_tv(v_i,t_i). (3) Unlike the static case, the same vertex provides different rewards depending on when it is visited, i.e., the solution requires optimization of both vertex selection and visit timing. Ma et al. 2017 introduced this extension, while Cao et al. 2024 improved efficiency via heuristic search. However, both assume that rtv(v,t)r_tv(v,t) is completely known in advance. This assumption is valid only for applications where reward dynamics follow known patterns, such as factory production schedules or periodic traffic flows. When rewards arise from uncontrollable factors, such as pedestrians whose intentions are unobservable, their dynamics are inherently stochastic, which makes exact prediction impossible. 3 Orienteering Problem with Uncertain Time-Varying Rewards (OP-UTVR) The proposed OP-UTVR is a novel variant of the traditional OP with two key features: 1) the rewards vary over time under uncertain dynamics that nevertheless can be predicted from observations for a short time horizon; 2) the agent can revisit the same vertices consecutively or repetitively in a solution path. A motivating example is a mobile service robot that needs to interact with as many pedestrians in the environment as possible by predicting their future locations, within its battery limit. Below, we formulate each key feature. 3.1 Problem Formulation OP-UTVR consists of a tuple (,ℰ,v0,rtv,P^,P,d,Tmax)(V,E,v_0,r_tv, P,P,d,T_max). Unlike the problems in Sec. 2.2, we tackle a more challenging case where the true time-varying reward rtvr_tv will remain unknown until actual time t. While rtvr_tv is not given, we assume two properties that the agent can exploit. First, we assume that the underlying reward dynamics P is a Markov chain over vertices V. That is, rtvr_tv moves between vertices following a transition matrix P.11 1 More complicated transition models, such as non-linear or non-Markovian dynamics, are left for future work. Specifically, let P∈(Δ||−1)||P∈( ^|V|-1)^|V| be the true (and unknown) row-stochastic transition matrix, where pu,vp_u,v represents the probability of reward transitioning from vertex u to vertex v. Let tv:ℕ→ℝ≥1×||r_tv:N _≥^1×|V| represent the true reward value at each vertex at timestep t. tvr_tv evolves following the underlying transition matrix P, and its expectation satisfies: [tv(t+1)]=tv(t)P.E[r_tv(t+1)]=r_tv(t)\,P. (4) The other assumption is that the agent has access to an estimate of the transition matrix, P^≈P P≈ P. P P can be obtained in any way; in our benchmark, we estimate it from prior observations (Sec. 5). The agent may use P P to estimate rtvr_tv in future using Eq. (4). Let r^tv r_tv denote the time-varying reward estimated by P P. Then, the estimated future reward ^tv(t) r_tv(t) at timestep t can be computed by multiplying P P for t times to the observation of tv(0)r_tv(0), which is available to the agent at the beginning of the traversal. [^tv(t)∣tv(0)]=tv(0)P^t.E[ r_tv(t) _tv(0)]=r_tv(0)\, P^t. (5) Yet with uncertainty, this enables the agent to make its decisions with estimates of the expected future reward. To summarize, unlike existing time-varying reward OP problems, the agent in OP-UTVR knows neither rtvr_tv nor P in advance; it only observes tv(t)r_tv(t) at each timestep t and has access to the estimate P P for reward prediction. 3.2 Solution The challenge of OP-UTVR requires the solutions to be formatted differently from prior formulations in two ways. First, we allow the agent to make decisions online. In OP-UTVR, an agent may benefit from adapting to unexpected outcomes during the traversal. While rtv(⋅,t)r_tv(·,t) is unknown in advance, we assume the agent observes the rewards at all vertices at timestep t. This also leads to an update to the estimate of the future reward. At timestep 00, the estimated reward at timestep t is computed as in Eq. (5). However, when the agent is at timestep tnowt_now, it may update its estimate using the observation of tv(tnow)r_tv(t_now), which is likely to be more informative than the observation at previous timesteps: [^tv(t)∣tv(tnow)]=tv(tnow)P^t−tnow.E[ r_tv(t) _tv(t_now)]=r_tv(t_now)\, P^t-t_now. (6) Thus, we allow the agent to choose its path adaptively during traversal in OP-UTVR. Concretely, the solution of OP-UTVR is a policy π that computes the next vertex to visit given the current circumstances (e.g., current agent and reward positions, remaining timesteps). The other point to consider is that, in OP-UTVR, the agent does not have to visit a new previously unvisited vertex to obtain a new reward. Because the rewards are also moving, the agent may obtain rewards from visiting the same vertex more than once. For example, the agent may choose to visit the same vertex consecutively to wait at the current position, e.g., V=(v,v,v,v′,…)V=(v,v,v,v ,…) or repetitively e.g., V=(v,v′,v′,v,…)V=(v,v ,v ,v,…). For the sake of simplicity, we denote d to represent both the travel time and the wait time (i.e., visiting the same vertex consecutively). We assume d(e(u,u))>0d(e(u,u))>0 as otherwise the agent may visit the same vertex infinitely many times. These modifications accommodate applications where rewards are not strictly one-time payments upon the first visit, but are instead accrued continually while occupying a vertex. This effectively models applications such as digital advertisements in shopping malls, where viewing duration by visitors is critical as time-varying rewards, and different visitors may arrive at the same location at different time intervals. Our experiments in Sec. 5 consider an agent in such scenarios. The objective of the agent Rtot(π)R_tot(π) is to maximize the expected total reward obtained by its policy π: Rtot(π)=V∼π[Rtot(V)]=V∼π[∑i=0n−1rtv(vi,Ti)],R_tot(π)= V πE[R_tot(V)]= V πE[ _i=0^n-1r_tv(v_i,T_i)], (7) where Ti=∑j=0i−1d(e(vj,vj+1))T_i= _j=0^i-1d(e(v_j,v_j+1)) is the timestep when the agent arrives at vertex viv_i, V is a path sampled according to the decisions of π, and n is the length of V. The objective function (Eq. (7)) is equivalent to Eq. (3) but with expectation over V, which depends on the choice of π. Note that OP-UTVR with known dynamics can be cast as a Markov decision process (MDP; Puterman 2014, Puterman 2014). Lemma 1. Assume P^=P P=P. An instance of OP-UTVR is an instance of an MDP. The optimal policy of this MDP can in principle be computed in advance by dynamic programming. This requires the true transition matrix P, which is unavailable in OP-UTVR. Figure 2: Solution overview. Left: observations (top row) refine predictions over time (lower rows). Badges A–C mark the information each planner uses. Right: (A) One-Step Planner maximizes immediate reward, (B) Offline Planner follows a precomputed multi-step plan, (C) Adaptive Online Planner updates both predictions and plans as observations arrive. 4 Planning Algorithms As illustrated in Fig. 2, we investigate three planning algorithms to solve OP-UTVR, named One-Step Planner, Offline Planner, and Adaptive Online Planner. These planners involve a policy π that selects a next vertex, i.e., vi+1=π(vi,…)v_i+1=π(v_i,...), and differ in how they utilize predicted time-varying rewards under uncertainty. In addition to these planners, Sec. 4.4 provides novel performance guarantees under the stochastic reward dynamics of OP-UTVR. 4.1 One-Step Planner One-Step Planner πone-stepπ^one-step decides the next vertex to visit upon arrival at each vertex viv_i, by greedily maximizing the predicted reward gained only at the next vertex without considering any future rewards (Fig. 2A). πone-step(vi,tv(Ti)) π^one-step(v_i,r_tv(T_i)) =argmaxu∈r^tv(u,d(e(vi,u))+Ti) = _u r_tv (u,d(e(v_i,u))+T_i ) =argmaxu∈[tv(Ti)P^d(e(vi,u))]u, = _u [r_tv(T_i) P^d(e(v_i,u)) ]_u, (8) where []u[x]_u denotes the entry of x corresponding to vertex u. 4.2 Offline Planner Offline Planner πofflineπ^offline computes a fixed plan in advance, i.e., a sequence of possibly overlapping vertices V0∗=(v0,v1,…)V^*_0=(v_0,v_1,...) maximizing the expected total reward under the time budget. Then, it traverses vertices following V0∗V^*_0, regardless of the observations during execution (Fig. 2B). πoffline(vi,Ti,tv(0)) π^offline(v_i,T_i,r_tv(0)) =vi+1, =v_i+1, whereV0∗=(v0,v1,…) \;V^*_0=(v_0,v_1,...) =argmaxV[∑j=0n−1r^tv(vj,Tj)|tv(0)] = _VE[ _j=0^n-1 r_tv(v_j,T_j)|r_tv(0)] (9) Offline Planner thus relies on the estimate of Eq. (5) and returns an optimal solution for a traditional OP with known static rewards. However, it is not necessarily optimal for OP-UTVR as rewards move nondeterministically over time. In addition, the probabilistic transition model P P is an estimate and is not the ground truth P. The estimation error accumulates over time steps, so the estimate would be increasingly unreliable over time. These issues motivate us to deploy an online approach that can adapt during execution. 4.3 Adaptive Online Planner The shortcoming of Offline Planner is that it only uses the observation of the reward tv(0)r_tv(0) at timestep 00 to estimate the total reward using Eq. (5) and decide the entire plan despite observing the true reward (tv(t)r_tv(t)) in the course of travel at timestep t. Instead, Adaptive Online Planner replans at each vertex arrival and estimates the total reward of the plan with the updated information of the reward (tv(t)r_tv(t)) using Eq. (6): πadapt(vi,Ti,tv(t)) π^adapt(v_i,T_i,r_tv(t)) =vi+1, =v_i+1, whereVi∗=(vi,vi+1,…) \;V^*_i=(v_i,v_i+1,...) =argmaxV[∑j=in−1r^tv(vj,Tj)|tv(Ti)] = _VE[ _j=i^n-1 r_tv(v_j,T_j)|r_tv(T_i)] (10) Figure 2C illustrates how Adaptive Online Planner works. Initially, the planner plans to visit vertex 1 while expecting to obtain a high reward at vertex 3 subsequently. Upon arrival at vertex 1, the planner updates the total reward (RadaptR_adapt) with the current observation, and replans to visit vertex 2, where the reward will be higher than in vertex 3. 4.4 Theoretical Analysis We present the first analysis that quantifies how prediction errors and reward stochasticity affect each planner. See Appendix A for the proofs. First, Adaptive Online Planner achieves the optimal policy π∗π^* of the MDP in Lemma 1 if P P equals the true P. Theorem 1. If the estimated reward transition P P has no error (i.e., P^=P P=P), Adaptive Online Planner achieves the optimal solution. This result implies that the difficulty of OP-UTVR reduces to model error, as replanning itself loses no optimality. The challenge of OP-UTVR is that the reward transition P is not given to the agent, and it has to be learned from demonstrations. Still, assuming the demonstrations are i.i.d. samples from the true distribution P, we can bound the suboptimality of Adaptive Online Planner as follows. Theorem 2. Assume the demonstrations are i.i.d. samples from P. Let rmaxr_max be the maximum reward obtainable at any vertex. Then, the expected total reward of Adaptive Online Planner using the empirical distribution as the estimated reward transition P P is bounded suboptimal as: |Rtot(π∗)−Rtot(πadapt)|≤2rmaxTmaxln(2||2/δ)2|D||R_tot(π^*)-R_tot(π^adapt)|≤ 2r_maxT_max (2|V|^2/δ)2|D| (11) with probability at least 1−δ1-δ, where |D||D| is the number of transition samples. The bound shrinks with more transition samples. Reward transition estimation is thus not a fundamental obstacle in OP-UTVR, unlike the reward stochasticity itself. The performance of Offline Planner compared to Adaptive Online Planner degrades when the reward transition P has stochasticity, as a fixed plan commits to expected rewards. Theorem 3. Assume P^=P P=P. Let rmaxr_max be the maximum reward obtainable at any vertex. Then, Rtot(πadapt)−Rtot(πoffline)≤rmaxTmax⋅Nln||2,R_tot(π^adapt)-R_tot(π^offline)≤ r_maxT_max· N |V|2, (12) where N is the number of reward objects with nondeterministic transitions. Here, a reward object is an individual reward source that moves between vertices according to P. Theorem 3 suggests that the advantage of adaptation grows with reward stochasticity. Section 5 examines this relationship empirically. 5 Experiments We develop a mobile service robot simulation to benchmark OP-UTVR. The simulation models a robot that navigates an environment to interact with people through activities such as displaying advertisements, gathering information, or monitoring pedestrians. The robot’s objective is to maximize the total number of interactions within a time budget. The environment contains several distinct spots where people tend to congregate. While the occupancy of each spot can be observed continuously, e.g., via surveillance camera networks (Fleuret et al. 2008), individual trajectories are complex and difficult to predict over long horizons. This setting requires the robot to handle uncertain time-varying rewards. 5.1 Mobile Service Robot Benchmark Environment construction. We build our benchmark on IR-SIM (Han et al. 2026), an open-source multi-agent crowd navigation simulator. Test environments come from the HM3D (Ramakrishnan et al. 2021) and Gibson (Xia et al. 2018) datasets, which provide scans of real-world indoor facilities such as offices and stores (Fig. 3). We evaluate planners on ten indoor environments, each 25 m × 25 m. Each environment has 13 gathering spots, i.e., the vertices V of the OP-UTVR tuple. Our formulation maps each pedestrian position to exactly one vertex (Sec. 3.1). We thus sample random points in the free space and define each gathering spot as the Voronoi region (Aurenhammer and Klein 2000) around each point (Fig. 5). For all pairs of gathering spots, we compute grid-based shortest paths using A∗ search, which are used during navigation for both the robot and pedestrians. We generate ten vertex placements per environment such that all spot pairs are connected, 100 test instances in total. Robot modeling. The robot is omnidirectional with a maximum velocity of 1.2 m/s. In planning, the travel time between spots, i.e., d of the OP-UTVR tuple, is computed assuming the robot moves along the shortest path at maximum velocity. At execution time, the robot follows the path to the target spot but uses the reciprocal velocity obstacles (RVO) model (van den Berg, Lin, and Manocha 2008) to avoid collisions with pedestrians. Thus, d only approximates the true travel time, which induces uncertainty as in practical robot navigation. The simulation runs in discrete steps of Δt=0.5 t=0.5 s, and each step updates robot control and pedestrian states. Pedestrian modeling. Each environment contains 20 pedestrians that transition stochastically between gathering spots according to a Markov chain with transition matrix P. We design P by randomly selecting one spot as the “entrance” where all pedestrians start. The remaining spots are evenly partitioned into two loops, and pedestrians enter either with probability 0.5 from the entrance. Within a loop, pedestrians move to the next spot with probability 0.75, skip one spot ahead with probability 0.05, or remain at the current spot with probability 0.2. This design creates stochastic crowd behaviors conditioned on latent intent (i.e., which group each pedestrian chooses). During execution, pedestrians move to their target spot along the pre-calculated shortest path at 1.0 m/s and use RVO to avoid collisions with other pedestrians and the robot. Interactions with the robot may change pedestrian behaviors from their transition patterns. Transition matrix estimation. To predict future rewards, the robot estimates P P from observed pedestrian trajectories. For each test instance, we collect 240 s of trajectory data without robot presence. Although these data follow the underlying rule defined by P, individual trajectories vary due to stochasticity. We estimate P P by fitting the gathered trajectory data using least-squares optimization. Figure 3: 3D views of example indoor environments from HM3D. We use bird’s-eye view maps from these scans. Figure 4: Statistical performance comparison of five planners across 100 instances (10 vertex placements × 10 maps). (a) Total reward. (b) Optimality gap relative to πoracleπ^oracle. (c) Reward-computation tradeoff, with points as instances and circles as means. Reward dynamics modeling. The reward rtv(v,t)r_tv(v,t) at each vertex is the number of pedestrians within the associated Voronoi region at time t. As described in Sec. 3.2, we allow d(e(v,v))>0d(e(v,v))>0 so that the robot can remain at a vertex. We set d(e(v,v))=5d(e(v,v))=5 s for all v∈v , and the robot collects rtv(vi,ti)r_tv(v_i,t_i) upon each arrival. 5.2 Evaluation Setup Planner implementation. For Offline Planner and Adaptive Online Planner, we compute solution paths using A∗ search (Hart, Nilsson, and Raphael 1968) over the expected rewards estimated via P^t P^t, with rewards treated as negative costs. For each partial path, branch-and-bound pruning (Land and Doig 1960) computes an upper bound on the remaining expected reward. This bound is used as the admissible heuristic of A∗, and branches whose bound cannot exceed the best solution are pruned. Adaptive Online Planner re-executes this search at each arrival. In addition to the three planners, we evaluate two baselines: 1) Greedy Planner (πgreedyπ^greedy), which selects the next vertex with the highest current pedestrian count without predicting future rewards, and 2) Oracle Planner (πoracleπ^oracle), which uses future pedestrian distributions from collected trajectory data and provides a coarse upper bound. πoracleπ^oracle replaces the optimal MDP policy (Lemma 1), which requires the true P and is not achievable in practice. Evaluation metrics. The following metrics assess each planner’s solution quality and computational efficiency: • Total reward (RtotR_tot) is the cumulative reward collected during execution, i.e., pedestrian encounters within TmaxT_max. • Optimality gap (Δopt _opt) [%] is computed as (Roracle−Rtot)/Roracle×100(R_oracle-R_tot)/R_oracle× 100, where RoracleR_oracle is the total reward of πoracleπ^oracle. This measures proximity to πoracleπ^oracle, though it is not a strict upper bound due to execution uncertainty. • Computation time (CTCT) [s] measures computational cost as total planning time in the course of execution. 5.3 Results Quantitative results. Figure 4 summarizes the performance of five planners across 100 test instances. πoracleπ^oracle achieves the highest total reward because it plans with true future pedestrian distributions (Fig. 4(a)). πgreedyπ^greedy, which relies on current observations, achieves the lowest total reward. All three proposed planners that leverage predicted reward dynamics outperform this baseline. This result validates our formulation, as planning with predicted reward dynamics is effective even when true dynamics remain unknown. Among the three planners, πadaptπ^adapt achieves the highest total reward in 64 cases, compared to 25 for πofflineπ^offline and 11 for πone-stepπ^one-step. Figure 4(b) shows their optimality gaps relative to πoracleπ^oracle. πone-stepπ^one-step has a 22.5% gap due to myopic decision-making, despite using updated observations. πofflineπ^offline reduces the gap to 8.9% by planning over the full time horizon, but its fixed plan cannot adapt to growing prediction errors. πadaptπ^adapt approaches the oracle with a 2.1% gap, as replanning keeps predictions up to date and prevents error accumulation (pairwise Wilcoxon signed-rank, Holm-corrected p<0.001p<0.001). These results suggest that effective planning combines long-horizon planning with runtime prediction updates. Figure 5: Snapshots of three planners for robot orienteering among pedestrians. RtotR_tot denotes the total reward at each snapshot. Voronoi cell colors indicate predicted rewards (warmer for higher values), with gray dashed boundaries. Annotations: black diamonds (graph vertices), dark gray (obstacles), cyan dot (robot), trajectory cyan-to-magenta over time, green dots (pedestrians). These performance differences come with tradeoffs in computational costs (Fig. 4(c)). πone-stepπ^one-step requires minimal computation as it only evaluates the immediate rewards of candidate next vertices. πofflineπ^offline involves moderate computation by solving the planning problem once at the start. πadaptπ^adapt demands the highest computation due to replanning, but achieves near-oracle performance. Beyond these general trends, we next examine individual planner behaviors. Qualitative results. Figure 5 compares trajectories of the three planners across three test instances, with snapshots at t=60t=60 and 180180 s. In Fig. 5(a), πadaptπ^adapt achieves a total reward of 184, while πofflineπ^offline and πone-stepπ^one-step obtain only 118 and 121, respectively (final values at t=240t=240 s; Fig. 5 shows snapshots). πofflineπ^offline repeatedly visits a few vertices, as its initial plan cannot adapt to reward dynamics. Its predictions also converge over time, so moving offers little expected gain. πone-stepπ^one-step responds to current observations but fails to collect high RtotR_tot due to optimizing only the next step. πadaptπ^adapt visits diverse vertices where pedestrians actually gather, by replanning with updated observations while optimizing over multiple steps. Figure 6: Environmental effect on planner performance. Point colors indicate maps. (a) Free space ratio vs. reward variance. (b) Reward variance vs. improvement of πadaptπ^adapt over πofflineπ^offline. Analysis of environmental effects. We quantify the relationship between environment geometry and planner performance for all instances using two metrics: free space ratio (0.34–0.53 across maps) and reward variance (temporal variance per vertex). Figure 6 shows that higher free space ratio correlates with greater reward variance (Pearson correlation, r=0.36r=0.36, p<0.001p<0.001), which increases the improvement of πadaptπ^adapt over πofflineπ^offline (r=0.29r=0.29, p<0.01p<0.01, measured as (Radapt−Roffline)/Roffline×100(R_adapt-R_offline)/R_offline× 100 [%]). Open spaces allow pedestrians to move freely, and rewards vary more over time. πofflineπ^offline follows a fixed plan and cannot adapt to these shifts, while πadaptπ^adapt updates its plan with new observations. Figure 5(b) and (c) illustrate this trend: πadaptπ^adapt leads in open spaces (194 vs. 135) while πofflineπ^offline outperforms in constrained spaces (241 vs. 193) (final values at t=240t=240 s). 6 Related Work OP and its variants. The OP selects and sequences vertex visits to maximize collected rewards under budget constraints (Tsiligirides 1984). As an NP-hard problem, OP has been extensively studied in operations research in terms of optimality (Fischetti, González, and Toth 1998), computational efficiency (Tang and Miller-Hooks 2005; Wang, Golden, and Wasil 2008), and scalability (Boussier, Feillet, and Gendreau 2007; Dang, Guibadj, and Moukrim 2013). Its abstract formulation readily extends to variants such as time-window constraints (Kantor and Rosenwein 1992) and team orienteering (Chao, Golden, and Wasil 1996). Robotic applications. This flexibility makes OP well-suited for robotics, where agents maximize task completion under resource constraints such as time or energy. For example, OP is extended to capture spatial correlations for environmental monitoring (Yu, Schwager, and Rus 2016), as nearby locations provide similar measurements. Peltzer et al. 2022 incorporates information gain into OP to prioritize areas that reduce map uncertainty for unknown terrain exploration. For search-and-rescue operations (Jorgensen and Pavone 2024), OP introduces survival constraints to account for the risk of agent loss. These examples show how robotics requires extending OP beyond its classical formulation. Uncertain/dynamic rewards. While most OP formulations assume static or known rewards, the real world is inherently uncertain and dynamic. Prior work addresses this through stochastic formulations or time-varying reward models. The former handle uncertainty by modeling stochastic travel costs with chance constraints (Carpin 2025) or rewards with probability distributions (Ilhan, Iravani, and Daskin 2008). However, these approaches assume that uncertainty follows known, stationary distributions. In contrast, time-varying reward models capture rewards that depend on location and visit time. Ma et al. 2017 introduced this formulation and solved it via dynamic programming on a spatio-temporal graph. Cao et al. 2024 improved computational efficiency with a heuristic search that guarantees optimality without explicit state spaces. Yet both methods require complete knowledge of future reward dynamics, an assumption rarely satisfied in practice. We combine both directions by considering time-varying rewards with uncertain dynamics. Relation to MDP. When future reward dynamics are unknown, one might formulate the problem as an MDP (Puterman 2014). While prior work has studied MDPs with changing rewards (Rivera Cardoso, Wang, and Xu 2019) or non-stationary dynamics (Cheung, Simchi-Levi, and Zhu 2020), such methods require learning both state transitions and reward functions. In our setting, agent transitions are deterministic and known, but only reward dynamics are uncertain. This allows us to learn only reward transitions rather than the entire MDP, which simplifies the learning problem. 7 Conclusion We presented OP-UTVR, a novel variant of the orienteering problem where rewards change stochastically and cannot be known in advance. Unlike prior work assuming known reward dynamics, our formulation allows agents to predict future reward transitions from observations. We investigated three planning algorithms and provided theoretical bounds on their performance. We also introduced a mobile service robot benchmark using real-world 3D scans. Experiments revealed trade-offs between planning horizon and adaptivity, and demonstrated the effectiveness of combining long-horizon planning with runtime observation updates. While we focused on Markovian dynamics in simulation, future directions include handling non-Markovian transitions, scaling to larger graphs, and validating with physical robots. References Aurenhammer and Klein (2000) Aurenhammer, F.; and Klein, R. 2000. Voronoi Diagrams, 201–290. North-Holland. Boussier, Feillet, and Gendreau (2007) Boussier, S.; Feillet, D.; and Gendreau, M. 2007. An Exact Algorithm for Team Orienteering Problems. 4OR, 5(3): 211–230. Cao et al. (2024) Cao, C.; Xu, J.; Zhang, J.; Choset, H.; and Ren, Z. 2024. Heuristic Search for the Orienteering Problem with Time-Varying Reward. In Proceedings of the International Symposium on Combinatorial Search, volume 17, 11–19. Carpin (2025) Carpin, S. 2025. Solving Stochastic Orienteering Problems with Chance Constraints Using Monte Carlo Tree Search. IEEE Transactions on Automation Science and Engineering, 22: 7855–7869. Chao, Golden, and Wasil (1996) Chao, I.-M.; Golden, B. L.; and Wasil, E. A. 1996. The Team Orienteering Problem. European Journal of Operational Research, 88(3): 464–474. Cheung, Simchi-Levi, and Zhu (2020) Cheung, W. C.; Simchi-Levi, D.; and Zhu, R. 2020. Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism. In Proceedings of the International Conference on Machine Learning, volume 119, 1843–1854. Dang, Guibadj, and Moukrim (2013) Dang, D.-C.; Guibadj, R. N.; and Moukrim, A. 2013. An Effective PSO-Inspired Algorithm for the Team Orienteering Problem. European Journal of Operational Research, 229(2): 332–344. Fischetti, González, and Toth (1998) Fischetti, M.; González, J. J. S.; and Toth, P. 1998. Solving the Orienteering Problem through Branch-and-Cut. INFORMS Journal on Computing, 10(2): 133–148. Fleuret et al. (2008) Fleuret, F.; Berclaz, J.; Lengagne, R.; and Fua, P. 2008. Multicamera People Tracking with a Probabilistic Occupancy Map. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(2): 267–282. Han et al. (2026) Han, R.; Wang, S.; Li, C.; Gao, R.; Wang, X.; Liu, Z.; Li, G.; Lu, Y.; Hao, Q.; Pan, J.; and Zhao, H. 2026. IR-SIM: A Lightweight Skill-Native Simulator for Navigation, Learning, and Benchmarking. arXiv preprint arXiv:2606.08729. Hart, Nilsson, and Raphael (1968) Hart, P. E.; Nilsson, N. J.; and Raphael, B. 1968. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2): 100–107. Hoeffding (1963) Hoeffding, W. 1963. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301): 13–30. Ilhan, Iravani, and Daskin (2008) Ilhan, T.; Iravani, S. M. R.; and Daskin, M. S. 2008. The Orienteering Problem with Stochastic Profits. IIE Transactions, 40(4): 406–421. Jorgensen and Pavone (2024) Jorgensen, S.; and Pavone, M. 2024. The Matroid Team Surviving Orienteers Problem and Its Variants: Constrained Routing of Heterogeneous Teams with Risky Traversal. The International Journal of Robotics Research, 43(1): 34–52. Kantor and Rosenwein (1992) Kantor, M. G.; and Rosenwein, M. B. 1992. The Orienteering Problem with Time Windows. Journal of the Operational Research Society, 43(6): 629–635. Land and Doig (1960) Land, A. H.; and Doig, A. G. 1960. An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28(3): 497–520. Ma et al. (2017) Ma, Z.; Yin, K.; Liu, L.; and Sukhatme, G. S. 2017. A Spatio-Temporal Representation for the Orienteering Problem with Time-Varying Profits. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 6785–6792. Peltzer et al. (2022) Peltzer, O.; Bouman, A.; Kim, S.-K.; Senanayake, R.; Ott, J.; Delecki, H.; Sobue, M.; Kochenderfer, M. J.; Schwager, M.; Burdick, J.; and Agha-mohammadi, A.-a. 2022. FIG-OP: Exploring Large-Scale Unknown Environments on a Fixed Time Budget. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 8754–8761. Puterman (2014) Puterman, M. L. 2014. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons. Ramakrishnan et al. (2021) Ramakrishnan, S. K.; Gokaslan, A.; Wijmans, E.; Maksymets, O.; Clegg, A.; Turner, J. M.; Undersander, E.; Galuba, W.; Westbury, A.; Chang, A. X.; Savva, M.; Zhao, Y.; and Batra, D. 2021. Habitat-Matterport 3D Dataset (HM3D): 1000 Large-Scale 3D Environments for Embodied AI. In Proceedings of the NeurIPS Datasets and Benchmarks Track. Rivera Cardoso, Wang, and Xu (2019) Rivera Cardoso, A.; Wang, H.; and Xu, H. 2019. Large Scale Markov Decision Processes with Changing Rewards. In Advances in Neural Information Processing Systems, volume 32. Tang and Miller-Hooks (2005) Tang, H.; and Miller-Hooks, E. 2005. A TABU Search Heuristic for the Team Orienteering Problem. Computers & Operations Research, 32(6): 1379–1407. Tsiligirides (1984) Tsiligirides, T. 1984. Heuristic Methods Applied to Orienteering. Journal of the Operational Research Society, 35(9): 797–809. van den Berg, Lin, and Manocha (2008) van den Berg, J.; Lin, M.; and Manocha, D. 2008. Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation. In Proceedings of the IEEE International Conference on Robotics and Automation, 1928–1935. Vansteenwegen, Souffriau, and Van Oudheusden (2011) Vansteenwegen, P.; Souffriau, W.; and Van Oudheusden, D. 2011. The Orienteering Problem: A Survey. European Journal of Operational Research, 209(1): 1–10. Wang, Golden, and Wasil (2008) Wang, X.; Golden, B. L.; and Wasil, E. A. 2008. Using a Genetic Algorithm to Solve the Generalized Orienteering Problem. In The Vehicle Routing Problem: Latest Advances and New Challenges, 263–274. Springer. Xia et al. (2018) Xia, F.; Zamir, A. R.; He, Z.; Sax, A.; Malik, J.; and Savarese, S. 2018. Gibson Env: Real-World Perception for Embodied Agents. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 9068–9079. Yu, Schwager, and Rus (2016) Yu, J.; Schwager, M.; and Rus, D. 2016. Correlated Orienteering Problem and Its Application to Persistent Monitoring Tasks. IEEE Transactions on Robotics, 32(5): 1106–1118. Appendix A Proofs We prove Theorems 1–3 and the supporting lemmas for the orienteering problem with uncertain time-varying rewards (OP-UTVR). A.1 Proof of Theorem 1 Theorem 1. If the estimated reward transition P P has no error (i.e., P^=P P=P), Adaptive Online Planner achieves the optimal solution. Proof. To show Theorem 1, we first prove the following lemma. Lemma 1. Assume P^=P P=P. An instance of OP-UTVR is an instance of a Markov decision process (MDP). Proof of Lemma 1. An MDP consists of a tuple (S,A,T,R)(S,A,T,R) (Puterman 2014). An MDP representing an instance of OP-UTVR can be constructed as follows. State space S: A state consists of the agent’s position v∈v , the current reward distribution tv∈ℝ≥1×||r_tv _≥^1×|V|, and the remaining time budget tremain∈[0,Tmax]t_remain∈[0,T_max]: s=(v,tv,tremain).s=(v,r_tv,t_remain). Action space A: The action space has size |||V|, where each action corresponds to selecting a vertex to travel to next. Transition function T: Given state s=(v,tv,tremain)s=(v,r_tv,t_remain) and action a∈a , the next state s′=(v′,tv′,tremain′)s =(v ,r _tv,t _remain) is determined as follows: v′ v =a, =a, (13) tv′ _tv ∼tvPd(e(v,a)), _tv\,P^d(e(v,a)), (14) tremain′ t _remain =tremain−d(e(v,a)). =t_remain-d(e(v,a)). (15) The agent’s position is deterministically updated to v′=av =a. The reward distribution evolves probabilistically according to the transition matrix P raised to the power of the travel time d(e(v,a))d(e(v,a)). The remaining time is decremented by the travel time. If tremain′≤0t _remain≤ 0, the system transitions to an absorbing terminal state. Reward function R: The agent receives reward rtv(v,t)r_tv(v,t) upon arriving at vertex v at timestep t. The policy of this MDP corresponds exactly to the policy in OP-UTVR, and the expected total rewards of the two formulations coincide. Therefore, OP-UTVR is an instance of an MDP. ∎ By Lemma 1, when P^=P P=P, OP-UTVR is an MDP with known transition dynamics. The optimal policy of an MDP selects, at each state, the action that maximizes the expected total reward. It can be obtained via dynamic programming or policy iteration. Adaptive Online Planner defined in Sec. 4 (Eq. (10)) computes exactly this: at each state, it selects the action (next vertex) that maximizes the expected total reward given the current observations. Therefore, Adaptive Online Planner achieves the optimal solution when P^=P P=P, which proves Theorem 1. ∎ A.2 Proof of Theorem 2 Theorem 2. Assume the demonstrations are i.i.d. samples from P. Let rmaxr_max be the maximum reward obtainable at any vertex. Then, the expected total reward of Adaptive Online Planner using the empirical distribution as the estimated reward transition P P is bounded suboptimal as: |Rtot(π∗)−Rtot(πadapt)|≤2rmaxTmaxln(2||2/δ)2|D||R_tot(π^*)-R_tot(π^adapt)|≤ 2r_maxT_max (2|V|^2/δ)2|D| (16) with probability at least 1−δ1-δ, where |D||D| is the number of transition samples. Proof. To show Theorem 2, we first prove the following lemma. Lemma 2. Suppose ‖P^−P‖∞≤ϵ\| P-P\|_∞≤ε, where ∥⋅∥∞\|·\|_∞ denotes the max-norm: ‖M‖∞=maxu,v|Mu,v|\|M\|_∞= _u,v|M_u,v|. Let rmaxr_max be the maximum reward obtainable at any vertex. Then, |Rtot(π∗)−Rtot(πadapt)|≤2ϵrmaxTmax.|R_tot(π^*)-R_tot(π^adapt)|≤ 2ε r_maxT_max. (17) Proof of Lemma 2. Let VPπ(s)V^π_P(s) denote the expected total reward when following policy π under true dynamics P, starting from state s. Similarly, let VP^π(s)V^π_ P(s) denote the expected total reward under estimated dynamics P P. By the Bellman equation for finite-horizon MDPs, for any policy π and state s=(v,tv,tremain)s=(v,r_tv,t_remain) with tremain>0t_remain>0: VPπ(s) V^π_P(s) =rtv(v)+s′∼TP(s,π(s))[VPπ(s′)], =r_tv(v)+E_s T_P(s,π(s))[V^π_P(s )], (18) VP^π(s) V^π_ P(s) =rtv(v)+s′∼TP^(s,π(s))[VP^π(s′)], =r_tv(v)+E_s T_ P(s,π(s))[V^π_ P(s )], (19) where TPT_P and TP^T_ P are the transition functions under P and P P, respectively. The difference in value functions can be bounded recursively. For a single timestep: |VPπ(s)−VP^π(s)| |V^π_P(s)-V^π_ P(s)| ≤|s′∼TP[VPπ(s′)]−s′∼TP^[VP^π(s′)]| ≤ |E_s T_P[V^π_P(s )]-E_s T_ P[V^π_ P(s )] | (20) ≤|s′∼TP[VPπ(s′)]−s′∼TP[VP^π(s′)]| ≤ |E_s T_P[V^π_P(s )]-E_s T_P[V^π_ P(s )] | (21) +|s′∼TP[VP^π(s′)]−s′∼TP^[VP^π(s′)]|. + |E_s T_P[V^π_ P(s )]-E_s T_ P[V^π_ P(s )] |. (22) The first term bounds the recursive error in value estimation. The second term captures the error due to transition mismatch. Since rewards are bounded by rmaxr_max, the maximum value function is bounded by rmaxTmaxr_maxT_max. The transition error ‖P^−P‖∞≤ϵ\| P-P\|_∞≤ε implies that the distribution over next states differs by at most ϵε in total variation distance. Therefore: |s′∼TP[VP^π(s′)]−s′∼TP^[VP^π(s′)]|≤ϵrmaxTmax. |E_s T_P[V^π_ P(s )]-E_s T_ P[V^π_ P(s )] |≤ε r_maxT_max. (23) Unrolling this recursion over TmaxT_max steps yields: |VPπ(s)−VP^π(s)|≤ϵrmaxTmax.|V^π_P(s)-V^π_ P(s)|≤ε r_maxT_max. (24) Now, π∗π^* is optimal under P, and πadaptπ^adapt is optimal under P P (by Theorem 1). Therefore: Rtot(π∗)− R_tot(π^*)- Rtot(πadapt)=VPπ∗(s0)−VPπadapt(s0) R_tot(π^adapt)=V^π^*_P(s_0)-V^π^adapt_P(s_0) (25) ≤VPπ∗(s0)−VP^πadapt(s0) ≤ V^π^*_P(s_0)-V^π^adapt_ P(s_0) +VP^πadapt(s0)−VPπadapt(s0) +V^π^adapt_ P(s_0)-V^π^adapt_P(s_0) (26) ≤VPπ∗(s0)−VP^πadapt(s0)+ϵrmaxTmax. ≤ V^π^*_P(s_0)-V^π^adapt_ P(s_0)+ε r_maxT_max. (27) Since πadaptπ^adapt is optimal under P P, we have VP^πadapt(s0)≥VP^π∗(s0)V^π^adapt_ P(s_0)≥ V^π^*_ P(s_0). Thus: VPπ∗(s0)−VP^πadapt(s0) V^π^*_P(s_0)-V^π^adapt_ P(s_0) ≤VPπ∗(s0)−VP^π∗(s0)≤ϵrmaxTmax. ≤ V^π^*_P(s_0)-V^π^*_ P(s_0)≤ε r_maxT_max. (28) Combining these bounds: |Rtot(π∗)−Rtot(πadapt)|≤2ϵrmaxTmax.|R_tot(π^*)-R_tot(π^adapt)|≤ 2ε r_maxT_max. (29) ∎ Let P P be the empirical transition matrix estimated from |D||D| i.i.d. transition samples. For each pair (u,v)∈×(u,v) ×V, the empirical estimate P^u,v P_u,v is the sample mean of Bernoulli trials (whether a transition from u lands at v). By Hoeffding’s inequality (Hoeffding 1963), for any fixed (u,v)(u,v): Pr(|Pu,v−P^u,v|>ϵ)≤2exp(−2|D|ϵ2). (|P_u,v- P_u,v|>ε)≤ 2 (-2|D|ε^2). (30) Applying a union bound over all ||2|V|^2 entries: Pr(‖P^−P‖∞>ϵ)≤2||2exp(−2|D|ϵ2). (\| P-P\|_∞>ε)≤ 2|V|^2 (-2|D|ε^2). (31) Setting the right-hand side equal to δ and solving for ϵε: 2||2exp(−2|D|ϵ2) 2|V|^2 (-2|D|ε^2) =δ =δ (32) ϵ ε =ln(2||2/δ)2|D|. = (2|V|^2/δ)2|D|. (33) Therefore, with probability at least 1−δ1-δ: ‖P^−P‖∞≤ln(2||2/δ)2|D|.\| P-P\|_∞≤ (2|V|^2/δ)2|D|. (34) Combining with Lemma 2, we obtain: |Rtot(π∗)−Rtot(πadapt)|≤2rmaxTmaxln(2||2/δ)2|D|,|R_tot(π^*)-R_tot(π^adapt)|≤ 2r_maxT_max (2|V|^2/δ)2|D|, (35) which completes the proof of Theorem 2. ∎ A.3 Proof of Theorem 3 Theorem 3. Assume P^=P P=P. Let rmaxr_max be the maximum reward obtainable at any vertex. Then, Rtot(πadapt)−Rtot(πoffline)≤rmaxTmax⋅Nln||2,R_tot(π^adapt)-R_tot(π^offline)≤ r_maxT_max· N |V|2, (36) where N is the number of reward objects with nondeterministic transitions. Proof. Let Xvv∈\X_v\_v be random variables representing rewards at different vertices at some future timestep. Lemma 3. For Adaptive Online Planner, the expected reward per step is [maxv∈Xv]E[ _v X_v]. For Offline Planner, the expected reward per step is at most maxv∈[Xv] _v E[X_v]. Therefore: [maxv∈Xv]−maxv∈[Xv]≥0.E [ _v X_v ]- _v E[X_v]≥ 0. (37) Proof of Lemma 3. Let v∗=argmaxv[Xv]v^*= _vE[X_v]. Then: [maxv∈Xv] [ _v X_v ] ≥[Xv∗] [X_v^*] (38) =maxv∈[Xv]. = _v E[X_v]. (39) ∎ Assume there are N independent reward objects, each following stochastic transitions according to P. Each object contributes a reward in [0,rmax][0,r_max] when collected. At any timestep t, let Yi(v)∈[0,rmax]Y_i^(v)∈[0,r_max] denote the reward from object i if it is located at vertex v, and 00 otherwise. The total reward at vertex v is: Xv=∑i=1NYi(v).X_v= _i=1^NY_i^(v). (40) Since each object transitions independently according to P, the Yi(v)Y_i^(v) are independent random variables. Let pv=Pr(object i is at vertex v)p_v= (object i is at vertex v) be the probability that object i is at vertex v. Then: [Xv]≤Nrmaxpv.E[X_v]≤ Nr_maxp_v. (41) For the maximum of |||V| independent sums (one per vertex), we have the following lemma using a concentration inequality. Lemma 4. For independent random variables bounded in [0,Nrmax][0,Nr_max], the gap between the expectation of the maximum and the maximum of expectations satisfies: [maxv∈Xv]−maxv∈[Xv]≤rmaxNln||2.E [ _v X_v ]- _v E[X_v]≤ r_max N |V|2. (42) Proof of Lemma 4. Let v∗=argmaxv[Xv]v^*= _vE[X_v] and let μ=[Xv∗]μ=E[X_v^*]. For any vertex v, by Hoeffding’s inequality applied to the sum Xv=∑i=1NYi(v)X_v= _i=1^NY_i^(v) where each Yi(v)∈[0,rmax]Y_i^(v)∈[0,r_max]: Pr(Xv−[Xv]≥t)≤exp(−2t2Nrmax2). (X_v-E[X_v]≥ t)≤ (- 2t^2Nr_max^2 ). (43) Therefore: Pr(maxvXv≥μ+t) ( _vX_v≥μ+t ) ≤∑v∈Pr(Xv≥μ+t) ≤ _v (X_v≥μ+t) (44) ≤∑v∈Pr(Xv−[Xv]≥t) ≤ _v (X_v-E[X_v]≥ t) (45) ≤||exp(−2t2Nrmax2). ≤|V| (- 2t^2Nr_max^2 ). (46) Let Z=maxvXv−μZ= _vX_v-μ. Then: [Z] [Z] =∫0∞Pr(Z≥t)t = _0^∞ (Z≥ t)\,dt (47) ≤∫0∞min(1,||exp(−2t2Nrmax2))t. ≤ _0^∞ (1,|V| (- 2t^2Nr_max^2 ) )dt. (48) Setting t0=rmaxNln||2t_0=r_max N |V|2 as the point where the exponential becomes small: [Z] [Z] ≤t0+∫t0∞||exp(−2t2Nrmax2)t ≤ t_0+ _t_0^∞|V| (- 2t^2Nr_max^2 )dt (49) ≤rmaxNln||2+(1) ≤ r_max N |V|2+O(1) (50) ≤rmaxNln||2(for sufficiently large ||). ≤ r_max N |V|2 (for sufficiently large $| V|$). (51) ∎ By Lemma 4, the gap per timestep is at most rmax⋅Nln||/2r_max· N |V|/2. Over TmaxT_max timesteps, the total gap is bounded by: Rtot(πadapt)−Rtot(πoffline)≤rmaxTmax⋅Nln||2.R_tot(π^adapt)-R_tot(π^offline)≤ r_maxT_max· N |V|2. (52) ∎ Corollary 1. If P is deterministic, then Rtot(πadapt)=Rtot(πoffline).R_tot(π^adapt)=R_tot(π^offline). (53) Proof. With P being deterministic, the value of XvX_v is fixed for any trials. Thus, [maxvXv]=maxv[Xv]E[ _vX_v]= _vE[X_v]. ∎ Appendix B Experimental Details All experiments were run on CPUs (8 CPU cores, 30 GB RAM) and require no GPU. The implementation is written in Python 3.12, and exact dependency versions are included with our code. Table 1 lists the parameters used in our experiments; see Sec. 5.1 for the design of the transition matrix P. All parameters were fixed a priori as benchmark design choices rather than tuned via hyperparameter search. These values are based on realistic service-robot settings, such as the robot and pedestrian velocities. Table 1: Experimental parameters. Parameter Value Environment size 25 m × 25 m Number of environments (maps) 10 Vertex placements per environment 10 Gathering spots per environment (|||V|) 13 Number of pedestrians (N) 20 Time budget (TmaxT_max) 240 s Simulation timestep (Δt t) 0.5 s Waiting time (d(e(v,v))d(e(v,v))) 5 s Robot maximum velocity 1.2 m/s Pedestrian velocity 1.0 m/s Transition prob. (next / skip / stay) 0.75 / 0.05 / 0.2 Prob. of entering each loop 0.5