Deep Learning Algorithms for Mean Field Optimal Stopping in Finite Space and Discrete Time

Thank you for your comments. We provide detailed answers below. If further clarifications are needed, please feel free to ask. Otherwise, we hope that you will consider raising your score.

Weakness (notations): We are sorry that the notations are quite complex. We made some efforts to clarify some of them in the revised version. For $A$ and $a$ specifically, our rationale was that: $A$ stands for "Alive" while $\alpha$ stands for "action" (which is to stop or not). So $A=1$ means the agent has not stopped yet; when the agent stops, $\alpha=1$, and $A$ switches to $0$. We have added a sentence to clarify this on lines 196-198. One advantage of using this convention is that we can write the cost as in Eq. (6); otherwise, we would have to replace all the $\alpha$'s by $(1-\alpha)$. We are open to discussing other notations to ensure our paper is as clear and concise as possible.

Questions 1 (individual vs common randomization): Thank you for your question. This comment is not central to our paper so we removed the expression "and differs from the randomization of the central planner on policies" to avoid any confusion. But let us explain better here. The central planner chooses a policy, which is a function $p$, where $p_n(s,\nu)$ gives the stopping probability for an agent when her state is $s$, the time step is $n$, and the mean field is $\nu$. So the agent will sample a random variable for herself to decide to stop or not by using a Bernoulli random variable with parameter $p_n(s,\nu)$. We call this randomness the "individual randomization". Our comment meant to say that (in the whole paper) $p$ is a deterministic function, and the randomness is only at the individual level. One could also consider that $p$ itself is a random function, which would be interpreted as randomness at the central planner's level (or "common randomization"). But this would add an extra layer of complexity without bringing any clear way to find better policies.

Questions 2 (definition of $p$): By using the notation $p:\{0,\dots,T\}\times\mathcal{X} \to[0,1]$, we mean that we can view $p$ as a function of time and space taking values in $[0,1]$. Alternatively, it can be viewed as a sequence $(p_n)_{n=0,\dots,T}$. For every $n \in \{0,\dots,T\}$ and $x \in \mathcal{X}$, $p_n(x) = p(n,x)$ is interpreted as the probability to stop at time $n$ in the state $x$. In other words, $p$ is the parameter of the Bernoulli distribution according to which the agent will choose to stop or not. When $p_n(x)$ is larger, agents in $x$ have higher probability of stopping.

Questions 3 (Lipschitz condition): Thank you for raising this technical point. Actually, since the objects are finite-dimensional, all the norms are equivalent. But to be specific, we use the total variation distance (see Appendix A.2 line 733, when we use the definition of the metric). Notice that the space we are working on has finite dimension $2|\mathcal X|$ where $\mathcal X$ is the state space. In the new Remark A.2, we stressed the fact that in finite dimensional spaces it is equivalent to the 2-Wasserstein distance which is the natural distance used in continuous spaces, see e.g., Carmona and Delarue (2018).

Based on these responses to your valuable feedback, we hope you will consider increasing your score for our paper.

Question 1 (Existing results on rate of convergence): Similar results indeed exist in the literature on mean field control (MFC). For example Corollary 1 in (Cui et al., 2024), but it does not provide a rate of convergence while we do. Theorem 2.1 of (Motte and Pham, 2022) is also in a similar spirit to our problem. However they consider infinite horizon discounted MFC while we focus on finite-horizon MFOS. So these existing results do not apply to our problem and our proof is tailor-made. Notice that it gives not only a rate of convergence but even the constant in the big $\mathcal{O}$ is explicit (see the proof of Theorem A.3 in Appendix).

Question 2 (Robust approximation): Thank you for raising these two points:

1. "Is the mean-field dynamics easy to learn/differentiate in real-world applications with a finite number of agents?": For the type of problems we consider here, the interactions between agents are through the empirical distribution (see Eqs. (1)-(2)). So the computational complexity is related to how the dynamics and cost functions depend on this distribution. About learning: it would be interesting to investigate the question of learning the model, as has been done for mean field control e.g. in (Pásztor et al., 2023) (these results do not apply directly to our setting though). Because MFOS is close to (but not same as) MFC, this paper gives hope that we can indeed learn the model efficiently in our problems as well. About differentiating: with our approach, the input is the mean field $\mu^N_n$ and not the vector of positions for all the agents $(X^1_n,\dots,X^N_n)$. So we expect that the complexity only scales with the dimension of the mean field (i.e., the number of states) and not with the number of agents. For the complexity with respect to the number of agents, see also our reply to Question 1 of Reviewer SfDE.

