Online Control in Population Dynamics

Thank you for your time and comments! Unfortunately we believe that the reviewer has missed the point of the paper, which is to extend non-stochastic control methods to population dynamics. See below for responses to specific criticisms:

Idealized Assumptions? The review claims that we assume Gaussian noise. This is incorrect. Our algorithm can deal with unknown adversarial perturbations (which is one of the main benefits of the non-stochastic control methodology).

Known transition matrices is a standard assumption in online non-stochastic control. Results established for known systems can often be extended to unknown systems with a similar regret guarantee (see the list of papers below). However, this is out of scope of our current work, which is focused on establishing a new framework for controlling population dynamics.

[1] Simchowitz, Max, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. Conference on Learning Theory. PMLR, 2020.

[2] Chen, Xinyi, and Elad Hazan. Black-box control for linear dynamical systems. Conference on Learning Theory. PMLR, 2021.

[3] Gradu, Paula, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. Advances in Neural Information Processing Systems 33 (2020): 10764-10774.

[4] Simchowitz, Max. Making non-stochastic control (almost) as easy as stochastic. Advances in Neural Information Processing Systems 33 (2020): 18318-18329.

Generalization to highly non-linear/complex systems? In fact, many of the systems studied in our experiments (e.g. SIR in section 4.1 and replicator dynamics in Section J) are highly non-linear. As discussed in Appendix G, our algorithm GPC-Simplex can nonetheless be naturally extended to such systems, and the experimental results are promising.

It is true that our theoretical results are limited to linear systems. However, this is the case for almost all existing theoretical guarantees in the control theory literature. Obtaining provable guarantees for non-linear systems is generally considered a very challenging research direction, and the linearity assumption has proven to be a good testbed for algorithm design in the past. For a concrete example, note that the original GPC algorithm (Agarwal et. al. 2019) also has theoretical guarantees restricted to linear systems.

Returning to empirical performance: we agree that experimenting with more complex scenarios is a valuable direction for future research, but it is outside the scope of this (primarily theoretical/conceptual) work. The goal of this work was to propose a robust framework for the long-standing problem of controlling population dynamics. To the best of our knowledge, all prior methods for this problem relied on much more restrictive assumptions (e.g., known costs, no noise, closed-form solution based on differential equations); see the references below.

[1] Mohamed Elhia, Mostafa Rachik and Elhabib Benlahmar. Optimal Control of an SIR Model with Delay in State and Control Variables. International Scholar Research Notices, 2013.

[2] Gul Zaman, Yong Han Kang and Il Hyo Jung. Optimal treatment of an SIR epidemic model with time delay. BioSystems, 2009.

[3] E.V. Grigorieva, E.N. Khailov and A. Korobeinikov. Optimal Control for a SIR Epidemic Model with Nonlinear Incidence Rate. Math. Model. Nat. Phenom, 2016.

[4] Luca Bolzoni, Elena Bonacini, Cinzia Soresina, Maria Groppi. Time-optimal control strategies in SIR epidemic models. Mathematical Biosciences, 2017.

[5] Urszula Ledzewicz and Heinz Schättler. On optimal singular controls for a general SIR-model with vaccination and treatment. DYNAMICAL SYSTEMS, 2011.

Sensitivity to Parameters? We are not sure of the basis for the reviewer's criticism that the performance of the algorithm is particularly sensitive to the choice of parameters. Our theoretical results provide guidance for setting the parameters (e.g. policy horizon $H$ and learning rate $\eta$) based on a choice of $\tau$ (mixing time of comparator class) and an upper bound on $L$ (Lipschitz constant for cost functions), which are both problem-specific. For our empirical results we did not need to tune the parameters across experiments; for all experiments we took $H = 5$ and $\eta$ as defined in Appendix G. This suggests that parameter tuning is not critical to the algorithm's performance in practice. Of course, designing adaptive algorithm is in general an interesting research area, but it is beyond the scope of this work.

Experimental Scope? As we mentioned previously, this is a theory-focused paper, and the primary role of our experiments is to serve as a validation of the theoretical framework. Therefore, although conducting experiments on real-world data would be interesting, we argue that it is not necessary for this work.

Question 1. First, we want to reiterate that we do not assume Gaussian noise. In the SIR experiments in Appendix I.1, the perturbations are not Gaussian either. We do assume known dynamics. For unknown systems, one could run one of the existing system identification algorithms to obtain an estimate for the system, and run our controller algorithm using those system estimates.

Question 2-5. As mentioned previously, this is not an experiment-focused paper. These are certainly valuable research directions and would lead to interesting follow-up works. However, they are out of scope of this work. The main focus of the work, again, was to provide a new framework for controlling population dynamics using tools from non-stochastic control theory --- a connection between two fields that has not previously been considered.

Thank you for your time and comments! We are glad that you appreciated our paper. We address your comments and questions below:

