Alexander Estes: The Submodular Adaptive Switching Problem

UMD Capital Area Theory Seminar - Fall 2024
Speaker: Alexander Estes
Title: The Submodular Adaptive Switching Problem
Date: September 12, 2024
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.