4 présentations

• 
  08h30 - 08h52

  Informative Path Planning with Limited Adaptivity

  • Rayen Tan, University of Michigan
  • Rohan Ghuge, prés., Georgia Institute of Technology
  • Viswanath Nagarajan, University of Michigan

  Adaptive decision-making is critical for informative path planning (IPP), where a robot navigates an uncertain environment to gather information while minimizing travel costs. Fully adaptive solutions, which update decisions after every step, offer the best performance but are often computationally prohibitive. In this talk, I will present a practical approach to IPP that balances computational efficiency and solution quality by employing a small number of adaptive "rounds." Our algorithm, parameterized by the number k of adaptive rounds, demonstrates a smooth trade-off between adaptivity and performance, achieving near-optimal results with significantly reduced computational overhead. We validate our theoretical results by experiments on a real road network, where we observe that a few rounds of adaptivity suffice to obtain solutions of cost almost as good as fully-adaptive ones.

• 
  08h52 - 09h14

  Revisiting Model Selection for Math Programming-Based Approximate Dynamic Programming

  • Selva Nadarajah, University of Illinois at Chicago
  • Negar Soheili, prés., University of Illinois at Chicago
  • Bo Yang, Hong Kong University of Science and Technology

  Approximations of Markov decision processes are widely used to develop policies for large-scale sequential decision-making problems. Math-programming-based approximate dynamic programming (ADP) methods, such as approximate linear programming (ALP) and pathwise optimization (PO), are notable for providing both policies and upper bounds on policy performance. ALP and PO typically solve large-scale linear or convex programming models, with recent advances in first-order methods improving solvability. Traditionally, ADP models are compared, assuming fixed features and that models can be solved optimally, in which case PO outperforms ALP. However, with machine learning techniques like random features, both ALP and PO become asymptotically optimal as more features are added. We revisit model selection between ALP and PO under random features and introduce a new ALP relaxation that improves both quality and solvability compared to the original ALP for fixed features. When no clear dominance exists between the ALP relaxation and PO models, solution methods and model structure become critical. Our ALP relaxation has a separability structure, making it preferable to PO both theoretically and numerically when using block-coordinate descent, the state-of-the-art method for solving PO. These findings offer new insights into model selection for math-programming-based ADP, where feature architecture, model, and solution method must be considered collectively, which is potentially relevant beyond these specific approaches.

• 
  09h14 - 09h36

  Stochastic Scheduling with Abandonments

  • Sebastian Perez-Salazar, prés., Rice University

  Motivated by applications where impatience is prevalent and service times are uncertain, we study a scheduling model involving jobs that may depart at unpredictable times and have stochastic service durations. The system consists of a single server and n jobs, each with a known non-negative value. The service and departure times of the jobs are stochastic but follow known probability distributions. When the server is free, it can process any available job, occupying the server for an uncertain duration while we obtain a reward. The goal is to maximize the expected total value of the jobs completed by the server. Since this problem is NP-hard, we propose polynomial-time approximation algorithms based on greedy heuristics and linear programming techniques.

• 
  09h36 - 09h58

  A Little Structure Goes a Long Way: Structure Aware Fluid Models for Weakly Coupled Markov Decision Processes

  • Selva Nadarajah, University of Illinois at Chicago
  • Andre A. Cire, prés., University of Toronto Scarborough

  Weakly coupled Markov decision processes (WDPs) represent a class of multi-stage decision making models with structure that facilitates computationally tractable Lagrangian methods. WDPs “couple” smaller component Markov decision processes via linking constraints. We investigate the value of new structure aware Lagrangian models that lie between two extremes: standard Lagrangian relaxation, which satisfies linking constraints in expectation, and feasible models that satisfy linking constraints exactly. Our investigation is based on a new combinatorial perspective for finding policy approximations, which deepens the theoretical understanding of WDP approximations and provides performance guarantees. We also show that our theory translates to significant improvements in existing feasible models, and enables new structured Lagrangian models of substantially smaller size.