2. "Are the proposed algorithms robust to any estimation errors in the mean-field dynamics?" Thank you for raising this interesting question. Although we did not address this question explicitly, the techniques used to prove Theorem 2.2 show that the MAOS problem is robust to a perturbation of the distribution. Furthermore, our Example 6 shows that even when the distribution is perturbed by a common noise, the algorithms still perform very well. Rigorously proving the stability of deep neural network algorithms is very challenging and is left for future work.

We hope that these clarifications will convince you to support our paper and raise your score.

New references:

Pásztor, B., Krause, A., & Bogunovic, I. . Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning. Transactions on Machine Learning Research (2023).

Cui, K., Hauck, S. H., Fabian, C., & Koeppl, H. Partially Observable Multi-Agent Reinforcement Learning using Mean Field Control. In ICML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists.

Han, J., Jentzen, A., & E, W. . Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115(34), 8505-8510 (2018).

Huré, C., Pham, H., Bachouch, A., & Langrené, N. Deep neural networks algorithms for stochastic control problems on finite horizon: convergence analysis. SIAM Journal on Numerical Analysis, 59(1), 525-557 (2021).

We thank you for the supportive review, and for highlighting our work as well-structured and demonstrating strong empirical performance. We have addressed each of the points in detail, aiming to clarify any doubts and justify a higher score. If further clarifications are needed, we would appreciate further references regarding the weaknesses mentioned.

Weakness 1 (MFOS vs MFRL): Thank you for pointing out a possible connection with "mean field RL" but could you please provide a specific reference please? We are not sure what you mean by "MFOS is a special class of mean field RL". Please note that our paper does not discuss reinforcement learning (RL) at all. Furthemore, in this paper we consider a cooperative problem, so methods for non-cooperative multi-agent settings (e.g., Nash equilibria) are not relevant for our problem.

Weakness 2 (Rate of convergence): We provided more information in point 4 of the common reply but please let us know if you would like further clarifications.

Weakness 3 (Model knowledge): Thank you for pointing out that it would be interesting to investigate model-free methods. We stress that in this work, we propose the first computational methods for mean field optimal stopping. With this in mind, we focus on situations where the model is known as stated in line 099. Model-free methods will be explored in future works. However, please evaluate our paper in the context of deep learning methods for optimal control and optimal stopping. For example, (Becker et al., 2019) for optimal stopping problems, and (Han et al., 2018; Huré et al., 2021) for optimal control are assuming that the model is known and have received considerable attention from the optimal control and machine learning communities.