Intuition about simplex LDS conditions. The assumption that the control norm is independent of the state is indeed needed for technical reasons: without it, since $Ax$ is multiplied by $1-\|u\|_1$ in the transition dynamics (see Eq. (4)), even a "linear'' policy $u := Kx$ does not induce a linear transition. Hence, it's not clear how one might define mixing time of a fully general linear policy (since it may not correspond to a Markov chain over $[d]$). It is a very interesting question whether there is a more natural (yet still tractable) definition of a simplex LDS that avoids this issue. We will add some discussion about this issue to the text.

Figure/label sizes. Thanks for pointing this out, we will try to make them larger.

Thank you for your time and comments! We are glad that you found the problem of great interest, and found our paper easy to follow. We address your questions and concerns below:

Novelty of the proposed algorithm. First, we reemphasize that the original GPC algorithm does not work in the simplex LDS setting. When there are no perturbations to the system, the original GPC algorithm simply plays its initialization policy for all time, which is highly unlikely to perform well. As discussed in Section 3, the fundamental issue is that GPC only competes against strongly stabilizing policies, but in a simplex LDS, no policy is strongly stabilizing. Indeed, prior to our work, this reliance on strong stability was a limitation of the entire literature on non-stochastic control.

This is why solving the control problem in the simplex LDS setting requires a new algorithm. From a bird's eye view, our proposed algorithm GPC-Simplex indeed looks similar to GPC --- hence the name --- but the differences are conceptually important. As discussed in Section 3, the key difference is that we augment the class of disturbance-action policies (over which we are optimizing via mirror descent) with an additional parameter $p_t$ that roughly represents the optimal stationary distribution that we would like to converge to in the absence of noise. This depends on the future sequence of adversarial cost functions, and hence must be learned in an online fashion along with the other parameters. The upshot is that this modification enables competing against not just policies that strongly stabilize the system (which do not exist in population dynamics), but also policies that mix the system (which are highly natural in population dynamics).

From a broader perspective, one contribution of our work is to show that even though non-stochastic control requires some assumptions to be tractable, strong stabilizability is not the end of the story. In particular, the tools from non-stochastic control can be modified to work even in some (theoretical and practical) settings where strong stabilizability is completely unreasonable and standard GPC fails. We believe that this perspective may be valuable even beyond the specific setting of population dynamics.

Non-uniform Lipschitz constant?

Certainly Theorem 7 would still hold with $L$ replaced by the maximum of $L_t$ over $1 \leq t \leq T$. If this maximum scales asymptotically slower (in $T$) than $\sqrt{T}$, then we still get sub-linear regret. If it scales as fast as $\sqrt{T}$ or faster, then (with no other control on the sequence of $L_t$'s) we would expect that achieving sub-linear regret is provably impossible by standard lower bounds from online convex optimization. It's plausible that tighter bounds are possible if e.g. the $L_t$'s are small on average, but we have not investigated this direction, as a uniform Lipschitz bound is the standard assumption in the control literature.

Thank you for your time and comments! Please see below for our responses to your concerns:

Motivation for simplex LDS? The basic motivation for the simplex LDS model, as discussed in the paper, is as a specialization/adaptation of the general LDS model to population dynamics, i.e. settings where the state is always a distribution. While there could be alternative models, we would argue that the constraints in the simplex LDS definition are for the most part fairly minimal. We are happy to add some discussion of potential generalizations and the technical obstacles to relaxing our assumptions.

Additionally, insofar as all models are wrong and should be justified by the algorithms they suggest, our experiments (in a variety of well-studied scenarios, not all of which satisfy the assumptions of the simplex LDS model or even the general LDS model) suggest that GPC-Simplex is a useful algorithm, and thereby vindicate the utility of the simplex LDS model as a theoretical tool for algorithm design.

Examples where $\gamma_t$ is observable? Note that even if we did not require knowledge of $\gamma_t$, the algorithm still requires knowing the proportions of individuals of different types in the population, which seems unavoidable for controlling the system. The assumption that we know $\gamma_t$ simply requires that we can additionally observe the total size of the population. Examples where this is feasible include many ecological settings, where e.g. the Mark-Recapture technique is often used to estimate the number of individuals.

Time complexity? As stated in Theorem 7, the time complexity of our algorithm is polynomial in the dimension and number of iterations; the computational bottleneck is the mirror descent subroutine, which requires solving a simple convex program. From a practical perspective, we remark that the time complexity is comparable to that of the standard GPC algorithm (Agarwal et al. 2019) for controlling general linear dynamical systems.

Additional comments. Thank you for the helpful comments about the figure sizes and order of experiments; modulo space constraints we will attempt those changes. Also as you suggested, we will add a section discussing the practical implications of our technical assumptions. We will remark that this work is only the first step towards more robust methodologies for control in population dynamics. There are numerous important directions for future research, including generalizations of the simplex LDS model, assumptions complementary to our mixing time assumption, and development of theoretical guarantees for non-linear systems.