Efficient Constraint Generation for Stochastic Shortest Path Problems

• URL: http://arxiv.org/abs/2604.01855v1
• Date: Thu, 02 Apr 2026 10:10:22 GMT
• Title: Efficient Constraint Generation for Stochastic Shortest Path Problems
• Abstract summary: Shortest Path problems (SSPs) are traditionally solved by computing each state's cost-to-go by applying Bellman backups.<n>A Bellman backup updates a state's cost-to-go by iterating through every applicable action, computing the cost-to-go after applying each one, and selecting a minimal action's cost-to-go.<n>We present CG-iLAO*, a new algorithm that adapts iLAO* with our novel technique, and considers only 40% of iLAO*'s actions on many problems, and as few as 1% on some
• Score: 1.9336815376402718
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Stochastic Shortest Path problems (SSPs) are traditionally solved by computing each state's cost-to-go by applying Bellman backups. A Bellman backup updates a state's cost-to-go by iterating through every applicable action, computing the cost-to-go after applying each one, and selecting a minimal action's cost-to-go. State-of-the-art algorithms use heuristic functions; these give an initial estimate of costs-to-go, and lets the algorithm apply Bellman backups only to promising states, determined by low estimated costs-to-go. However, each Bellman backup still considers all applicable actions, even if the heuristic tells us that some of these actions are too expensive, with the effect that such algorithms waste time on unhelpful actions. To address this gap we present a technique that uses the heuristic to avoid expensive actions, by reframing heuristic search in terms of linear programming and introducing an efficient implementation of constraint generation for SSPs. We present CG-iLAO*, a new algorithm that adapts iLAO* with our novel technique, and considers only 40% of iLAO*'s actions on many problems, and as few as 1% on some. Consequently, CG-iLAO* computes on average 3.5x fewer costs-to-go for actions than the state-of-the-art iLAO* and LRTDP, enabling it to solve problems faster an average of 2.8x and 3.7x faster, respectively.

Related papers

• Provably Optimal Learning Algorithms for Assistance Games [60.843021846414956]
  We provide the first provably efficient learning algorithms for repeated assistance games.<n>We present decentralized algorithms for both an informed human and the assistant.<n>We prove that achieving a regret approximation factor better than $(1-1/e)$ is computationally intractable.
  arXiv  Detail & Related papers  (2026-07-09T00:38:42Z)
• Cost-Aware Learning [72.31444819326795]
  We consider the problem of Cost-Aware Learning, where sampling different component functions incur different costs.<n>We propose the Cost-Aware Descent algorithm for convex functions, and derive its cost complexity to attain an error of $$.<n>We introduce Cost-Aware GRPO, an algorithm designed to reduce the cost of policy optimization while preserving performance.
  arXiv  Detail & Related papers  (2026-04-30T15:39:09Z)
• End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions [66.17960480460185]
  We study reinforcement learning with linear function approximation in Decision Processes (MDPs)<n>We provide a computationally efficient algorithm for linear Bellman complete oracles with emphdeterministic transitions, initial states, and rewards.
  arXiv  Detail & Related papers  (2026-03-24T17:32:29Z)
• Time-Varying Convex Optimization with $O(n)$ Computational Complexity [0.0]
  We consider the problem of unconstrained convex optimization, where the cost function changes with time. Our proposed algorithms only require the first-order derivatives of the cost function with respect to the decision variable. Specifically, the proposed algorithms reduce computational cost from $(n3)$ to $O(n)$ per timestep.
  arXiv  Detail & Related papers  (2024-10-19T06:45:05Z)
• Efficient Constraint Generation for Stochastic Shortest Path Problems [0.0]
  We present an efficient version of constraint generation for Shortest Path Problems (SSPs) This technique allows algorithms to ignore sub-optimal actions and avoid computing their costs-to-go. Our experiments show that CG-iLAO* ignores up to 57% of iLAO*'s actions and it solves problems up to 8x and 3x faster than LRTDP and iLAO*.
  arXiv  Detail & Related papers  (2024-01-26T04:00:07Z)
• Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs [31.673857053336352]
  We propose an algorithm that achieves the near-optimal regret with a switching cost logarithmic in the number of episodes and linear in the time-horizon $H$. We also show the doubling trick'' used in ELEANOR-LowSwitching can be further leveraged for the generalized linear function approximation.
  arXiv  Detail & Related papers  (2023-02-24T05:14:27Z)
• Shielding in Resource-Constrained Goal POMDPs [0.0]
  We consider partially observable Markov decision processes (POMDPs) modeling an agent that needs a supply of a certain resource to operate correctly. The agent aims to minimize the expected cost of reaching some goal while preventing resource exhaustion, a problem we call emphresource-constrained goal optimization (RSGO) We implement our algorithm and present experiments showing its applicability to benchmarks from the literature.
  arXiv  Detail & Related papers  (2022-11-28T14:30:05Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization [60.72410937614299]
  We propose a new tractable bi-level optimization problem, design and analyze a new set of algorithms termed Bi-level AT (FAST-BAT) FAST-BAT is capable of defending sign-based projected descent (PGD) attacks without calling any gradient sign method and explicit robust regularization.
  arXiv  Detail & Related papers  (2021-12-23T06:25:36Z)
• Logistic Q-Learning [87.00813469969167]
  We propose a new reinforcement learning algorithm derived from a regularized linear-programming formulation of optimal control in MDPs. The main feature of our algorithm is a convex loss function for policy evaluation that serves as a theoretically sound alternative to the widely used squared Bellman error.
  arXiv  Detail & Related papers  (2020-10-21T17:14:31Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Excursion Search for Constrained Bayesian Optimization under a Limited Budget of Failures [62.41541049302712]
  We propose a novel decision maker grounded in control theory that controls the amount of risk we allow in the search as a function of a given budget of failures. Our algorithm uses the failures budget more efficiently in a variety of optimization experiments, and generally achieves lower regret, than state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-05-15T09:54:09Z)
• Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm [0.0]
  We consider an extension of the rollout algorithm that applies to constrained deterministic dynamic programming. We show that if the base produces a feasible solution, the rollout algorithm has a cost improvement property. We show that the cost improvement property is maintained with an alternative implementation that has greatly reduced computational requirements.
  arXiv  Detail & Related papers  (2020-02-18T07:09:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.