Strachey Lecture: From classical to non-classical stochastic shortest path problems
From Strachey Lectures by Oxford University
February 6, 2024 · 57 min
About this episode
Professor Christel Baier discusses classical and non-classical stochastic shortest path problems in the context of Markov decision processes.
Professor Christel Baier delivers the Hillary Term 2024 Strachey Lecture Abstract: The classical stochastic shortest path (SSP) problems asks to find a policy for traversing a weighted stochastic graph until reaching a distinguished goal state that minimizes the expected accumulated weight. SSP problems have numerous applications in, e.g., operations research, artificial intelligence, robotics and verification of probabilistic systems. The underlying graph model is a finite-state Markov decision process (MDP) with integer weights for its state-action pairs. Prominent results are the existence of optimal memoryless deterministic policies together with linear programming techniques and value and policy iteration to compute such policies and their values. These results rely on the assumption that the minimum under all proper policies that reach the goal state almost surely exists. Early work on the SSP problems goes back to the 1960s-1990s and makes additional assumptions. Complete algorithms that only require the existence of proper policies combine these techniques with a pre-analysis of end components, an elegant graph-theoretic concept for MDPs that has been introduced by de…
People in this episode
Host: Oxford University
Guest: Professor Christel Baier
Topics covered
- stochastic shortest path
- Markov decision process
- operations research
- artificial intelligence
- robotics
- probabilistic systems
Keywords
- stochastic shortest path
- Markov decision process
- optimal policies
- linear programming
- probabilistic systems
- graph theory
- expected accumulated weight
More episodes of Strachey Lectures
- Hardening Digital Infrastructure: Two Examples · May 27, 2026 · 1h 2m
- An AI stack: from scaling AI workloads to evaluating LLMs · February 26, 2026 · 56 min
- Advances in Garbled Circuits · October 27, 2025 · 48 min
- Will Computers prove theorems? · May 15, 2025 · 46 min
- Formalizing the Future: Lean’s Impact on Mathematics, Programming, and AI · May 15, 2025 · 47 min
- Privacy, Verification, Robustness: A Cryptographer's perspective on ML · March 11, 2025 · 1h 4m
Explore listener stats, chart rankings, contacts and more on the Strachey Lectures podcast page.