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

Authors: Yuchen Zhu, Lorenzo Magnino, Mathieu Lauriere
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Optimal Stopping, Mean Field, Deep Learning, Dynamic Programming

Abstract:
Optimal stopping of stochastic processes is a fundamental problem in optimization that has found applications in risk management, finance, economics, and recently in the fields of computer science. We extend the standard framework to a multi-agent setting, named multi-agent optimal stopping (MAOS), where a group of agents cooperatively solves finite-space, discrete-time optimal stopping problems. Solving the finite-agent case is computationally prohibitive when the number of agents is very large, so this work studies the mean field optimal stopping (MFOS) problem, obtained as the number of agents approaches infinity. We prove that MFOS provides a good approximate solution to MAOS.  We also prove a dynamic programming principle (DPP), based on the theory of mean field control. We then propose two deep learning methods: one simulates full trajectories to learn optimal decisions, whereas the other leverages DPP \blue{to compute the value function and to learn the optimal stopping rule} with backward induction; both methods train neural networks for the optimal stopping decisions. We demonstrate the effectiveness of these approaches through numerical experiments on 6 different problems in spatial dimension up to 300. To the best of our knowledge, this is the first work to study MFOS in finite space and discrete time, and to propose efficient and scalable computational methods for this type of problems.

Decision: reject
Reviewer scores: 5, 8, 6, 5

Reviews and discussion:
<thread>
creation date:
1730695913988

thread_type:
official_review

<thread_object>
creator: reviewer_ijgf

<content>
summary:
This paper studies the mean field optimal stopping problem in finite space and discrete time. Theoretically, the authors show that as the number of agents N goes to infinity, the optimal cost converges to its mean field limit at a rate of $N^{-1/2}$. They also show the dynamic programming principle in this setting. Numerically, the authors propose two algorithms, one directly optimizes the objective, and the other leverages the maximum principle. The authors apply the algorithms on 6 examples to test the efficacy.

strengths:
The numerical experiments are comprehensive, showing the effectiveness of the algorithm.

weaknesses:
Part of the article is not clear enough. I have put details in Questions.
The notations in the paper are complicated and hard to track. For example, stopping corresponds to $\alpha=1$ and $A=0$, while $\alpha=0$ and $A=1$ refer to continuing the dynamic. This causes some confusion.

questions:
Page 3 line 156. You mention that “randomized stopping times for individual agents differ from the randomization of the central planner on policies”. Why are they different? What should a central planner be like?

Page 4. What is the space for a stopping probability p? Is it a sequence of T functions in x, with values in [0,1]?

In assumption 2.1, you assume the Lipschitz condition of $\bar{F}$ and $\Psi$. However, you did not specify the metric in the input domain, which makes the assumption ambiguous.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730704440387

thread_type:
official_review

<thread_object>
creator: reviewer_v9zm

<content>
summary:
This paper studies a special form of mean field reinforcement learning (RL), the mean-field optimal stopping problem (MFOS), where each agent can only choose to continue or stop. The authors prove that MFOS is a good approximation of the multi-agent optimal stopping problem (MAOS) and characterize the convergence rate as the number of agents tends to infinity. They also propose two algorithms for optimizing the policy in MFOS. The authors verify the effectiveness of their proposed algorithms in several numerical simulations.

strengths:
The paper is well-structured and easy to follow because the authors provide sufficient background and motivations for the MFOS. The convergence rate concerning the number of agents (Theorem 2.2) should be a good contribution if it is the first theoretical result that characterizes the gap between multi-agent RL and mean field RL. However, I’m unsure if similar results exist in the literature on mean field RL. The proposed algorithms are natural and show a good empirical performance.

weaknesses:
Problem setting: MFOS is a special class of mean field RL. The readers may wonder why this work's theoretical guarantees and algorithms cannot directly apply to general transition kernels and action sets.

