log in  |  register  |  feedback?  |  help  |  web accessibility
The Submodular Adaptive Switching Problem
IRB 3137 or Zoom: https://umd.zoom.us/j/6778156199?pwd=NkJKZG1Ib2Jxbmd5ZzNrVVlNMm91QT09
Thursday, September 12, 2024, 2:30-3:30 pm
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

We define and study an optimization problem called the adaptive switching problem. Suppose that there is a system with a finite number of configurations and a set of times, called a time scale, at which the configuration may be switched. The time scale can be any closed subset of the real numbers, so that decisions may be made continuously, at discrete points in time, or some combination of the two. While a configuration is active, the system provides a reward that depends on the entire history of the system. In addition, decision-dependent information is collected as the system progresses, and the decision-maker may adapt their choices to the observed information. The goal is to identify a policy that maximizes the expected accumulated rewards. Applications include advertisement configuration selection and viral marketing. We develop definitions of monotonicity and submodularity in this setting. For problems exhibiting monotonicity and submodularity properties, we show that a greedy policy achieves an approximation ratio. These results are the first that apply simultaneously to the case wherein decisions are made at discrete points in time and that wherein decisions are made continuously over time. These are also the first to apply to more general time scales that may include a mixture of discrete time steps and continuous time intervals. In addition, the results that we provide are the first results relating to situations in which the decisions are adaptive and made continuously over time.

Bio

Alexander S. Estes is an assistant professor at the University of Maryland with a joint appointment in the Institute for Systems Research and in the Department of Decisions, Operations, and Information Technology, Robert H. Smith School of Business. His research interests include discrete optimization, statistics, and data science, often with applications to air traffic management.

This talk is organized by Kishen N Gowda