Finding geodesics on graphs using reinforcement learning

DOI10.1214/21-AAP1777zbMath1501.05029arXiv2010.04820OpenAlexW3091816934MaRDI QIDQ2090610

Bruno Schapira, Cécile Mailler, Daniel Kious

Publication date: 31 October 2022

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.04820

zbMATH Keywords

reinforcement learningrandom walks on graphslinear reinforcementpath formationgeneralised Pólya urns

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Planar graphs; geometric and topological aspects of graph theory (05C10) Stochastic approximation (62L20) Distance in graphs (05C12) Random walks on graphs (05C81)

Related Items

MATRIX-MFO tandem workshop: Stochastic reinforcement processes and graphs. Abstracts from the MATRIX-MFO tandem workshop held March 5--10, 2023

Cites Work

• Unnamed Item
• Strongly reinforced Pólya urns with graph-based competition
• Limit theorems for triangular urn schemes
• A survey of random processes with reinforcement
• A strong law for some generalized urn processes
• Vertex-reinforced random walk on \(\mathbb Z\) has finite range
• Ant foraging and geodesic paths in labyrinths: analytical and computational results
• Vertex reinforced non-backtracking random walks: an example of path formation
• Vertex-reinforced random walk on \(\mathbb Z\) eventually gets stuck on five points.
• Probability on Trees and Networks
• Random Walk: A Modern Introduction
• Proof of the WARM whisker conjecture for neuronal connections
• A random hierarchical lattice: the series-parallel graph and its properties
• Reinforced random walk