Theoretical results: The $1/\sqrt{N}$ convergence rate in Theorem 2.2 is not fast enough if we consider the practical number of agents in target applications (e.g., the number of drones in a fleet in Example 6). But it is good to see that this convergence rate is tight.

Algorithms: A major limitation is that both algorithms, Direct Approach (DA) and Dynamic Programming (DP), need to know the exact mean-field dynamics $\bar{F}$ and take derivatives of this function.

Besides, the authors mention that DP is "A more ideal treatment" than DA in Line 325. However, I do not see any rigorous reasoning through time/memory complexity. The only practical reason might be the training memory size mentioned in Line 374. But even when T is large, it may be better to have a single time-dependent neural network (as required by DA) rather than training T in different neural networks (as needed by DP).

Experiments: The examples are all about synthetic environments with known transition probabilities.
Despite the above limitations, I still feel this work makes contributions that should be interesting to the audience in the field of multi-agent RL.

questions:
I hope the authors can clarify whether similar convergence results like Theorem 2.2 exist in the literature of mean-field RL. If not, does the proof of Theorem 2.2 rely on the special structures of MAOS compared with general multi-agent RL?

Is the mean-field dynamics easy to learn/differentiate in real-world applications with a finite number of agents? Are the proposed algorithms robust to any estimation errors in the mean-field dynamics?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731149144030

thread_type:
official_review

<thread_object>
creator: reviewer_7hvt

<content>
summary:
This papers designs a mean field approximation method for solving multi-agent optimal stopping (MAOS). Theoretical justifications are provided establishing that the mean field approximation error is relatively small as number of agents goes to infinity. A dynamic programming principle is also established. Two algorithms are designed with neural networks modeling the policy functions. Adequate numerical experiments are provided.

strengths:
1. The paper is overall clear and well-written.
2. The idea is innovative.
3. Solid theoretical results are shown with practical interpretations.
4. Adequate numerical experiments are conducted for the proposed algorithms.

weaknesses:
I agree with the limitations discussed by the authors in Sec 6. Other than that, having some specific problem as an example in the first few sections could further improve readibility.

questions:
1. Is the intuition of Theorem 2.2 similar to Law of Large Numbers, in the sense that averaging the stop/continue of N agents starts to loose randomness as N gets larger? And the rate of 1 / \sqrt{n} could roughly be related to the rate of concentration for the average?
2. What is the structure of neural networks for the applications? I.e. some shallow fully connected layers, or are some specific architectures prefered?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731201572269

thread_type:
official_review

<thread_object>
creator: reviewer_sfde

<content>
summary:
This work focuses on optimal stopping of stochastic processes in the multi-agent setting. 
Prior work on optimal stopping: 
1. provided deep learning approaches in the single-agent case, 
2. extended the optimal stopping problem in the multi-agent case, referred to as multi-agent optimal stopping (MAOS).

Furthermore, as the MAOS problem complexity increases with the number of agents $N$, prior work:

3. has combined MAOS with mean-field approximation where $N\to\infty$ in the continuous time and continuous space setting.


This work builds on these approaches in that it considers a mean-field approximation for MAOS as in (2,3), but aims to develop computational methods as in (1).

It introduces two deep learning methods to efficiently find solutions, proving the approach efficient with experiments on high-dimensional problems.

strengths:
- Proposes two deep learning methods that leverage trajectory simulation and backward induction for optimal stopping.
- Empirical validation: demonstrates the effectiveness of the methods through experiments on high-dimensional problems

weaknesses:
## Lacking explanation of the motivation
The introduction does not give a motivating multi-agent example or explain examples of what kind of problems this work will allow to solve. 
I also did not understand by reading the introduction why the results (and deep learning approaches) from the single-agent setting do not extend to the multi-agent setting. The introduction should emphasize the main challenges for the extension.

## Writing

*Title*. This paper is about a multi-agent setting extension, and the title does not even mention that.