Weakness 4 (Comparison between algorithms): Thank you for this interesting question. We provided more information in point 3 of our common reply. In addition, we want to add the following. As far as the memory required for the parameters of the neural network (NN), we agree with you that "it may be better to have a single time-dependent neural network (as required by DA)". However, DA requires differentiating through the whole trajectory during backpropagation, the memory required for this increases with $T$. (This is not just backpropagation through the NN layers, which is well optimized. It is backpropagation through the entire state's trajectory.) On the other hand, the DP approach proceeds step-by-step, requiring backpropagation through one time step only, with memory requirement independent of $T$.

Weakness 5 (Extensions to MARL): Thank you for your positive comment. This paper is a first step towards efficient computational methods for large-scale MAOS. While we assume full knowledge of the model for now, we hope our work will attract more attention to this problem and will be used as a basis for model-free RL methods in the near future. Our examples are new and have been designed for this family of MAOS problems. They can hopefully be used as benchmark problems by other authors in future works.

We thank you for recognizing the novelty of our work and its solid theoretical foundations. We are uncertain about why the initial score of 8 was changed to 6 and we hope that you will remain supportive of our work and will consider reverting the score to 8. We have addressed all the comments with detailed explanations below.

Weakness: Thank you for the suggestion. We have added a motivating example (Distributional Cost), at the end of Section 2.1. We believe it is important to introduce a simpler, yet equally interesting, example in the early sections to familiarize the reader with the topic. Note that this example is later solved in Section 6 as Example 4. For further details on the example, please refer to our previous response.

Question 1 (Propagation of chaos): The intuition of Theorem 2.2 is based on the so-called "propagation of chaos". We gave explanations in the first paragraph of Section 2. We can also give the following comparison with LLN. LLN can be used only at time $0$ because $(X^i_0)_{i=1,\dots,N}$ are independent, and only to approximate an expected value by an empirical average. However, it cannot be applied at future times (because the particles are interacting) and it cannot be used to compute more complex functions of the population distribution. Propagation of chaos allows us to do that based on the intuition that, when $N$ goes to infinity, particle trajectories become decoupled because they only see the population distribution (which is deterministic in the limit $N=\infty$). To be specific, propagation of chaos yields that the empirical distribution of the $N$ particles converges to the state distribution of the limiting process. For more information, see e.g., Sznitman (1991). However, notice that we do not use an existing propagation-of-chaos result. We prove it completely, with arguments tailored to our problem, which allows us to get an explicit rate of convergence in Theorem 2.2 (even the constant in the big $\mathcal{O}$ is explicit, see the proof of Theorem A.3 in Appendix).

Question 2 (Architecture): Thank you for the question. In fact, we described in details the neural network architectures in Appendix D, in paragraph "Neural Network Architectures". We summarize here the main points. For all the numerical experiments conducted in this work, we use an MLP with residual connections and a varying hidden dimension. We processed the inputs to neural nets to acquire an embedding vector of same dimension that represents the information. We embed time using a fixed sinusoid vector, embed state with a learnable embedding table and embed mean field distribution vector with a learnable MLP. We found that this architecture is the most efficient among the ones we tried, although our algorithm can work with various other architectures. However, we do not think that shallow neural networks (e.g., with just one hidden layer) are enough for solving the numerical problems considered in this work, particularly for the more complex examples.

We appreciate your support and we hope that these answers (and the ones given to other reviewers) will convince you to raise your score.

New reference:

Sznitman, A. S. (1991). Topics in propagation of chaos. Ecole d’été de probabilités de Saint-Flour XIX—1989, 1464, 165-251.

Questions 1 (complexity in N): We are not aware of any results about the exact complexity of MAOS. However, we note that existing references only tackled models with a very small number of agents. For instance Best et al. (2018) has only up to 8 robots. Furthermore, there is a connection with optimal multiple stopping problems, in which the goal is to choose $N$ distinct stopping times. These problems are simpler than ours because there are no interacting agents. We note that for instance Han et al. (2023) solve the problem with $N$ only up to $3$. Last, to solve MAOS without using mean-field approximations, there are 2 issues:

1. The stopping decision should be a function of the vector of all the agents' states $(X^1_n,\dots,X^N_n)$, whose dimension increases linearly with the number $N$ of agents. We would expect computational complexity at least polynomial in $N$.
2. At every time step, one needs to find the optimal subset of agents to stop (see e.g., Eq. (3.3) in (Talbi et al., 2022)). But the number of subsets is exponential in the number of agents.

In the mean field limit, these issues are avoided.

Question 2 (comparison of algos): Please see point 2 in our common reply.

Question 3 (single vs multi-agent): We provide some background information in point 1 of our common reply. To be more specific, let us compare with the method of Becker et al. (2019). First, they do not consider at all a direct approach like our Algo. 1. The algo. of Becker et al. is based on DPP, like our Algo. 2, but in a very different form. The only common point is that the value function is computed backward in time. But they optimize the stopping decision for a single agent, while we optimize for a whole population, hence solving the MFOS problem. trying to apply their method in our problem would lead to one of the two issues described in point 1 of our common reply. We hope this answers your question. If not, could you please clarify what you mean by "on a per agent basis"?

Question 4 (time inconsistency): We use this term to mean that the problem, in its initial formulation (Eq. (3)), is not Markovian and therefore does not satisfy the Bellman optimality principle. Specifically, the transition from time $n$ to $n+1$ does not depend only on $X^\alpha_n$ but also on $\mu^\alpha_n$. In particular, agents that have stopped in the past remain stopped. This information is not included in the state $X^\alpha_n$ and hence its evolution is not Markovian and we cannot derive a DPP based purely on $X^\alpha_n$. Our use of the word time inconsistent is in line with other works, such as (D. Andersson & B. Djehiche, 2010) which stated "the cost functional is also of mean-field type, which makes the control problem time inconsistent in the sense that the Bellman optimality principle does not hold".

Question 5 (extended state): As mentioned in Section 2.3 (line 208) "The idea of extending the state using the extra information is similar to Talbi et al. (2023)". However, our Eq. (5) is in discrete time and space while their evolution is in continuous time and space (see Eq. (2.7) in the aforementioned paper). It implies that the methods are completely different since they choose to rely on partial differential equations, which do not make sense in discrete problems.

Question 6 (role of mean field in Eq. (5)): In Eq. (5), the evolution of the representative player state $X_n^\alpha$ is given by $F(n, X_n^{{\alpha}}, \mathcal{L}(X_n^\alpha), \epsilon_{n+1})$, which involves the law $\mathcal{L}(X_n^\alpha)$ of the random variable $X^\alpha_n$. So the state's evolution involves the distribution of the state itself. If we remove this term $\mathcal{L}(X_n^\alpha)$, then the problem reduces to a standard optimal stopping problem for one single agent. However, the presence of this term means that the agent cannot find an optimal stopping time without taking into consideration $\mathcal{L}(X_n^\alpha)$. When transitioning from the single-agent case to the multi-agent case, the crucial step involves accounting for the interactions between an agent and the rest of the population.

In light of these clarifications, would you consider increasing your score? If not, could you please let us know which additional clarifications are needed?

New references:

Han, Y., & Li, N. A new deep neural network algorithm for multiple stopping with applications in options pricing. Communications in Nonlinear Science and Numerical Simulation, 117, 106881 (2023).

Andersson, D., Djehiche, B. A Maximum Principle for SDEs of Mean-Field Type. Appl Math Optim 63, 341–356 (2011).

Germain, M., Mikael, J. & Warin, X. Numerical Resolution of McKean-Vlasov FBSDEs Using Neural Networks. Methodol Comput Appl Probab 24, 2557–2586 (2022).

Huré, C., Pham, H., Bachouch, A., Langrené, N. Deep neural networks algorithms for stochastic control problems on finite horizon: convergence analysis. SIAM J Numer Anal 59(1):525–557 (2021).

Many thanks for your detailed review, which helped improve the quality of our paper. We have addressed all the points with detailed responses. Based on this, we hope you will consider raising your score.

Weakness 1 (motivations): Thank you for giving us the opportunity to clarify the motivations for MAOS. Please see points (1) and (2) in our common reply, and let us know if you would like more details.

Weakness 2 (writing):

• Title: Thank you for this suggestion. We made the choice of focusing on "mean field", but we could change it, for example to "Deep Learning Algorithms for Multi-Agent Mean Field Optimal Stopping in Finite Space and Discrete Time". If changing the title would help to increase your score, please let us know and we will do it.
• Abstract:
  • We added "stochastic processes" to avoid any confusion.
  • We rephrased how the DP method works: DPP gives a way to compute the value function and the stopping rule using backward induction.
• Contributions: it is for the discrete problem; we updated the draft.

Weakness 3 (structure): Thank you for the observation. Our main contributions are listed on page 2 (blue box). But in the revision, we follow your suggestion and we keep Sections 2.1 to 2.3 in Section 2 and then put Section 2.4 as a new Section 3.

Weakness 4 (minor): Thank you for raising these points. We corrected them in the revised paper. We provide explanations for some of the observations:

• Dimension, line 101 (former line 100): The problem dimension is explained in a dedicated paragraph at the beginning of Section 6, former Section 5 ("Problem Dimensions"): We count the total dimension of the neural network's input, which is $|\mathcal{X}| + 2 |\mathcal{X}| = 3|\mathcal{X}|$, where $|\mathcal{X}|$ is the dimension of an individual agent's state space.
• $\mathbb{N}$, line 127 (former line 126): In the definition of $F: \mathbb{N} \times\mathcal X\times\mathcal P(\mathcal X)\times E\to\mathcal X$, $\mathbb N$ represent the set of integers because the time variable is an integer. It is not the same as $N$, which is the number of agents.

We summarize here the main changes in the updated draft. We improved clarity and provided more motivations.

To make it easier for reviewers to track the updates, the changes made in the draft are highlighted in purple.

• The "Introduction" and the "Related Work" paragraph have been updated.
• Line 110, we added a reference to (Sznitman, 1991) for background on the propagation of chaos.
• We added a "Motivating Example" at the end of Section 2.1 (Distributional Cost).
• To increase clarity, we added blue boxes for the main contributions (p.2) and the 3 main theorems; we also added a paragraph containing the major challenges addressed by this work at the end of Section 2.1 (red box).
• To avoid confusion, we removed the comment about common randomization in Section 2.2.
• We added a sentence in Section 2.3 to clarify the notations.
• We moved Section 2.4 in a separate section (new Section 3).
• The conclusion has been updated.
• We moved to Appendix E.1 and E.2 the brief descriptions of Example 1 and Example 2 respectively, due to space constraints.
• We placed the details of the transition probabilities of Example 3 in Appendix E.3.
• We added a comment on the metric that has been used in the proofs (total variation distance) in line 733.
• We corrected the typos pointed out by reviewer SfDE.

References for the common reply:

Daudin, S., Delarue, F., & Jackson, J. On the optimal rate for the convergence problem in mean field control. Journal of Functional Analysis, 287(12), 110660, (2024).

Germain, M., Mikael, J., & Warin, X. Numerical resolution of McKean-Vlasov FBSDEs using neural networks. Methodology and Computing in Applied Probability, 24(4), 2557-2586, (2022).