Learning to Stop: Deep Learning for Mean Field Optimal Stopping

We sincerely thank the reviewer for the constructive suggestions to improve our paper. We provide detailed responses to each of your questions below.

(Theoretical Claims) We would like to thank the reviewer for spotting a typo in the proof of Lemma A.1. We corrected the proof by modifying lines 694, 695, and 747 in the original manuscript. Following the argument presented, in the end we obtain with the following inequality:

$E\left[\|\nu_{n+1}^{N,p} - \nu_{n+1}^{p}\|\right]\leq \frac{|S|}{4\sqrt{N}}(\frac{1 - K^{n+1}}{1- K}) + K^{n+1}E[\lVert \nu^{N,p}_0 - \nu^p_0 \rVert],$

where $K=(L_F (1 + L_P))$. We remark that this updated inequality does not affect our conclusion as the convergence rate remains the order of $\mathcal O (1/\sqrt N)$.

(Experimental Designs or Analyses) Although we agree that the experiments are relatively simple (compared with real-world applications), establishing a solid theoretical framework and validating our algorithms through progressively more complex examples was a necessary step towards tackling real-world applications. We want to emphasize that all the experiments presented are intended as proof-of-concept demonstrations. Each of them was carefully designed to demonstrate specific features of MFOS. As mentioned in lines 406-411, we include common noise in Example 6 to show that our method has potential beyond the theoretical framework covered in our proofs (see Appendix E.6 for more details on this example). We will add more explanations about how to extend the theory to cover the common noise.

(Originality and Significance) Multi-agent problems have become a central topic in the machine learning community. The optimal stopping problem has not yet been extensively studied in the literature in a multi-agent scenario. MAOS fits neither in classical optimal stopping, nor in classical MDP theory. To the best of our knowledge, our work is the first to propose deep learning algorithms to efficiently address this class of problems, through the lens of mean field MDPs. If the reviewer has specific suggestions about potential improvements, we would be grateful and we would try to provide a more detailed answer.

(Question) Thank you for this clarification question. In the setting we consider, all the agents are implicitly forced to stop when the problem reach the time horizon $T$. Concretely, we enforce $p_T^i(\cdot) = 1$. In this way, the stopping time $\tau^i$ defined at line 146 is always less than or equal to $T$. We will clarify this point in the text.

We sincerely thank the reviewer for the helpful suggestions to improve our work, especially for raising the connection to the options framework in reinforcement learning. While we agree that this seems connected to MFOS in spirit, we believe that we cannot make one fit in the other. We list specific points below.

• Options framework: There are three main challenges that make it difficult to compare our work directly with the options framework.
  1. Once an agent decides to stop, they stay in their current state until terminal time $T$, whereas in the options framework, when the current option terminates, the agent has the possibility to pick a new option and her state keeps changing.
  2. The "termination" criterion in our framework is controlled by the agent itself whereas in the options framework, the termination of the option is exogeneous to the agent and most of the time completely random.
  3. We are working in a finite-horizon setting with non-stationary policies whereas the options framework seems particularly relevant for infinite horizon discounted setting;
• SMDP: Our problem’s non‐Markovian nature differs from the semi‐MDP formulation found in options theory. In a semi‐MDP, the next state depends only on the current state and action, while the transition time can be random. In contrast, in our original framework, the transition depends on the agent’s entire history: the dynamics depends on whether the agent has stopped before or not. To make the problem markovian again, we need to introduce the augmented state space (Section 2.3) to capture the status of stopping decisions.

Given these limitations, we believe that it is not possible to represent mean-field optimal stopping as an option framework, although the two share some similarity in spirit. We are open to further discussions.

In the final version, we will include a summary of the above discussion on the options framework in RL. The typos will be corrected in the final version. We hope these arguments clarify our approach and may improve the reviewer’s assessment. Of course, we remain open to further discussion on these points.

First of all, we would like to sincerely thank the reviewer for their detailed review, which highlights our contributions and originality, and for the constructive suggestions to improve our manuscript.

(Restricted to Finite State Mean-Field). We agree with the reviewer that focusing on a finite‐state mean‐field setting is a limitation, and we plan to explore continuous settings in future work. However, we would like to emphasize that this is the first work to both model and propose deep learning algorithms for multi‐agent optimal stopping in this setting. We believe this represents a fundamental step before tackling more complex scenarios.

(Typos). We thank the reviewer for taking the time to carefully read our work. We have corrected the typos and improved the readability in the final version.

(Highlight Randomization Requirement). The randomized stopping policies are a key aspect of this work, as emphasized by the reviewer. Following the proposed modifications, we have strengthened the argument in the main text.

(Essential References Not Discussed and Classical Baselines). We thank the reviewer for directing us to these important works on optimal stopping. In response, we will update the introduction to more clearly position our method relative to LSM and the work of Tsitsiklis & Van Roy (1999), comparing the different approaches. Although our first two examples already compare our algorithm’s solution against the analytical solution obtained via dynamic programming, we agree that conducting additional comparisons with established classical methods will strengthen our argument.

(Experimental Details). We agree with the reviewer that including a description of the network´s architecture in the main text (section 6) will help the reader better understand the results. We thank the reviewer for the valuable suggestions, which we will incorporate into the final version.

Runtime and Memory Usage - Regarding the reviewer's question and observations on runtime and memory usage we have briefly commented on the training time and computational resources in Appendix D. To provide a more quantitiative analysis, we list the memory usage and required training time per 100 iterations in the following table, for a varying size of problem with different time horizons and dimensions. We fix the batch size to be 128 and deep networks to have around 260k parameters.

• From the table, we see that memory usage for the direct approach (DA) scales as $O(DT)$, where $D$ is the problem dimension and $T$ is the time horizon, while the dynamic programming approach (DP) only requires memory of $O(D)$. We also observe that DA in general requires more memory than DP, which makes DP the most preferable approach for problems with long time horizons or very high dimensions, as we have discussed in the paper.

• As for the running time, the time horizon $T$ has a crucial impact on the required time per $100$ iterations, while the dimension plays a relatively minimal role. While DA tends to run slower per hundred iterations, we want to stress that in practice it takes less than $2000$ iterations for DA training, but would usually requires around $200 * T$ total iterations for DP training. Therefore, DA still could be faster in training time compared with DP when the memory usage is affordable.

Based on these quantitative data, we believe that our proposed approaches are quite scalable, and therefore still feasible for long-horizon, high dimensional problems and are of pratical impact in real scenarios.