*Abstract*.
- starting with "optimal stopping of stoch. processes" would be clearer, because there are other studied stopping criteria
- I couldn't tell what the DPP proof implies. Perhaps describe what it implies for MFOS without assuming the reader knows DPP and its implications.

*Introduction*. The problem of the paper is very vague while reading the introduction. It would be helpful to provide a simple multi-agent optimal stopping motivating example so that ML readers can understand for which type of problems this problem is relevant.


*Other.*
- In the listed contributions it is unclear if (1) is for the discrete or the continuous case.

### Structure
The results are not in a separate section, making it hard to understand the contributions vs. the background. Section 2 contains existing models and subsection 2.4 gives one of the main theorems.

### Minor
- line 100: the text in brackets is unclear, do you mean the net's input can be up to 300? How was this determined?
- lines 108-109. At this point, only $N$ is introduced, but you use $\delta, X, k, \alpha$, etc. Moreover, this notation cannot be found later in the paper. 
- lines 116-118: It is weird that you first define  $P(\mathcal{X})$ and later $\mathcal{X}$.
- line 125: $\delta$ is not defined.
- line 126: typo mathds-$N$ should be $N$?
- line 133: missing 'is' (which is)
- line 139: write what is the expectation over in eq. (2)

questions:
1. Regarding prior MAOS work, precisely how does the problem complexity increase with N? 
2. From the two proposed Deep Learning approaches, which one is better (or in which case which one is better)?
3. Could you elaborate on how the deep learning approaches for discrete-time single-agent case OS problems (listed in line 84) differ from the approach taken here on a per-agent basis? 
4. I do not understand what you mean by "this makes the problem time inconsistent" in line 170. I understand that Markovian is comp. efficient, but do not understand why otherwise is "time inconsistent".
5. How does the extended state in Eq. (5) differ from Talbi et al. (2023)?
6. Since Eq. (5) is for a representative player, how does it differ from the singe-agent setting? Why is the most complex step in extending the single-agent results to the multi-agent setting? (with mean field)
</content>
</thread_object>

</thread>
<thread>
creation date:
1732033521793

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common Reply

comment:
We thank all the reviewers for their thoughtful and constructive feedback, which recognizes the strengths and innovative aspects of our work. We have addressed every comment in detail, aiming to clarify any ambiguities and reinforce the contributions of our manuscript. We hope these responses effectively resolve any concerns and demonstrate the value of our work, encouraging an improvement of the scores.

Before providing answers to each reviewer, we address a few key points in this common reply:

**1. Single vs Multi-Agent OS**: Optimal stopping (OS) focuses on a single-agent problem, and it is very different from multi-agent optimal stopping (MAOS). Indeed,
- In the single-agent case, the dynamics and the costs depend only on the individual agent's state; the stopping rule also depends only on that state.
- In MAOS, the dynamics and costs of agent $i$ involve the states of other agents, which creates an interdependence in the stopping decisions; the stopping rules are functions of the states of all the agents.
- We can envision two ways to use single-agent OS numerical methods for MAOS, but none of them is satisfactory:
	- First, we can view the whole system, consisting of the $N$ agents' states, as a single state, and apply OS methods for that state. Then the whole group has to stop at once. However, we want to allow agents to stop at different times.
	- Second, we can fix the behavior of $N-1$ agents, and solve the OS problem for the remaining agent. We need to update every agent iteratively in this way. But it is not clear why this would converge, and it is more likely to converge to a Nash equilibrium than a social optimum, as we want.

**2. Applications and examples:** Let us give more concrete motivations:
1. MAOS has gained significant importance in a variety of fields. Two specific applications are:
	- **Robotics:** in mission monitoring tasks, multiple mobile robots must observe the progress of another robot performing a specific task (Best et al., 2018).
	- **Finance:** pricing options with multiple stopping times (Kobylansky et al. 2011) can be viewed as an MAOS problem (see Talbi et al. (2024)).
