Distributed Learning Dynamics Convergence in Routing Games

on YouTube ↗48m

" summary

Shows that route-choice dynamics either oscillate or converge depending on the learning rule, with three concrete results: no-regret yields only average convergence and persistent day-to-day oscillations; a Hedge/replicator update gives almost-sure convergence under decaying learning rates; mirror descent (Bregman-divergence) gives provable convergence speed. Uses LWR traffic models, Ensemble Kalman filtering for estimation, ramp metering control, and an experimented Mobile Millennium prototype (notably 100 cars, 200 students achieving ~2% penetration) plus a Mechanical Turk routing game for human validation.

AI-written summary · about

" chapters (29)

1. 0:00Start
2. 0:15Historical perspective on monitoring and routing
3. 0:41Historical perspective on mobile devices
4. 1:48Mobile Millennium (2008-2010)
5. 2:51Prototype experiment: Mobile Century
6. 3:48Mobile Century validation video data collection
7. 5:50Example: 0.5% of Mobile Millennium data (one day)
8. 6:50Implementation at 2% penetration rate
9. 7:25Flow reconstruction (inverse modeling)
10. 8:05Google Maps vs. model driven estimation
11. 8:45Project timeline
12. 9:27Historical perspective on data collection
13. 10:00Hybrid Traffic Data - Data Quality Metrics
14. 10:35Contributions of the Mobile Millennium project
15. 12:17Building a decision support system for road traffic
16. 12:35Illustration (Los Angeles): the 1210 corridor
17. 14:01Problem formulation
18. 24:17Nash equilibrium
19. 24:39Equilibrium of a game: tangential condition
20. 25:04regret analysis
21. 25:52Application to the routing game
22. 26:10Convergence on average
23. 27:16stochastic approximation
24. 29:33AREP: approximate replicator dynamics: illustration
25. 30:46convex optimization
26. 33:38Routing game with strongly convex potential
27. 35:38Game process
28. 40:36Back to Coupled sequential decision problem
29. 46:53Graph formulation

" related talks

• 21mThe Evolution of Traffic Routing in a Streaming WorldAbhishek Srikanth · SREcon20 Americas
• 33mA New Model for Ant Trail Formation and its Convergence PropertiesMoses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur · ITCS 2021
• 01h 33mLocally Convergent GraphsChristian Borgs · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 16mSDE Approximations and Scaling Rules for Distributed Deep LearningKaifeng Lyu · Meet the Fellows Welcome Event Fall 2024
• 01h 07mIndustry PresentationsKostas Kollias, Giuliano Losa, Hilal Asi, Rohan Alur, Horst Simon, Vigyan Singhal · Eleventh Annual Industry Day
• 46mTiming Matters: Online Dynamics in Broadcast GamesShuchi Chawla · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 29mState Management in Distributed Online Learning with RayEdmon Begoli · Ray Summit 2020
• 26mOn the O(1/k) Convergence of the Asynchronous Distributed Alternating Direction Method of Mult...Ermin Wei · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)