Paper deep dive
Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees
Mansur M. Arief, Ali Akarma, Ahmad Alfan Alfian Irfan
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/19/2026, 5:21:21 AM
Summary
This paper introduces DORA (Dijkstra Oracle Reduced-cost Algorithm), an online learning method for robot navigation in stochastic environments. It demonstrates that Dijkstra's algorithm can serve as an exact planning engine for stochastic shortest path problems if the reduced costs on the determinized map are nonnegative, a condition weaker than traditional causality. DORA leverages this by iteratively updating cost estimates and calling Dijkstra, avoiding explicit transition kernel estimation. The method achieves performance comparable to optimistic value iteration with significantly lower computational cost and improved safety constraints via a chance-constrained variant.
Entities (8)
Relation Signals (7)
DORA → uses → Dijkstra's algorithm
confidence 98% · DORA... calls a shortest path oracle... Building on this characterization, an online learner DORA... is proposed
DORA → reliesoncondition → Reduced Cost
confidence 96% · Dijkstra's algorithm can remain an exact planning engine under a condition... namely nonnegativity of a reduced cost
DORA-S → isvariantof → DORA
confidence 95% · We call this variant DORA-S.
DORA → solves → Stochastic Shortest Path
confidence 95% · DORA... is proposed for robot navigation... solves the underlying stochastic shortest path problem
Reduced Cost → isweakerthan → Causality Condition
confidence 94% · condition that is much weaker than the causality condition... nonnegativity of a reduced cost... is strictly weaker than the causality condition
DORA-S → handles → Chance Constraints
confidence 93% · adds a logarithmic survival weight when the probability of contact with a dynamic obstacle must stay within a budget
DORA → outperforms → Value Iteration
confidence 90% · the learner matches optimistic value iteration... while performing 4.5 to 19.3 times less planner work
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Mobile robots that operate in side by side with humans and critical facilities must reach their goals at low cost, despite often unknown true traversal costs of the map apriori and imperfect actuation. Planners that solve the underlying stochastic shortest path problem exactly, such as value iteration, require computation that grows with the diameter of the map, whereas Dijkstra's algorithm is fast but is usually considered inexact once transitions are stochastic. This study shows that Dijkstra's algorithm can remain an exact planning engine under a condition that is much weaker than the causality condition often invoked in the literature, namely nonnegativity of a reduced cost defined on the determinized map. Building on this characterization, an online learner DORA (Dijkstra Oracle Reduced-cost Algorithm) is proposed for robot navigation that calls a shortest path oracle a fixed number of times per episode, never estimates a transition kernel, and adds a logarithmic survival weight when the probability of contact with a dynamic obstacle must stay within a budget. In the numerical experiments involving three other benchmarks that cover grid world navigation, directional drilling, and drone surveillance, the learner matches optimistic value iteration that is given the true transition kernel while performing 4.5 to 19.3 times less planner work, reduces contacts during learning by a factor of seventeen relative to determinize and replan, and keeps the contact rate within budgets that span two orders of magnitude. These results indicate that shortest path search supports safe and efficient online navigation and path planning tasks.
Tags
Links
- Source: https://arxiv.org/abs/2608.17703v1
- Canonical: https://arxiv.org/abs/2608.17703v1
Trouble viewing inline? Open PDF directly →
Full Text
63,128 characters extracted from source content.
Expand or collapse full text
Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees Mansur Arief Affiliation: Industrial and Systems Engineering Department, IRC Smart Mobility and Logistics, King Fahd University of Petroleum and Minerals (KFUPM), Saudi Arabia. Email: mansur.arief@kfupm.edu.sa Ali Akarma Affiliation: Faculty of Computer and Information Systems, Islamic University of Madinah, Saudi Arabia. Email: 443059463@stu.iu.edu.sa Ahmad Alfan Alfian Irfan Thanks: $ˆ†$This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. Thanks: $ˆ*$The code is available online at https://github.com/ai-vnv/DORASolvers.jl Affiliation: Information Technology, Universitas Muhammadiyah Yogyakarta, Indonesia. Email: ahmad.alfan.ft23@mail.umy.ac.id Abstract Mobile robots that operate in side by side with humans and critical facilities must reach their goals at low cost, despite often unknown true traversal costs of the map apriori and imperfect actuation. Planners that solve the underlying stochastic shortest path problem exactly, such as value iteration, require computation that grows with the diameter of the map, whereas Dijkstra’s algorithm is fast but is usually considered inexact once transitions are stochastic. This study shows that Dijkstra’s algorithm can remain an exact planning engine under a condition that is much weaker than the causality condition often invoked in the literature, namely nonnegativity of a reduced cost defined on the determinized map. Building on this characterization, an online learner DORA (Dijkstra Oracle Reduced-cost Algorithm) is proposed for robot navigation that calls a shortest path oracle a fixed number of times per episode, never estimates a transition kernel, and adds a logarithmic survival weight when the probability of contact with a dynamic obstacle must stay within a budget. In the numerical experiments involving three other benchmarks that cover grid world navigation, directional drilling, and drone surveillance, the learner matches optimistic value iteration that is given the true transition kernel while performing 4.5 to 19.3 times less planner work, reduces contacts during learning by a factor of seventeen relative to determinize and replan, and keeps the contact rate within budgets that span two orders of magnitude. These results indicate that shortest path search supports safe and efficient online navigation and path planning tasks. Index Terms: Stochastic shortest path, online learning, robot navigation, planning under uncertainty, warehouse automation. I Introduction Autonomous and service robots often deal with problems involving known maps and goals, and the robot must reach the goal at low cost while avoiding contact with obstacles and people [30, 40, 29]. Under such a setting, what is not known in advance is how expensive each part of the map really is. Floor condition, local clutter and foot traffic all change the effective cost of a route, and they are learned in real-time only by traversing. The robot must therefore improve its routing policy online while it continues to operate. In the literature, we often cast this setting as a stochastic shortest path problem, or SSP [4]. Key characteristics include actuation being imperfect, so a commanded move sometimes slips and contact with a dynamic obstacle ends the task. Value iteration and its heuristic search variants solve such problems to optimality [18, 8], and recent work has established minimax regret rates for learning them online [36, 11, 39]. However, the difficulty is usually computational. Value iteration propagates information one step per sweep, so the number of sweeps needed grows with the diameter of the graph. A robot that replans at every cycle incurs this compute cost every cycle. Meanwhile, Dijkstra’s algorithm [15] has the opposite profile. A single pass propagates cost information across the entire map, and the run time is near linear in the number of edges. It is also the workhorse of deployed navigation stacks [30, 28]. The usual objection is that it does not apply to stochastic problems. The classical condition for a one pass label setting method to be exact is that an optimal policy is consistently improving, meaning the value strictly decreases along every transition that has positive probability [41, 16]. As soon as an actuator slips sideways into a more expensive region, that condition fails. As shown in later sections, our analysis shows that this objection is stated too strongly. The minimal condition is nonnegativity of a reduced cost. To see this, for each state and action, define the reduced cost as the state action value of the stochastic problem minus the value of the state the action was intended to reach. If these quantities are nonnegative, then running Dijkstra with them as edge weights returns exactly the optimal value function and exactly the optimal policy. That said, the reduced cost is nonnegative under a much weaker requirement than causality, because it only constrains the determinized edge, not the slip outcomes. In our study the classical causality condition holds at about half of the states with the slip present, while the reduced costs remain non-negative on state-action pairs up to a slip probability of 0.300.30. This observation suggests an algorithm. The reduced costs are unknown, but they have a self consistent form: the reduced cost is the learned step cost plus the expected change in cost to goal caused by slip. We therefore iterate. Given a current estimate of the cost to goal, we form the reduced cost weights, call Dijkstra, and use the returned labels to update the estimate. A small number of damped iterations is enough. The result is the proposed Dijkstra Oracle Reduced-cost Algorithm (DORA). DORA maintains optimistic estimates of the |||||S||A| traversal costs and never estimates a transition kernel, which would require ||2|||S|^2|A| parameters. Our contributions are threefold. First, we characterize when the policy class induced by Dijkstra contains an optimal policy for a stochastic shortest path problem. The condition is nonnegativity of a reduced cost on the determinized map, and it is strictly weaker than the causality condition used in the label setting literature. Second, we introduce DORA, an online learner that reaches this class using a fixed number of shortest path oracle calls per episode and no transition model, together with a chance constrained variant that enforces a risk budget through an additive log survival weight. Third, we evaluate the method on a warehouse navigation benchmark. DORA matches optimistic value iteration supplied with the true kernel while doing an order of magnitude less planner work, and it reduces contacts during learning by a factor of seventeen relative to plain determinize and replan. The same advantages hold on three further navigation benchmarks. The remainder of the paper is organized as follows. Section I reviews the related work. Section I states the problem. Section IV develops the reduced cost characterization and the algorithm. Section V reports the experiments. Section VI discusses the findings, and Section VII concludes. I Related Work I-A Shortest Path Search for Robot Navigation Graph search is the standard planning layer in mobile robotics. D* Lite reuses information across a sequence of searches and returns the same optimal path that A* [20] would return on the current cost map [23]. ARA* attaches an explicit suboptimality factor to every anytime solution [26], and Anytime D* combines the two while preserving the bound [25]. These methods assume deterministic transitions. When transitions are stochastic the solution is a policy rather than a path, and LAO* extends heuristic search to solution graphs with loops [18]. Labeled real-time dynamic programming adds a convergence bound that the plain counterpart is lacking [8]. The idea of using Dijkstra on a stochastic problem is not new. McMahan and Gordon generalize Dijkstra and Gaussian elimination into a family of exact MDP solvers that reduce to Dijkstra when the transitions are deterministic [31]. Bounded real time dynamic programming uses a Dijkstra sweep to build a monotone initial bound [32]. Topological value iteration performs label setting at the granularity of strongly connected components [12, 13]. Bertsekas develops a Dijkstra like algorithm for robust shortest paths under a semicontractive model [5]. The exactness conditions for one pass label setting on stochastic problems were established by Vladimirsky, who requires a consistently improving optimal policy [41], and sharpened by Gaspard and Vladimirsky, who give explicit cost conditions and an explicit counterexample when the condition is violated [16]. Our contribution is to show that a weaker condition, stated on reduced costs, rather than on raw values, is what governs whether Dijkstra-derived policies are lossless. I-B Online Learning for Goal Oriented Problems Regret guarantees for stochastic shortest path learning have advanced quickly. UC-SSP gave the first no regret algorithm without restrictive assumptions [38], near optimal bounds in terms of the optimal cost to go followed [36], and the minimax rate was settled by two concurrent works [11, 39]. Policy optimization for this setting was initiated by Chen, Luo and Rosenberg [9], and Chen et al. [10] proved that horizon free regret is impossible under general costs. All of these algorithms plan by value iteration or by optimization over occupancy measures, and none treats a combinatorial planner as a black box oracle. Oracle-based learners are standard in online combinatorial optimization, where following the perturbed leader calls an offline solver on perturbed costs [22], but that line assumes deterministic edges. We place a shortest path oracle inside a learner for a stochastic shortest path problem. I-C Determinization and the Price of Structure Replanning with a determinized model is a strong practical baseline in probabilistic planning [42]. Little and Thiébaux [27] showed by construction that the policy induced by the most likely trajectory can be exponentially worse than optimal, and later work on reduced models states plainly that little can be guaranteed about the quality of plans produced by replanners [35]. Hansen [19] gives an a posteriori suboptimality bound for stochastic shortest path in which the expected time to absorption replaces the discount amplifier. Our experiments show that this bound is vacuous at realistic slip levels, while the actual gap of the reduced cost member of the class is zero. The picture that emerges is that determinization is not intrinsically lossy. What is lossy is weighting the determinized graph by expected one step cost. I-D Safe Navigation under Uncertainty Chance constrained planning allocates a risk budget across constraints and solves a tightened deterministic problem [34]. RAO* searches belief states with admissible bounds on both utility and execution risk and returns optimal policies that satisfy the chance constraint [37]. FIRM makes edge costs independent in belief space so that the optimal substructure needed by graph search is restored [1]. In probabilistic verification, weighting each edge by the negative logarithm of its probability turns a most probable violating path into a shortest path [17]. Our chance constrained variant uses the same transformation on the planning side. Related work also shows that a deterministic solver used as a black box suffices for several risk objectives with only a logarithmic number of calls [33], and that a budget of uncertainty costs at most n+1n+1 nominal solves [6]. I Problem Formulation We model navigation as a stochastic shortest path problem M=(,,P,c,s0,g)M=(S,A,P,c,s_0,g). The state set S contains the free cells of a known occupancy map together with an absorbing crash state, and A contains four motion primitives. The robot starts at s0s_0 and must reach the goal g. Transitions are stochastic because actuation is imperfect. A commanded action a moves the robot to its intended successor with probability 1−ε1- and slips to one of the two lateral cells with probability ε/2 /2 each. A slip into a shelf stops the robot in place and incurs a bump cost. Entering a cell that is occupied by a dynamic obstacle sends the robot to the crash state, which carries a known dead end penalty. The traversal cost c(s,a)c(s,a) is unknown. At each step the robot observes a noisy sample of it. Costs are bounded below by cmin>0c_ >0 and above by cmaxc_ . We write c¯(s,a) c(s,a) for the true mean cost. The value of a stationary policy π is the expected cost accumulated before absorption, truncated at a horizon H with a timeout penalty, and V⋆V is the optimal value. We write Q⋆(s,a)=c¯(s,a)+∑s′P(s′|s,a)V⋆(s′).Q (s,a)= c(s,a)+ _s P(s |s,a)V (s ). (1) The map geometry gives a determinized graph. Let σ(s,a)σ(s,a) denote the cell that action a is intended to reach from s, and let E be the set of pairs for which this is defined. We make the following standing assumptions, which hold for any connected occupancy map. Assumption 1. The goal g is reachable from every state along determinized edges, and c(s,a)∈[cmin,cmax]c(s,a)∈[c_ ,c_ ] with cmin>0c_ >0. The learner interacts for K episodes. In episode k it commits to a stationary policy πk _k, executes it until absorption or timeout, and updates its estimates. We measure performance by the regret RK=∑k=1K(Jπk(s0)−V⋆(s0)),R_K= _k=1^K (J _k(s_0)-V (s_0) ), (2) by the success, contact and timeout rates of the executed policy, and by the work performed by the planner per episode. Work is counted in elementary operations, namely edge scans for a shortest path call and successor evaluations for a value iteration sweep. We report work rather than wall clock so that the comparison does not depend on how each planner is implemented. IV Method IV-A The Dijkstra Policy Class Any nonnegative weight vector on the determinized graph induces a policy. Definition 1. For w∈ℝ≥0Ew _≥ 0^E let dwd_w solve dw(s)=minaw(s,a)+dw(σ(s,a))d_w(s)= _a\w(s,a)+d_w(σ(s,a))\ with dw(g)=0d_w(g)=0, and let πw(s)=argminaw(s,a)+dw(σ(s,a)) _w(s)= _a\w(s,a)+d_w(σ(s,a))\. The Dijkstra policy class is Πσ=πw:w∈ℝ≥0E _σ=\ _w:w _≥ 0^E\. Under Assumption 1 the labels dwd_w are the unique solution of that system and Dijkstra computes them in O(|E|+||log||)O(|E|+|S| |S|) time. Note that a single backward call from the goal returns a policy defined at every state, not a single path, so the robot may be displaced by a slip and still act greedily without replanning. Furthermore, the class is finite with cardinality at most |||||A|^|S|, so it cannot be searched by enumeration. The oracle searches it implicitly. IV-B Reduced Costs and Exactness The natural choice w=c¯w= c is the one often used by determinize and replan planners [42]. However, the right choice is a reduced cost defined in Definition 2 and shown to be exact in Proposition 1. Definition 2. The reduced cost of (s,a)∈E(s,a)∈ E is w⋆(s,a)=Q⋆(s,a)−V⋆(σ(s,a)).w (s,a)=Q (s,a)-V (σ(s,a)). (3) Proposition 1 (Exact representation). Suppose Assumption 1 holds and w⋆(s,a)≥0w (s,a)≥ 0 for all (s,a)∈E(s,a)∈ E. Then dw⋆=V⋆d_w =V and πw⋆ _w is an optimal policy for M. In particular, Πσ _σ contains an optimal policy and Dijkstra recovers it in one call. Proof. By the Bellman equation and (3), minaw⋆(s,a)+V⋆(σ(s,a))=minaQ⋆(s,a)=V⋆(s), _a\w (s,a)+V (σ(s,a))\= _aQ (s,a)=V (s), and V⋆(g)=0V (g)=0. So V⋆V solves the determinized fixed point system of Definition 1 with weights w⋆w . Under Assumption 1 and w⋆≥0w ≥ 0 that system has a unique solution, hence dw⋆=V⋆d_w =V . The greedy action then satisfies argminaw⋆(s,a)+dw⋆(σ(s,a))=argminaQ⋆(s,a) _a\w (s,a)+d_w (σ(s,a))\= _aQ (s,a), which is optimal. ∎ The condition in Proposition 1 is weaker than the condition used in the label-setting literature [41, 16]. A policy is consistently improving when V⋆(s)>V⋆(s′)V (s)>V (s ) for every s′s with P(s′|s,π⋆(s))>0P(s |s,π (s))>0, which constrains all slip outcomes [41, 16]. We thus have Proposition 2. Proposition 2 (Relation to causality). At the optimal action, w⋆(s,π⋆(s))=V⋆(s)−V⋆(σ(s,π⋆(s)))w (s,π (s))=V (s)-V (σ(s,π (s))). Hence nonnegativity of the reduced cost at the optimal action is exactly the causality condition restricted to the determinized edge, and it is implied by, but does not imply, consistent improvement. Proof. Q⋆(s,π⋆(s))=V⋆(s)Q (s,π (s))=V (s) by optimality, and substitution into (3) gives the identity. Consistent improvement requires a strict decrease on all positive probability successors, of which the determinized successor is one, so it implies the stated inequality. The converse fails because a lateral slip may raise the value without affecting w⋆w . ∎ This distinction explains the empirical picture reported in Section V. Slip breaks causality immediately, because some lateral outcome always lands in a more expensive region. It does not break nonnegativity of the reduced cost, because a step still costs at least cminc_ and still makes progress toward the goal in the determinized graph. IV-C The DORA Algorithm The reduced costs are unknown, but (3) can be written in a self consistent form. Substituting the definition of Q⋆Q , w⋆(s,a)=c¯(s,a)+∑s′P(s′|s,a)V⋆(s′)−V⋆(σ(s,a))⏟drift.w (s,a)= c(s,a)+ _s P(s |s,a)V (s )-V (σ(s,a))_drift. (4) The drift term is the expected penalty for not landing where the action intended. It requires the actuation model, which is a single calibrated scalar ε together with the known map geometry, and it requires an estimate of the cost to goal, which the oracle itself returns. DORA therefore alternates between forming the weights and calling the oracle. Let c^k c_k be the empirical mean cost, bk(s,a)=βlog(2||||K/δ)max(Nk(s,a),1)b_k(s,a)=β (2|S||A|K/δ) (N_k(s,a),1) (5) be a confidence radius, and wkbase=max(cmin,c^k−bk)w^base_k= (c_ , c_k-b_k) (6) be the optimistic step cost. Given a current label vector d, the algorithm forms (w(s,a))+ (w(s,a) )^+ where w(s,a)=wkbase(s,a)+∑s′P^(s′|s,a)d(s′)−d(σ(s,a)),w(s,a)=w^base_k(s,a)+ _s P(s |s,a)d(s )-d(σ(s,a)), (7) calls Dijkstra, and updates d by a damped step with parameter α. Note here that the clipping at zero is required because the oracle needs nonnegative weights, and it is inactive whenever Proposition 1 applies. The full procedure is given in Algorithm 1. At this stage, we have: Algorithm 1 DORA 1: map σ, actuation model P P, episodes K, inner iterations I, damping α, radius scale β, dead end penalty cdec_de 2: N←0N← 0, C←0C← 0, d←0d← 0, d(crash)←cded(crash)← c_de 3: build reverse adjacency of σ once 4: for k=1,…,Kk=1,…,K do 5: wbase←max(cmin,C/N−bk)w^base← (c_ ,C/N-b_k) ⊳ Eq. (5) 6: for i=1,…,Ii=1,…,I do 7: form w from wbasew^base and d ⊳ Eq. (7) 8: (πk,d+)←Dijkstra(σ,w,g)( _k,d^+)← Dijkstra(σ,w,g) 9: d←(1−α)d+αd+d←(1-α)d+α d^+; d(crash)←cded(crash)← c_de 10: end for 11: execute πk _k for one episode 12: update N and C from the observed step costs 13: end for 14: return πK _K Proposition 3 (Fixed point). Suppose c^=c¯ c= c, P^=P P=P, b≡0b≡ 0 and w⋆≥0w ≥ 0 on E. Then d=V⋆d=V is a fixed point of the inner loop of Algorithm 1, and the returned policy is optimal. Proof. Setting d=V⋆d=V in (7) and comparing with (4) gives w=[w⋆]+=w⋆w=[w ]^+=w . Proposition 1 then yields d+=dw⋆=V⋆d^+=d_w =V , so the update leaves d unchanged and πk=πw⋆ _k= _w is optimal. ∎ Proposition 3 states what the planner converges to when the estimates are correct. However, it does not by itself give a regret bound. Furthermore, because wkbasew^base_k is an optimistic estimate of c¯ c on the event that all confidence intervals hold, the policy returned at episode k is greedy with respect to an optimistic model, and the per episode regret is controlled by the sum of confidence radii along the visited trajectory. Following the argument used for optimistic algorithms in this setting [39, 36], we have a bound of order O~(cmaxτmax||||K) O(c_ _ |S||A|K) against the best member of Πσ _σ, where τmax _ bounds the expected time to absorption. Even further, under Proposition 1 the best member of Πσ _σ is optimal, so the same bound holds against V⋆V . We state this as the guarantee that motivates the design and verify the resulting sublinear behavior empirically in Section V. The formal guarantee for the variant whose inner iteration is run to convergence is provided in Appendix A. In terms of compute, the cost of Algorithm 1 is I oracle calls and I drift evaluations per episode. The advantage is the number I does not grow with the map. A single Dijkstra pass already propagates cost information across the whole graph, so the iteration only has to correct for slip (which is local). On the contrary, value iteration has no such property. Its number of sweeps grows with the diameter of the graph, because each sweep moves information one step. This difference is the source of the scaling behavior reported in Section V-B. IV-D Chance-Constrained Navigation Finally we address safety, which is often specified as a budget [34, 7, 14]. Let ρ(π)ρ(π) be the probability that an episode ends in contact, and require ρ(π)≤Δρ(π)≤ . Let p^(s,a) p(s,a) be the empirical contact probability. For that, we add a log survival term to the oracle weight, wλ(s,a)=w(s,a)+λ(−log(1−p^(s,a))).w_λ(s,a)=w(s,a)+λ (- (1- p(s,a) ) ). (8) The weight of a route under the second term alone is the negative logarithm of the probability of traversing it without contact, so a shortest path under (8) trades distance off against survival. The same transformation underlies counterexample generation in probabilistic verification [17]. Furthermore, the multiplier is updated by projected dual ascent on the realized contact indicator of the episode just executed, λk+1=[λk+η0k(contactk−Δ)]0λmax, _k+1= [ _k+ _0 k (1\contact_k\- ) ]_0 _ , (9) which needs no extra planning sweep. Here, ⋅1\·\ is the indicator function. We call this variant DORA-S. Because the optimal policy of a constrained Markov decision process is in general a mixture of deterministic policies [2], the constraint is met in the time averaged sense rather than by every individual iterate. Fig. 1: The warehouse benchmark. Dark blocks are shelves, the shading of free cells is the unknown traversal cost, and the red band is a picking zone where contact ends the episode. (a) The risk neutral route drives through the picking zone. (b) With a risk budget the same oracle call returns a detour that almost eliminates contact. V Experiments V-A Setup The benchmark we provide is a 20×2020× 20 warehouse with shelf blocks and four vertical cross aisles, giving 266266 states after adding the crash state. A human picking zone spans two interior columns. The robot may drive through it or detour through the perimeter aisles, which are the only gates left open. Figure 1 shows the map and the two routes. Traversal costs combine a shelf proximity term with a smoothed random field, so that the region a robot slips into affects its performance and not only the step on which it slipped. Unless stated otherwise the slip probability is ε=0.10 =0.10, the contact probability in the picking zone is 0.140.14, the dead end penalty is 8080, the horizon is 150150 and the radius scale is β=0.05β=0.05. Every configuration is repeated over 1010 instances that differ in the random terrain field, and we report the mean and the standard deviation of the regret, along with the other key metrics, which include Work, SR, CR, and Contacts. Here, work is planner operations per episode. SR and CR are the success and contact rates of the final policy, respectively. Finally, contacts is the expected number accumulated during learning. The model, the Dijkstra implementation and all learners are written in Julia. The oracle is an indexed binary heap Dijkstra with decrease key. We evaluate each distinct policy exactly by backward recursion (rather than by sampling), which removes evaluation noise from every reported curve. We compare the following methods. DORA is Algorithm 1 with I=3I=3 and α=0.4α=0.4. DORA-0 is the ablation with the reduced cost correction switched off, which is optimistic determinize and replan. CED [42] is the certainty equivalent Dijkstra planner with neither optimism nor correction. EGD adds ε greedy exploration to CED. OVI-U is optimistic value iteration that estimates the transition kernel [38, 36], and OVI-K uses the true kernel. Both value iteration baselines are run to convergence with a warm start at every episode, so they are not penalized by an arbitrary sweep budget. V-B Online Navigation Table I reports the main comparison over K=800K=800 episodes. We summarize the results also in Figure 2. Our findings are as follows. TABLE I: Online navigation metric comparison over 800800 episodes Method Regret ↓ Work ↓ SR ↑ CR ↓ Contacts ↓ DORA ±203± 74 15,08415,084 0.9840.984 0.0160.016 12.712.7 DORA-0 4,806±8664,806± 866 772 0.7270.727 0.2730.273 219.4219.4 CED 4,751±8414,751± 841 772 0.7270.727 0.2730.273 218.7218.7 EGD 7,753±7407,753± 740 772 0.7090.709 0.2910.291 232.6232.6 OVI-U 1,906±1,6661,906± 1,666 196,094196,094 0.9830.983 0.0170.017 20.520.5 OVI-K 203±47203± 47 164,801164,801 0.9840.984 0.0160.016 12.712.7 Optimal −- −- 0.9840.984 0.0160.016 −- Fig. 2: Online warehouse navigation results. (a) Cumulative regret, shaded by one standard deviation over ten instances. (b) Expected contacts accumulated during learning. (c) Planner work per episode as the map grows. First, we observe that DORA attains a regret of 203203, which is statistically indistinguishable from the 203203 attained by OVI-K, while performing 10.910.9 times less planner work. It also beats OVI-U, which must estimate the transition kernel, by a factor of 9.49.4 in regret and by 13.013.0 in work. Second, the reduced cost correction is what makes this possible. The ablation DORA-0 incurs 2424 times more regret and 1717 times more contacts, and it converges to a policy whose cost exceeds the optimum by 5.85.8 units. The difference is that a determinized planner weighted by expected one step cost cannot see where a slip takes the robot, and in this map a slip into the picking zone is what causes contact. Third, safety during learning follows the same pattern. DORA accumulates 12.712.7 expected contacts across the whole training run, which matches the 12.712.7 accumulated by an agent that knows the true dynamics, whereas the uncorrected planners accumulate more than 218218. Panel (c) of Figure 2 reports planner work as the map is enlarged from 266266 to 12021202 states. The ratio of work between OVI-K and DORA grows from 13.713.7 to 21.121.1, further supporting our argument in Section IV. DORA performs a fixed number of oracle calls whatever the size of the map, whereas the number of value iteration sweeps needed to converge grows with the diameter. V-C Losslessness of Dijkstra-class Algorithms The second experiment tests our theory. We sweep the slip probability from 00 to 0.450.45 on 2525 instances with a strongly varying terrain field and no picking zone, so that the only source of difficulty is actuation noise. For each instance we compute the exact optimal value, evaluate the two exactness conditions, and evaluate three members of the Dijkstra class. Results are summarized in Figure 3. Fig. 3: Exactness of the Dijkstra policy class. (a) Causality collapses as soon as slip is introduced, while the reduced costs stay nonnegative. (b) The reduced cost weights are exactly optimal at every slip level, and the DORA fixed point stays within 0.0110.011 percent of the optimum. The classical causality condition collapses immediately. At ε=0 =0 it holds at every state, and at ε=0.05 =0.05 it holds at only 47.347.3 percent of them. The reduced cost condition holds at every state action pair up to a slip of 0.300.30, and even at ε=0.45 =0.45 it holds at 92.892.8 percent of them. Correspondingly, the member of the class defined by the reduced costs is exactly optimal at every slip level tested, to the precision of the computation. The DORA fixed point, which reaches the same weights from data stays within 0.0110.011 percent of the optimum. Finally, we note the contrast with the two standard reference points. The member of the class weighted by expected one step cost, which is what determinize and replan uses, loses up to 7.17.1 percent, with a ninetieth percentile loss of 14.514.5 percent. The a posteriori residual bound of [19], in which the Bellman residual is amplified by the expected time to absorption, exceeds the optimal value itself for any slip above 0.150.15. The gap between a vacuous worst case bound and an exact policy is the practical content of Proposition 1. V-D Chance Constrained Navigation The third experiment enforces a risk budget. We set the contact probability in the picking zone to 0.160.16 and sweep the budget Δ from 0.300.30 down to 0.020.02. DORA-S runs Algorithm 1 with the risk weight (8) and the dual update (9). As a reference we compute, on the true model, the best stationary policy that meets the budget, by bisecting a Lagrange multiplier on the true contact probability. Results are summarized in Figure 4. Fig. 4: Chance constrained navigation. (a) The contact rate of DORA-S tracks the budget across two orders of magnitude. (b) The cost paid for that safety. At intermediate budgets DORA-S beats the best deterministic policy because dual ascent mixes routes across episodes. The mean contact rate tracks the budget across the whole range, from 0.2680.268 at a budget of 0.300.30 down to 0.0110.011 at a budget of 0.020.02, against an unconstrained rate of 0.3070.307. The cost paid for that safety rises from 22.4122.41 to 33.9933.99, which is the price of routing around the picking zone rather than through it. In addition, we also note two caveats. First, satisfaction is in the time averaged sense. At the intermediate budgets the mean satisfies the constraint but individual instances could violate it, which is expected because dual ascent oscillates around the boundary of the feasible set. Second, at budgets of 0.200.20 and 0.100.10 DORA-S attains a lower expected cost than the best single deterministic policy that meets the budget, namely 25.4925.49 against 29.3529.35. The reason is that the feasible set of deterministic policies is discrete in this map. Since there is no deterministic route with a contact rate near 0.150.15, the reference must jump to a much safer and much longer route. Note also dual ascent mixes two routes across episodes and lands between them instead. This is the mixture structure that is known to characterize optimal policies of constrained Markov decision processes [2]. V-E Benchmark Problems Across Navigation Tasks The final experiment tests whether these findings are general across environments. We convert three navigation problems from the JuliaPOMDP ecosystem into stochastic shortest path form and repeat the exactness analysis and the online comparison on each of them. First, SimpleGridWorld, is a 10×1010× 10 grid with actuation slip of 0.30.3, one goal cell, and two hazard cells that absorb with the dead end penalty. Second, GeoSteeringMDP from GeoSteerings.jl [3] is a directional drilling problem in which the agent must keep the wellbore inside a sinusoidal target zone under a drift probability of 0.30.3 and reach the terminal zone at the right edge of the map. Finally, the drone surveillance problem [21] asks a UAV to travel from one corner of a grid to the opposite corner while a ground agent performs a random walk, and sharing a cell with the agent ends the episode. Here, traversal costs are one per move in the grid world and the drone problem. In the geosteering problem a move that lands in the target zone costs one and a move that lands in the shale margin costs eleven, which preserves the reward ratio of the original model. The learner observes each step cost with uniform noise of half width 0.20.2, and every other quantity is treated exactly as in the warehouse study. We run K=400K=400 episodes over five seeds per domain with β=0.05β=0.05. Results appear in Figure 5 and I. Fig. 5: Benchmark problems on navigation tasks. The top row shows each problem and the optimal determinized route. Hazard cells and the ground agent are red. In the geosteering problem the target zone is white, the shale margin is gray, and the terminal zone is green. The bottom row shows cumulative regret, shaded by one standard deviation over five seeds. TABLE I: Online navigation metric comparison on the three navigation benchmarks tasks over 400400 episodes Domain Method Regret ↓ Work ↓ SR ↑ CR ↓ Contacts ↓ Grid DORA ±35± 5 5,9165,916 0.9390.939 0.0610.061 25.125.1 world DORA-0 1,187±2221,187± 222 388 0.8740.874 0.1260.126 57.257.2 CED 891±388891± 388 388 0.8830.883 0.1170.117 43.243.2 OVI-K 31±631± 6 31,16631,166 0.9390.939 0.0610.061 24.924.9 Geosteering DORA 5,625±1,3185,625± 1,318 5,6345,634 1.0001.000 0.0000.000 0.00.0 DORA-0 7,095±2,3587,095± 2,358 465 1.0001.000 0.0000.000 0.00.0 CED 7,577±1,9657,577± 1,965 465 0.9990.999 0.0000.000 0.00.0 OVI-K 6,666±1,6156,666± 1,615 108,514108,514 0.9990.999 0.0000.000 0.00.0 Drone surv. DORA ±65± 5 195,366195,366 1.0001.000 0.0000.000 0.00.0 DORA-0 1,673±1351,673± 135 9,8479,847 0.8030.803 0.1970.197 83.983.9 CED 2,067±1512,067± 151 9,8479,847 0.7810.781 0.2190.219 88.988.9 OVI-K 52±552± 5 880,116880,116 1.0001.000 0.0000.000 0.00.0 Figure 5 shows that the exactness picture from the warehouse carries over. The causality condition varies widely, from 3.13.1 percent of states in the grid world to 94.194.1 percent in the drone problem, while the reduced costs stay nonnegative on at least 9090 percent of the state action pairs in every domain. The reduced cost member of the class is exactly optimal in the grid world and in the geosteering problem. The gap of the member weighted by expected one step cost reaches 31.731.7 percent in the grid world, so the correction closes a larger gap on this benchmark than on the warehouse. The drone problem is the first domain in which the clipped reduced cost member itself loses value, namely 5.85.8 percent. The negative entries are caused by the motion of the ground agent rather than by actuation slip. DORA nevertheless reaches a final policy within one percent of the optimum, which shows that the class contains better members than the clipped reduced cost weighting and that the learner finds one of them. Table I shows that the online behavior also carries over. DORA attains a regret within one standard deviation of OVI-K on the grid world and the drone problem, and a lower regret than OVI-K on the geosteering domain, while performing 5.35.3, 19.319.3 and 4.54.5 times less planner work on the three domains. The reduced cost correction remains essential. DORA-0 and CED incur 2525 to 3434 times more regret than DORA on the grid world and the drone problem, and they roughly double the contacts accumulated in the grid world and drive the contact rate of the final policy to about 0.20.2 in the drone problem. The geosteering domain has no crash state, so every method is safe there, and the correction still reduces the regret by about a fifth. VI Discussion VI-A Role of the Reduced Cost Views The label-setting literature is organized around causality, and causality is a demanding condition. Our results suggest it is the wrong condition to check when the question is whether the Dijkstra derived policy class is expressive enough. Causality asks whether the value decreases along every stochastic outcome. Exact representation only asks whether it decreases along the determinized edge, after the drift caused by the other outcomes has been charged to that edge. Figure 3 quantifies the difference. This also explains a long standing empirical puzzle. Determinize and replan is known to work far better than worst case analysis predicts [42, 27], and equally known to have no useful guarantee [35]. Our interpretation is that the practical success comes from the policy class, which is rich enough to contain the optimum, while the missing guarantee comes from the weighting. VI-B Compute and Deployment DORA performs a fixed number of oracle calls per episode, which does not depend on the size of the map. Planning time is therefore more predictable, which is what a real time control loop requires, and the oracle is the same shortest path routine that navigation stacks already contain. Using that perspective, DORA can be added to an existing planner as a change to the edge weights instead of a replacement of the planning layer. VI-C Safety by Construction One observation deserves emphasis for safety critical deployment. The determinized graph contains no edge into the crash state, so the oracle cannot return a route that plans to collide, and risk enters only through the weights. Optimistic value iteration has no such protection. In an early version of our study it actively sought the absorbing failure state, because an unvisited action looked cheap and the failure state carried no future cost. We removed that pathology by giving every method the known dead end penalty, which is the standard treatment in this literature [24]. Constraining the search space of the planner is a more robust safety mechanism than relying on a value function to have learned that failure is expensive. VI-D Limitations Finally, we highlight three limitations. First, DORA uses the actuation model, namely the scalar slip probability and the map geometry. This is far less than a transition kernel and is a calibrated quantity on a real platform, but it is still a required input. An extension that estimates the slip probability online was omitted in this study. Second, the regret guarantee proved in Appendix A covers the variant whose inner iteration is run to convergence, and the implemented algorithm with its finite inner iteration is supported only by experiments. Third, the benchmarks are grid maps with a small number of motion primitives. Continuous state, non holonomic dynamics and partial observability would each require additional work, although the reduced cost identity itself does not depend on the grid structure. We aim to study these further extensions in future work. VII Conclusion This paper revisits the use of Dijkstra’s algorithm for SSP navigation. We showed that the policy class induced by shortest path search contains an optimal policy whenever a reduced cost defined on the determinized map is nonnegative, and that this condition is much weaker than the causality condition normally invoked in past studies. On a warehouse navigation benchmark the condition holds on every state action pair up to a slip probability of 0.300.30, and the reduced cost member of the class is exactly optimal at every slip level we tested. Building on this, we introduced DORA (Dijkstra Oracle Reduced-cost Algorithm), an online learner that reaches this member using a fixed number of oracle calls per episode and no transition kernel. DORA matches optimistic value iteration that is given the true kernel while performing an order of magnitude less planner work, and the gap widens with the size of the map, which we validate further on three navigation benchmarks. Future work will estimate the actuation model online, complete the regret analysis, and extend the reduced cost construction to continuous state planners. References [1] A. Agha-mohammadi, S. Chakravorty, and N. M. Amato (2014) FIRM: sampling-based feedback motion-planning under motion uncertainty and imperfect measurements. International Journal of Robotics Research 33 (2), p. 268–304. Cited by: §I-D. [2] E. Altman (1999) Constrained Markov decision processes. Chapman and Hall/CRC, Boca Raton, FL. Cited by: §IV-D, §V-D. [3] Anonymous (2024) GeoSteerings.jl: sequential decision making for geosteering. Note: Repository withheld for double-anonymous review Cited by: §V-E. [4] D. P. Bertsekas and J. N. Tsitsiklis (1991) An analysis of stochastic shortest path problems. Mathematics of Operations Research 16 (3), p. 580–595. Cited by: Appendix A, Appendix A, §I. [5] D. P. Bertsekas (2019) Robust shortest path planning and semicontractive dynamic programming. Naval Research Logistics 66 (1), p. 15–37. Cited by: §I-A. [6] D. Bertsimas and M. Sim (2003) Robust discrete optimization and network flows. Mathematical Programming 98 (1–3), p. 49–71. Cited by: §I-D. [7] L. Blackmore, M. Ono, and B. C. Williams (2011) Chance-constrained optimal path planning with obstacles. IEEE Transactions on Robotics 27 (6), p. 1080–1094. External Links: Document Cited by: §IV-D. [8] B. Bonet and H. Geffner (2003) Labeled RTDP: improving the convergence of real-time dynamic programming. In International Conference on Automated Planning and Scheduling (ICAPS), p. 12–21. Cited by: §I, §I-A. [9] L. Chen, H. Luo, and A. Rosenberg (2022) Policy optimization for stochastic shortest path. In Conference on Learning Theory (COLT), p. 982–1046. Cited by: §I-B. [10] L. Chen, A. Tirinzoni, M. Pirotta, and A. Lazaric (2023) Reaching goals is hard: settling the sample complexity of the stochastic shortest path. In International Conference on Algorithmic Learning Theory (ALT), p. 310–357. Cited by: §I-B. [11] A. Cohen, Y. Efroni, Y. Mansour, and A. Rosenberg (2021) Minimax regret for stochastic shortest path. In Advances in Neural Information Processing Systems (NeurIPS), p. 28350–28361. Cited by: §I, §I-B. [12] P. Dai and J. Goldsmith (2007) Topological value iteration algorithm for Markov decision processes. In International Joint Conference on Artificial Intelligence (IJCAI), p. 1860–1865. Cited by: §I-A. [13] P. Dai, Mausam, D. S. Weld, and J. Goldsmith (2011) Topological value iteration algorithms. Journal of Artificial Intelligence Research 42, p. 181–209. Cited by: §I-A. [14] O. de Groot, L. Ferranti, D. M. Gavrila, and J. Alonso-Mora (2025) Scenario-based motion planning with bounded probability of collision. International Journal of Robotics Research 44 (9), p. 1507–1525. External Links: Document Cited by: §IV-D. [15] E. W. Dijkstra (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1 (1), p. 269–271. Cited by: §I. [16] M. E. Gaspard and A. Vladimirsky (2025) Monotone causality in opportunistically stochastic shortest path problems. Mathematics of Operations Research. External Links: Document Cited by: §I, §I-A, §IV-B. [17] T. Han, J. Katoen, and B. Damman (2009) Counterexample generation in probabilistic model checking. IEEE Transactions on Software Engineering 35 (2), p. 241–257. Cited by: §I-D, §IV-D. [18] E. A. Hansen and S. Zilberstein (2001) LAO*: a heuristic search algorithm that finds solutions with loops. Artificial Intelligence 129 (1–2), p. 35–62. Cited by: §I, §I-A. [19] E. A. Hansen (2011) Suboptimality bounds for stochastic shortest path problems. In Conference on Uncertainty in Artificial Intelligence (UAI), p. 301–308. Cited by: §I-C, §V-C. [20] P. E. Hart, N. J. Nilsson, and B. Raphael (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4 (2), p. 100–107. Cited by: §I-A. [21] JuliaPOMDP (2019) DroneSurveillance.jl: implementation of a drone surveillance problem with POMDPs.jl. Note: https://github.com/JuliaPOMDP/DroneSurveillance.jl Cited by: §V-E. [22] A. Kalai and S. Vempala (2005) Efficient algorithms for online decision problems. Journal of Computer and System Sciences 71 (3), p. 291–307. Cited by: §I-B. [23] S. Koenig and M. Likhachev (2002) D* Lite. In AAAI Conference on Artificial Intelligence, p. 476–483. Cited by: §I-A. [24] A. Kolobov, Mausam, D. S. Weld, and H. Geffner (2011) Heuristic search for generalized stochastic shortest path MDPs. In International Conference on Automated Planning and Scheduling (ICAPS), p. 130–137. Cited by: §VI-C. [25] M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, and S. Thrun (2005) Anytime dynamic A*: an anytime, replanning algorithm. In International Conference on Automated Planning and Scheduling (ICAPS), p. 262–271. Cited by: §I-A. [26] M. Likhachev, G. Gordon, and S. Thrun (2003) ARA*: anytime A* with provable bounds on sub-optimality. In Advances in Neural Information Processing Systems (NIPS), Cited by: §I-A. [27] I. Little and S. Thiébaux (2007) Probabilistic planning vs replanning. In ICAPS Workshop on the International Planning Competition, Cited by: §I-C, §VI-A. [28] S. Macenski, F. Martín, R. White, and J. G. Clavero (2020) The Marathon 2: a navigation system. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 2718–2725. External Links: Document Cited by: §I. [29] V. Malathi, P. Sreedharan, R. P R, V. Anil Kumar, A. L. Sadasivan, G. Udupa, L. Pastorelli, and A. Troppina (2025) Decision-making for path planning of mobile robots under uncertainty: a review of belief-space planning simplifications. Robotics 14 (9), p. 127. External Links: Document Cited by: §I. [30] E. Marder-Eppstein, E. Berger, T. Foote, B. Gerkey, and K. Konolige (2010) The office marathon: robust navigation in an indoor office environment. In IEEE International Conference on Robotics and Automation (ICRA), p. 300–307. External Links: Document Cited by: §I, §I. [31] H. B. McMahan and G. J. Gordon (2005) Fast exact planning in Markov decision processes. In International Conference on Automated Planning and Scheduling (ICAPS), p. 151–160. Cited by: §I-A. [32] H. B. McMahan, M. Likhachev, and G. J. Gordon (2005) Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees. In International Conference on Machine Learning (ICML), p. 569–576. Cited by: §I-A. [33] E. Nikolova (2010) Approximation algorithms for reliable stochastic combinatorial optimization. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), p. 338–351. Cited by: §I-D. [34] M. Ono and B. C. Williams (2008) Iterative risk allocation: a new approach to robust model predictive control with a joint chance constraint. In IEEE Conference on Decision and Control (CDC), p. 3427–3432. Cited by: §I-D, §IV-D. [35] L. E. Pineda and S. Zilberstein (2019) Probabilistic planning with reduced models. Journal of Artificial Intelligence Research 65, p. 271–306. Cited by: §I-C, §VI-A. [36] A. Rosenberg, A. Cohen, Y. Mansour, and H. Kaplan (2020) Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning (ICML), p. 8210–8219. Cited by: §I, §I-B, §IV-C, §V-A. [37] P. Santana, S. Thiébaux, and B. Williams (2016) RAO*: an algorithm for chance-constrained POMDPs. In AAAI Conference on Artificial Intelligence, p. 3308–3314. Cited by: §I-D. [38] J. Tarbouriech, E. Garcelon, M. Valko, M. Pirotta, and A. Lazaric (2020) No-regret exploration in goal-oriented reinforcement learning. In International Conference on Machine Learning (ICML), p. 9428–9437. Cited by: §I-B, §V-A. [39] J. Tarbouriech, R. Zhou, S. S. Du, M. Pirotta, M. Valko, and A. Lazaric (2021) Stochastic shortest path: minimax, parameter-free and towards horizon-free regret. In Advances in Neural Information Processing Systems (NeurIPS), p. 6843–6855. Cited by: §I, §I-B, §IV-C. [40] P. Trautman and A. Krause (2010) Unfreezing the robot: navigation in dense, interacting crowds. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 797–803. Cited by: §I. [41] A. Vladimirsky (2008) Label-setting methods for multimode stochastic shortest path problems on graphs. Mathematics of Operations Research 33 (4), p. 821–838. Cited by: §I, §I-A, §IV-B. [42] S. W. Yoon, A. Fern, and R. Givan (2007) F-Replan: a baseline for probabilistic planning. In International Conference on Automated Planning and Scheduling (ICAPS), p. 352–359. Cited by: §I-C, §IV-B, §V-A, §VI-A. Appendix A Formal Statements and Proofs This appendix expands the proofs of Propositions 1 to 3 and states and proves the regret guarantee for the variant of Algorithm 1 whose inner iteration is run to convergence. Throughout, V⋆V and Q⋆Q denote the exact stochastic shortest path values of M, which exist and satisfy the Bellman equation under Assumption 1 and cmin>0c_ >0 by the standard theory [4]. The goal and the crash state are absorbing, with terminal cost zero at the goal and cdec_de at the crash state. For a weight vector w≥0w≥ 0 on the determinized edge set E, we write Dw(s)D_w(s) for the shortest path distance from s to g in the determinized graph, which is what a backward Dijkstra call returns. The proofs use one condition beyond the hypotheses stated in the main text. Assumption 2 (Strict determinized progress). For every s∉g,crashs∉\g,crash\, V⋆(s)>V⋆(σ(s,π⋆(s)))V (s)>V (σ(s,π (s))). Assumption 2 states that the intended successor of the optimal action strictly decreases the optimal value. It is the strict form of the causality condition restricted to the determinized edge, so it is still much weaker than consistent improvement, which constrains every stochastic outcome. It can fail only through an exact tie, and it holds with positive margin on every instance in our experiments. Lemma 1 (Path lower bound). Let s=s1→s2→…→sm+1=gs=s_1→ s_2→…→ s_m+1=g be any path in the determinized graph, with si+1=σ(si,ai)s_i+1=σ(s_i,a_i). Then ∑i=1mw⋆(si,ai)≥V⋆(s) _i=1^mw (s_i,a_i)≥ V (s). Proof. By Definition 2 and Q⋆≥V⋆Q ≥ V , ∑i=1mw⋆(si,ai) _i=1^mw (s_i,a_i) =∑i=1m(Q⋆(si,ai)−V⋆(si+1)) = _i=1^m (Q (s_i,a_i)-V (s_i+1) ) ≥∑i=1m(V⋆(si)−V⋆(si+1)), ≥ _i=1^m (V (s_i)-V (s_i+1) ), and the last sum telescopes to V⋆(s)−V⋆(g)=V⋆(s)V (s)-V (g)=V (s). ∎ Lemma 2 (Achievability). Under Assumption 2, for every s the path that follows π⋆π through the determinized graph reaches g, and its total weight equals V⋆(s)V (s). Hence Dw⋆(s)≤V⋆(s)D_w (s)≤ V (s). Proof. Along the path si+1=σ(si,π⋆(si))s_i+1=σ(s_i,π (s_i)) the optimal value strictly decreases by Assumption 2. Since the state space is finite and the crash state cannot be a determinized successor, the path cannot revisit a state and must terminate at g. At the optimal action Q⋆(si,π⋆(si))=V⋆(si)Q (s_i,π (s_i))=V (s_i), so every inequality in the proof of Lemma 1 holds with equality, and the total weight telescopes exactly to V⋆(s)V (s). ∎ Proof of Proposition 1. Under the hypothesis w⋆≥0w ≥ 0 on E, Dijkstra computes Dw⋆D_w . Lemmas 1 and 2 give Dw⋆=V⋆D_w =V . The greedy policy of the shortest path tree satisfies πw⋆(s) _w (s) ∈argminaw⋆(s,a)+Dw⋆(σ(s,a)) ∈ _a\w (s,a)+D_w (σ(s,a))\ =argminaQ⋆(s,a), = _aQ (s,a), so πw⋆ _w is greedy with respect to V⋆V and therefore optimal [4]. ■ Proof of Proposition 2. At the optimal action Q⋆(s,π⋆(s))=V⋆(s)Q (s,π (s))=V (s), and substituting into (3) gives w⋆(s,π⋆(s))=V⋆(s)−V⋆(σ(s,π⋆(s)))w (s,π (s))=V (s)-V (σ(s,π (s))). Consistent improvement requires V⋆(s)>V⋆(s′)V (s)>V (s ) for every successor s′s with positive probability, and the determinized successor is one of them, so consistent improvement implies w⋆(s,π⋆(s))≥0w (s,π (s))≥ 0. For the converse, a lateral slip outcome may satisfy V⋆(s′)>V⋆(s)V (s )>V (s) and violate consistent improvement while leaving the determinized edge, and hence the reduced cost, unchanged. Figure 3 shows that this is the typical case rather than the exception. ■ Proof of Proposition 3. With c^=c¯ c= c, P^=P P=P and b≡0b≡ 0, substituting d=V⋆d=V into (7) and comparing with (4) gives w=[w⋆]+w=[w ]^+, which equals w⋆w under the hypothesis w⋆≥0w ≥ 0. The oracle then returns d+=Dw⋆=V⋆d^+=D_w =V by Lemmas 1 and 2, so the damped update leaves d unchanged, and the returned policy is πw⋆ _w , which is optimal by Proposition 1. ■ A-A Regret of the Idealized Variant We analyze the variant of Algorithm 1 in which the inner iteration is run to its fixed point at every episode, so that by Proposition 3 the executed policy πk _k is an optimal policy of the optimistic model MkM_k that has the true kernel P and the step costs ck(s,a)=max(cmin,c^k(s,a)−bk(s,a))c_k(s,a)= (c_ , c_k(s,a)-b_k(s,a)). Episodes are run to absorption. The analysis uses three conditions. Assumption 3. (i) Observed step costs are c¯(s,a)+η c(s,a)+η with η independent, mean zero, and bounded in [−η¯,η¯][- η, η], and the radius scale satisfies β≥(cmax+η¯)/2β≥(c_ + η)/ 2. (i) The exactness conditions of Propositions 1 and 3 and Assumption 2 hold for every optimistic model MkM_k. (i) Every executed policy is proper, and its expected time to absorption from every state is at most τmax _ . Proposition 4 (Regret). Under Assumptions 1 to 3, with probability at least 1−δ1-δ the idealized variant satisfies RK≤ 4βlog(2||||K/δ)||||TK,R_K\;≤\;4β \! (2|S||A|K/δ )\; |S||A|\,T_K, where TKT_K is the total number of steps taken in the K episodes. Since [TK]≤τmaxKE[T_K]≤ _ K, the expected regret is of order O~(βτmax||||K) O(β _ |S||A|K). Proof. Let L=log(2||||K/δ)L= (2|S||A|K/δ) and let G be the event that |c^k(s,a)−c¯(s,a)|≤bk(s,a)| c_k(s,a)- c(s,a)|≤ b_k(s,a) for all (s,a)(s,a) and all k≤Kk≤ K. Each observed cost lies in an interval of length at most cmax+2η¯≤22βc_ +2 η≤ 2 2\,β, so by Hoeffding’s inequality and a union bound over states, actions, episodes, and the two tail directions, ℙ()≥1−δP(G)≥ 1-δ with the radius (5). The remainder of the proof conditions on G. First, optimism. On G, ck(s,a)≤c¯(s,a)c_k(s,a)≤ c(s,a) for every pair, because c^k−bk≤c¯ c_k-b_k≤ c and cmin≤c¯c_ ≤ c. Values of a fixed proper policy are monotone in the step costs, so VMk⋆(s0)≤JMkπ⋆(s0)≤JMπ⋆(s0)=V⋆(s0)V _M_k(s_0)≤ J^π _M_k(s_0)≤ J^π _M(s_0)=V (s_0). Second, the value difference. The models M and MkM_k share the kernel and the terminal costs and differ only in the step costs, so for the proper policy πk _k, JMπk(s0)−JMkπk(s0) J _k_M(s_0)-J _k_M_k(s_0) =πk[∑t(c¯−ck)(st,at)] =E _k [ _t ( c-c_k )(s_t,a_t) ] ≤πk[∑t2bk(st,at)], _k [ _t2\,b_k(s_t,a_t) ], where the sum runs until absorption and the inequality uses c¯−ck≤c¯−(c^k−bk)≤2bk c-c_k≤ c-( c_k-b_k)≤ 2b_k on G. Since πk _k is optimal for MkM_k by Proposition 3 and Assumption 3(i), JMkπk(s0)=VMk⋆(s0)≤V⋆(s0)J _k_M_k(s_0)=V _M_k(s_0)≤ V (s_0), and the per episode regret is bounded by the displayed expectation. Third, the pigeonhole step. Summing the realized radii over the whole run and letting NT(s,a)N_T(s,a) be the final visit counts, ∑k=1K∑tbk(st,at) _k=1^K _tb_k(s_t,a_t) ≤βL∑s,a∑j=1NT(s,a)1j ≤β L _s,a _j=1^N_T(s,a) 1 j ≤2βL∑s,aNT(s,a), ≤ 2β L _s,a N_T(s,a), and by the Cauchy Schwarz inequality the last sum is at most ||||TK |S||A|\,T_K. Combining the three steps gives the claim. ∎ Proposition 4 covers the idealized variant. The implemented algorithm differs in two ways: the inner loop performs I damped iterations rather than running to convergence, and the clipping in (7) can be active when the optimistic reduced costs are negative. Proposition 3 identifies the fixed point that the inner loop targets, and Section V verifies empirically that I=3I=3 damped iterations track the idealized behavior. Closing this gap formally is left to future work, as stated in Section VI. Appendix B Experimental Parameters Tables I and IV list every parameter of the four experiments. The warehouse model and the learners are described in Sections I to V, and the benchmark conversions in Section V-E. TABLE I: Parameters of the warehouse experiments. Parameter Exp. 1 Exp. 2 Exp. 3 Map size 20×2020× 20 20×2020× 20 20×2020× 20 States |||S| 266266 266266 266266 Slip probability ε 0.100.10 00 to 0.450.45 0.100.10 Picking zone contact prob. 0.140.14 00 0.160.16 Terrain roughness 0.50.5 1.61.6 0.50.5 Cost bounds [cmin,cmax][c_ ,c_ ] [0.25, 2.2][0.25,\,2.2] Bump cost 1.51.5 1.51.5 1.51.5 Dead end penalty cdec_de 8080 8080 2525 Timeout penalty ctoc_to 6060 6060 6060 Horizon H 150150 150150 150150 Cost noise half width 0.120.12 −- 0.120.12 Episodes K 800800 −- 800800 Instances 1010 2525 1010 Radius scale β, confidence δ 0.050.05, 0.10.1 −- 0.050.05, 0.10.1 Inner iterations I, damping α 33, 0.40.4 88, 0.40.4 33, 0.40.4 OVI sweep cap, tolerance 200200, 10−410^-4 −- −- EGD exploration rate 0.100.10 −- −- Scaling sizes 20,28,36,44\20,28,36,44\ −- −- Scaling episodes, seeds 6060, 33 −- −- Dual step η0 _0, cap λmax _ −- −- 300300, 300300 TABLE IV: Parameters of the benchmark domains of experiment 4. Parameter Grid world Geosteering Drone surv. Grid size 10×1010× 10 15×1515× 15 7×77× 7 States |||S| 9999 157157 22112211 Actions 44 33 55 Motion noise slip 0.30.3 drift 0.30.3 agent walk Start (1,1)(1,1) (1,10)(1,10) (1,1)(1,1), agent (4,4)(4,4) Goal (9,3)(9,3) right edge (7,7)(7,7) Hazards (4,3)(4,3), (4,6)(4,6) shale margin meeting agent Step cost 11 11 / 1111 11 Dead end penalty cdec_de 2020 6060 2525 Timeout penalty ctoc_to 3030 120120 4040 Horizon H 100100 100100 100100 Cost noise half width, cminc_ 0.20.2, 0.50.5 0.20.2, 0.50.5 0.20.2, 0.50.5 Episodes K, seeds 400400, 55 400400, 55 400400, 55 Map generator default default restricted agent The geosteering map uses the default generator of the original package, with base amplitude 3.03.0, base frequency 1.01.0, amplitude variation 0.50.5, frequency variation 0.050.05, phase 0.30.3, vertical shift 7.07.0, and target thickness 5.05.0. All learners in every experiment use the radius scale β=0.05β=0.05 and the confidence parameter δ=0.1δ=0.1. Appendix C Policy Rollouts Figures 6 to 9 compare one rollout of the final DORA policy with one rollout of the final OVI-K policy in each domain. The sequences illustrate the main quantitative finding of Section V. In every domain the two final policies follow nearly the same route, although DORA computed its policy with a fixed number of shortest path calls per episode while OVI-K ran value iteration with the true kernel. In the warehouse both policies route above the picking zone, which is optimal at this dead end penalty. In the grid world both detour below the hazard cells, in the geosteering domain both follow the sinusoidal target zone and absorb the same drift events, and in the drone domain both curve around the region that the ground agent occupies. Fig. 6: Rollout of the final DORA policy (top) and the final OVI-K policy (bottom) on the warehouse instance of experiment 1. Fig. 7: Rollout of the final policies on the grid world benchmark. Red cells are the hazard cells. Fig. 8: Rollout of the final policies on the geosteering benchmark. The target zone is white, the shale margin is gray, and the terminal zone is green. Fig. 9: Rollout of the final policies on the drone surveillance benchmark. The dashed red line is the path of the ground agent.