2. To help understand MAOS, let us explain the **$N$-agent version of our numerical Example 4**:
	- Here, $F(n,x,\mu,\epsilon) = x+\epsilon$, which means that the next state of an agent is the previous state plus some random disturbance. Based on Eq. (1), the dynamics of agent $i$ is: $X_{n+1}^{i} = X_{n}^{i} + \epsilon_{n+1}^{i}$ if the agent does not stop, and $X_{n+1}^{i} = X_{n}^{i}$ otherwise.
	- The agents' states yield the empirical distribution $\mu^N_n$ (proportion of agents in each state).
	- Based on Eq. (2), if agent $i$ stops at time $n$, then she is incurred the cost: $\Phi(X^i_n,\mu^N_n) = \sum_{x} |\mu^N_n(x) - \rho_{\mathrm{target}}(x)|^2$, which is smaller if the agent stops when the population distribution matches the target one.
	- Some agents might have to stop even though the target distribution is not matched, so that others can later have a lower cost. This is a cooperative task to minimize the social cost.
	- Solving exactly the problem (finding the optimal stopping rule for every agent) is very complex. Our approach is to consider the mean-field problem which leads to an efficient solution (see Example 4, Section 6). Based on Theorem 2.2, the mean field solution provides a good approximation of the $N$-agent problem.

**3. DA vs DP algorithms:** We propose 2 algorithms, each with their own advantages. We refer to the dedicated paragraph "**Comparison of the Two Proposed Algorithms**" at the beginning of Section 6 (former Section 5). Based on empirical evidence,
- When computational resources are not a limitation, the stopping decision is learnt faster by the DA method than by the DP method.
- However the required memory for training with DA increases with $T$, whereas DP requires only constant order memory that is independent of the time horizon. This is because DA requires backpropagating gradients through the whole trajectory. So DP is more memory efficient when $T$ is large.
- Similar observations were made in continuous time optimal control by Germain et al. (2022); their local and global methods are analogous to our DP and DA methods respectively.

**4. Rate of convergence:** Theorem 2.2 justifies that the MFOS solution gives a good approximation of the MAOS problem, not only with an asymptotic result but with a rate of convergence of $\mathcal O(1/\sqrt{N})$. We want to stress that:
- It is possible that for some specific dynamics and costs with simple dependence on the mean field distribution, better rates can be obtained.
- However, under general conditions his result is expected to be optimal due to state-of-the-art results established in the mean field control literature (e.g., (Daudin et al. 2024).

For more details about each reviewer's points, please see our individual replies. We hope that these clarifications will convince the reviewers to increase their score.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper considers the mean-field optimal stopping (MFOS) problem, a multi-agent version of the optimal stopping in the limit where the number of agents becomes very large, so the agents are essentially playing against a mean field. The authors provide an approximation theorem connecting the mean-field approximation to large-but-finite numbers of agents, as well as a dynamic programming principle (DPP) that characterizes the mean-field solution. Finally, they provide two algorithms for solving the MFOS problem based on deep learning (but with no theoretical guarantees).

Most of the reviewers were on the fence about this paper, for several reasons:
- First, the paper is difficult to read, and the positioning of its contributions is somewhat unclear. The authors' comments and revisions did help in this regard, but did not fully alleviate the problem.
- Another concern was that the proposed algorithms require global knowledge of the exact mean-field dynamics, as captured by $\bar F$ (including being able to differentiate it). This assumption is conceptually ill-suited to the multi-agent setting, which the authors motivate as agents interacting and stopping on their own (that is, based on local algorithms / rules).

To be sure, the paper isn't without its merits. At the same time however, it was not possible to make a clear case for acceptance of the paper "as is" (that is, without considerable further revisions requiring a fresh look), and the paper was not championed during the discussion phase. As a result, it was decided to make a "reject" recommendation, while encouraging the authors to take into account the feedback provided by the reviewers and resubmit at the next opportunity.