A recent method for solving zero-sum partially observable stochastic games (zs-POSGs) embeds the original game into a new one called the occupancy Markov game. This reformulation allows applying [Bellman, 1957]'s principle of optimality to solve zs-POSGs. However, improving a current solution requires solving a linear program with exponentially many potential constraints, which significantly restricts the scalability of this approach. This paper exploits the optimal value function's novel uniform continuity properties to overcome this limitation. We first construct a new operator that is computationally more efficient than the state-of-the-art update rules without compromising optimality. In particular, improving a current solution now involves a linear program with an exponential drop in constraints.  We then also show that point-based value iteration algorithms utilizing our findings improve the scalability of existing methods while maintaining guarantees in various domains.

§ INTRODUCTION

§ BACKGROUND

§ EXPLOITING UNIFORM CONTINUITY

§ POINT-BASED VALUE ITERATION

§ EXPERIMENTS

[Aström, 1965]
Karl J Aström.
Optimal Control of Markov Decision Processes with Incomplete State Estimation.
Journal of Mathematical Analysis and Applications, 10:0 174–205, 1965.

[Bellman, 1957]
Richard E Bellman.
Dynamic Programming.
Dover Publications, Incorporated, 1957.

[Buffet et al., 2020]
Olivier Buffet, Jilles S. Dibangoye, Abdallah Safidine, and Vincent Thomas.
$\epsilon$-optimally solving zs-POSGs using Bellman's optimality principle.
Technical report, Inria Nancy Grand-Est, 2020.

[Cunha et al., 2023]
Rafael F Cunha, Jacopo Castellini, Johan Peralez, and Jilles S Dibangoye.
On convex optimal value functions for POSGs.
arXiv preprint arXiv:2311.09459, 2023.

[Delage et al., 2023]
Aurélien Delage, Olivier Buffet, Jilles S Dibangoye, and Abdallah Saffidine.
HSVI can solve zero-sum partially observable stochastic games.
Dynamic Games and Applications, pages 1–55, 2023.

[Dibangoye and Buffet, 2018]
Jilles Dibangoye and Olivier Buffet.
Learning to act in decentralized partially observable MDPs.
In Proceedings of the 35th International Conference on Machine Learning, pages 1233–1242, 2018.

[Dibangoye et al., 2016]
Jilles S Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet.
Optimally Solving Dec-POMDPs as Continuous-State MDPs.
Journal of Artificial Intelligence Research, 55, 2016.

[Dibangoye et al., 2013]
Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet.
Optimally solving Dec-POMDPs as continuous-state MDPs.
In IJCAI, pages 90–96, 2013.

[Filar and Vrieze, 1997]
J. Filar and K. Vrieze.
Competitive Markov Decision Processes.
Springer, 1997.

[Ghosh et al., 2004]
MK Ghosh, D McDonald, and S Sinha.
Zero-sum stochastic games with partial information.
JOTA, 121, 2004.

[Hansen et al., 2004]
Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein.
Dynamic Programming for Partially Observable Stochastic Games.
In AAAI, 2004.

[Horák and Bošanskỳ, 2019]
Karel Horák and Branislav Bošanskỳ.
Solving partially observable stochastic games with public observations.
In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.

[Horák et al., 2017]
Karel Horák, Branislav Bošanskỳ, and Michal Pěchouček.
Heuristic search value iteration for one-sided partially observable stochastic games.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.

[Nayyar and Gupta, 2017]
Ashutosh Nayyar and Abhishek Gupta.
Information structures and values in zero-sum stochastic games.
In 2017 American Control Conference (ACC), pages 3658–3663, 2017.

[Nayyar et al., 2013]
Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis.
Decentralized stochastic control with partial history sharing: A common information approach.
IEEE Transactions on Automatic Control, 580 (7):0 1644–1658, 2013.

[Neumann, 1928]
J. von Neumann.
Zur theorie der gesellschaftsspiele.
Mathematische Annalen, 100:0 295–320, 1928.
URL <http://eudml.org/doc/159291>.

[Oliehoek, 2013]
Frans Adriaan Oliehoek.
Sufficient plan-time statistics for decentralized pomdps.
In Twenty-Third International Joint Conference on Artificial Intelligence, 2013.

[Pineau et al., 2003]
Joelle Pineau, Geoff Gordon, Sebastian Thrun, et al.
Point-based value iteration: An anytime algorithm for pomdps.
In IJCAI, volume 3, pages 1025–1032, 2003.

[Smallwood and Sondik, 1973]
Richard D Smallwood and Edward J Sondik.
The optimal control of partially observable Markov decision processes over a finite horizon.
Operations Research, 210 (5):0 1071–1088, 1973.

[Smith and Simmons, 2006]
Trey Smith and Reid G Simmons.
Focused Real-Time Dynamic Programming for MDPs: Squeezing More Out of a Heuristic.
In Proceedings of the Twenty-First AAAI Conference on Artificial Intelligence, pages 1227–1232, 2006.

[Sokota et al., 2023]
Samuel Sokota, Ryan D'Orazio, Chun Kai Ling, David J. Wu, J. Zico Kolter, and Noam Brown.
Abstracting imperfect information away from two-player zero-sum games.
In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 32169–32193. PMLR, 2023.

[Sondik, 1978]
Edward J Sondik.
The Optimal Control of Partially Observable Markov Decision Processes Over the Infinite Horizon: Discounted cost.
Operations Research, 12:0 282–304, 1978.

[Szer et al., 2005]
Daniel Szer, François Charpillet, and Shlomo Zilberstein.
MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs.
In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, 2005.

[Tammelin, 2014]
Oskari Tammelin.
Solving large imperfect information games using CFR+.
CoRR, 2014.

[Wiggers et al., 2016]
Auke J. Wiggers, Frans A. Oliehoek, and Diederik M. Roijers.
Structure in the value function of two-player zero-sum games of incomplete information.
In ECAI, 2016.

[Xie et al., 2020]
Yuxuan Xie, Jilles Dibangoye, and Olivier Buffet.
Optimally solving two-agent decentralized POMDPs under one-sided information sharing.
In ICML, pages 10473–10482, 2020.

* Claims

Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?

Justification: The paper exploits recent uniform continuity properties in Theorem <ref> and Theorem <ref>, provides update and backup operators used in Algorithm 1, and conducts experiments to support claims about the efficiency of the proposed approach.

* The answer NA means that the abstract and introduction do not include the claims made in the paper.

* The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.

* The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.

* It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.

* Limitations

Question: Does the paper discuss the limitations of the work performed by the authors?

Justification: The sample sets are generated in a random manner, potentially resulting in the inclusion of superfluous points that can impact the efficiency of the proposed approach. While point pruning techniques can address this issue, they may necessitate trade-offs in terms of theoretical guarantees.

* The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.

* The authors are encouraged to create a separate "Limitations" section in their paper.

* The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.

* The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.

* The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.

* The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.

* If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.

* While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.

* Theory Assumptions and Proofs

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

Justification: All the proofs of our results are given in the appendix. We also properly referenced Theorems and Lemmas that our proofs rely upon.

* The answer NA means that the paper does not include theoretical results.

* All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.

* All assumptions should be clearly stated or referenced in the statement of any theorems.

* The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.

* Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.

* Theorems and Lemmas that the proof relies upon should be properly referenced.

* Experimental Result Reproducibility

Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

Justification: We add the source code as a supplementary material with the necessary scripts to reproduce our experimental results.

* The answer NA means that the paper does not include experiments.

* If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.

* If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.

* Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.

* While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example

* If the contribution is primarily a new algorith the paper should make it clear how to reproduce that algorithm.

* If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.

* If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).

* We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.

* Open access to data and code

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

Justification: We add the source code as a supplementary material with the necessary scripts to reproduce our experimental results.

* The answer NA means that paper does not include experiments requiring code.

* Please see the NeurIPS code and data submission guidelines (<https://nips.cc/public/guides/CodeSubmissionPolicy>) for more details.

* While we encourage the release of code and data, we understand that this might not be possible, so “No” is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).

* The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (<https://nips.cc/public/guides/CodeSubmissionPolicy>) for more details.

* The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.

* The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.

* At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).

* Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.

* Experimental Setting/Details

Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?

Justification: Our contribution is a planning algorithm and everything is provided in the source code we make available.

* The answer NA means that the paper does not include experiments.

* The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.

* The full details can be provided either with the code, in appendix, or as supplemental material.

* Experiment Statistical Significance

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

Justification: The algorithms' only source of uncertainty lies in the selection of sample sets. As the sample sets grow with iterations, we have provided anytime performances as a means to assess the effect of the sample sets on the performances.

* The answer NA means that the paper does not include experiments.

* The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.

* The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).

* The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

* The assumptions made should be given (e.g., Normally distributed errors).

* It should be clear whether the error bar is the standard deviation or the standard error of the mean.

* It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.

* For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).

* If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.

* Experiments Compute Resources

Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

Justification: We provide these details in the Supplementary Material of the paper.

* The answer NA means that the paper does not include experiments.

* The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.

* The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.

* The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).

* Code Of Ethics

Question: Does the research conducted in the paper confor in every respect, with the NeurIPS Code of Ethics <https://neurips.cc/public/EthicsGuidelines>?

Justification: We fully read and adhered to the NeurIPS code of Ethics.

* The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.

* If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.

* The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).

* Broader Impacts

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

Answer: .

Justification: We believe that at the current stage, this work does not have any societal impact.

* The answer NA means that there is no societal impact of the work performed.

* If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.

* Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

* The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.

* The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.

* If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).

* Safeguards

Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?

Justification: We believe that this research poses no such risks as it's mainly theoretical research.

* The answer NA means that the paper poses no such risks.

* Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for actionled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.

* Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.

* We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.

* Licenses for existing assets

Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

Justification: We follow the CC BY-NC-SA 4.0 practices.

* The answer NA means that the paper does not use existing assets.

* The authors should cite the original paper that produced the code package or dataset.

* The authors should state which version of the asset is used and, if possible, include a URL.

* The name of the license (e.g., CC-BY 4.0) should be included for each asset.

* For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.

* If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, <paperswithcode.com/datasets> has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.

* For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

* If this information is not available online, the authors are encouraged to reach out to the asset's creators.

* New Assets

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

Justification: The paper does not release new assets.

* The answer NA means that the paper does not release new assets.

* Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.

* The paper should discuss whether and how consent was obtained from people whose asset is used.

* At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.

* Crowdsourcing and Research with Human Subjects

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

Justification: This research does not involve any human subjects.

* The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.

* Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.

* According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.

* Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

Justification: The research conducted does not involve any human subjects.

* The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.

* Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

* We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.

* For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.

§ PROOF OF THEOREM <REF>

The proof starts with the definition of the greedy-action selection at occupancy state $s_\tau$, and value function $\upsilon^{\pb}_{\tau+1}\colon s_{\tau+1}\mapsto \max_{V\in \mathbb{V}} \sum_{o^{\pw} \in O^{\pw}} s_{\tau+1}^{\mathtt{m},\circ}(o^{\pw}) \min_{\alpha\in V} \alpha(s_{\tau+1}^{\mathtt{c},o^{\pw}})$. Let $q^{\pb}_\tau \colon (s_\tau,a_\tau) \mapsto R(s_\tau,a_\tau) + \gamma\upsilon^{\pb}_{\tau+1}(T(s_\tau,a_\tau))$. Then,

$\mathbb{G}^{\pb}(s_\tau,\upsilon^{\pb}_{\tau+1}) =\textstyle \argmax_{a_\tau^{\pb}}\min_{a_\tau^{\pw}} ~ q^{\pb}_\tau(s_\tau,a_\tau)$.

Let $s_{\tau+1}^{\mathtt{m},\pw}(o_{\tau+1}^{\pw})$ and $s_{\tau+1}^{\mathtt{c}, o_{\tau+1}^{\pw}}$ be marginal probability and conditional occupancy state associated with $T(s_\tau,a_\tau)$.  The injection of  (<ref>) into $\upsilon^{\pb}_{\tau+1}(T(s_\tau,a_\tau))$ produces the following expression:

\begin{align*}
\upsilon^{\pb}_{\tau+1}(T(s_\tau,a_\tau))&=\max_{V\in \mathbb{V}} {\textstyle \sum_{o_{\tau+1}^{\pw} \in O_{\tau+1}^{\pw}}}s_{\tau+1}^{\mathtt{m},\pw}(o_{\tau+1}^{\pw}) \min_{\alpha\in V}\alpha(s_{\tau+1}^{\mathtt{c},o_{\tau+1}^{\pw}}).
\end{align*}

If we replace $\max_{V\in \mathbb{V}}$ by $\max_{\xi \in \triangle(\mathbb{V})}$  then there is no loss in optimality,

\begin{align*}
&=\max_{\xi \in \triangle(\mathbb{V})} {\textstyle \sum_{o_{\tau+1}^{\pw} \in O_{\tau+1}^{\pw}}  \sum_{V \in \mathbb{V}}}\min_{\alpha \in V}\xi(V) s_{\tau+1}^{\mathtt{m},\pw}(o_{\tau+1}^{\pw}) \alpha(s_{\tau+1}^{\mathtt{c},o_{\tau+1}^{\pw}}).
\end{align*}

Cunha et al., 2023 shows that these statistics $s_{\tau+1}^{\mathtt{m},\pw}(o_{\tau+1}^{\pw})$ and $s_{\tau+1}^{\mathtt{c}, o_{\tau+1}^{\pw}}$  depend on $T(s_\tau,a_\tau)$ only through marginal probability $s_\tau^{\mathtt{m},\pw}(o_\tau^{\pw})$, conditional occupancy state $s_\tau^{\mathtt{c},o_\tau^{\pw}}$ associated with $s_\tau$, action probability $a_\tau^{\pw}(u_\tau^{\pw}|o_\tau^{\pw})$, observation $z_{\tau+1}^{\pw}$, and decision rule $a_\tau^{\pb}$, for all $y\in X$ and $o_{\tau+1} = (o_\tau ,u ,z )\in O_{\tau+1}$

\begin{align*}
s_{\tau+1}^{\mathtt{m},\pw}(o_{\tau+1}^{\pw})\cdot s_{\tau+1}^{\mathtt{c}, o_{\tau+1}^{\pw}}(y,o_{\tau+1}^{\pb})  &=\textstyle  a_\tau^{\pw}(u^{\pw}|o_\tau^{\pw}) \cdot a_\tau^{\pb}(u^{\pb}|o_\tau^{\pb})\sum_{x \in X}s_\tau(x,o_\tau)\cdot p_{xy}^{uz}.
\end{align*}

Exploiting this insight along with the linearity of $\alpha$ yields:

\begin{align*}
\upsilon^{\pb}_{\tau+1}(T(s_\tau,a_\tau)) =\max_{\xi \in \triangle(\mathbb{V})}  \sum_{o_{\tau+1}^{\pw}} \sum_{V \in \mathbb{V}} \min_{\alpha\in V} a_\tau^{\pw}(u^{\pw}|o_\tau^{\pw}) \xi(V) \sum_{o_\tau^{\pb}, u^{\pb}} a_\tau^{\pb}(u^{\pb}|o_\tau^{\pb}) \sum_{x,y,z^{\pb}} \alpha(y,o_{\tau+1}) s_\tau(x,o_\tau) p_{xy}^{uz}.
\end{align*}

Define the following two intermediate functions $g_{V}^{\alpha}$ and $q_{V}^{\alpha}$ for all joint histories $ouz$,

\begin{align*}
&\textstyle g_{V}^{\alpha}\colon(ouz^{\pw})\mapsto   \sum_x  s_\tau(x,o) ( \frac{r_{xu}}{|Z^{\pw}|} + \gamma \sum_{y,z^{\pb}}\alpha(y,o^{\pb}u^{\pb}z^{\pb}) p_{xy}^{uz})\\
&\textstyle q_{V}^{\alpha}\colon(o^{\pw}u^{\pw}z^{\pw})\mapsto  \sum_{o^{\pb}}\sum_{u^{\pb}} a^{\pb}(u^{\pb}|o^{\pb}) \cdot g_{V}^{\alpha}(ouz^{\pw}).
\end{align*}

Consequently, the action value $q^{\pb}_\tau(s_\tau,a_\tau)$ can be rewritten as follows:

\begin{align*}
&\max_{\xi \in \triangle(\mathbb{V})} {\textstyle \sum_{o^{\pw}}\sum_{u^{\pw}} a^{\pw}(u^{\pw}|o^{\pw}) \sum_{V \in \mathbb{V}} \xi(V) \sum_{z^{\pw}}}\min_{\alpha\in V}   q_{V}^{\alpha}(o^{\pw}u^{\pw}z^{\pw}).
\end{align*}

Thus, the greedy decision rule of player ${\pb}$ is the solution of the following optimization problem:

\begin{align*}
\max_{a^{\pb}}\min_{a^{\pw}}\max_{\xi \in \triangle(\mathbb{V})}  \sum_{o^{\pw},u^{\pw}} a^{\pw}(u^{\pw}|o^{\pw}) \sum_{V \in \mathbb{V}} \xi(V) \sum_{z^{\pw}}\min_{\alpha\in V}   q_{V}^{\alpha}(o^{\pw}u^{\pw}z^{\pw}).
\end{align*}

Since the function

$ o^{\pw} \mapsto  \sum_{u^{\pw}} a^{\pw}(u^{\pw}|o^{\pw}) \sum_{V \in \mathbb{V}} \xi(V) \sum_{z^{\pw}}\min_{\alpha\in V}   q_{V}^{\alpha}(o^{\pw}u^{\pw}z^{\pw})$
is a bilinear function of $a^{\pw}$ and $\xi$ as the quantities $\sum_{z^{\pw}}\min_{\alpha\in V}   q_{V}^{\alpha}(o^{\pw}u^{\pw}z^{\pw})$ are constants any pair $(a^{\pw},\xi)$.

Using Von Neuman minimax theorem [Neumann, 1928], one can swap both operators $\min_{a^{\pw}}$ and $\max_{\xi}$  with no loss in optimality,

\begin{align*}
\max_{\xi,a^{\pb}}\min_{a^{\pw}}  \sum_{o^{\pw},u^{\pw}} a^{\pw}(u^{\pw}|o^{\pw}) \sum_{V \in \mathbb{V}} \xi(V) \sum_{z^{\pw}}\min_{\alpha\in V}   q_{V}^{\alpha}(o^{\pw}u^{\pw}z^{\pw}).
\end{align*}

Let us define the decision variable $\theta(V,u^{\pb}|o^{\pb})  = \xi(V) \cdot a^{\pb}(u^{\pb}|o^{\pb})$ and function $\beta_{V}^{\alpha}\colon (o^{\pw}u^{\pw}z^{\pw}) \mapsto  \xi(V) \cdot q_{V}^{\alpha} (o^{\pw}u^{\pw}z^{\pw}) = \sum_{o^{\pb}}\sum_{u^{\pb}} \theta(V,u^{\pb}|o^{\pb}) \cdot g_{V}^{\alpha}(ouz^{\pw})$, such that the greedy decision rule is the solution of the maximin optimization problem:

\begin{align*}
\max_{\theta}\min_{a^{\pw}} \textstyle \sum_{o^{\pw},u^{\pw}} a^{\pw}(u^{\pw}|o^{\pw}) \sum_{V \in \mathbb{V}}  \sum_{z^{\pw}}\min_{\alpha\in V}   \sum_{o^{\pb}}\sum_{u^{\pb}} \theta(V,u^{\pb}|o^{\pb}) \cdot g_{V}^{\alpha}(ouz^{\pw}).
\end{align*}

Using Wald's maximin model we can convert this maximin optimization problem into a maximization mathematical program,

\begin{equation*}
\begin{aligned}
\text{maximize}&\textstyle  \sum_{o^{\pw}} \alpha_\theta(o^{\pw}) \\
\text{subject to } &\left|
\begin{array}{l}
\alpha_\theta(o^{\pw}) \leq \sum_{V}\sum_{z^{\pw}}  \beta_{V}(o^{\pw}u^{\pw}z^{\pw}), ~\forall u^{\pw} \in U^\pw, o^{\pw} \in O^\pw \\
\beta_{V}(o^{\pw}u^{\pw}z^{\pw}) \leq \sum_{o^{\pb}}\sum_{u^{\pb}} \theta(V,u^{\pb}|o^{\pb}) \cdot g_{V}^{\alpha}(ouz^{\pw}),~\forall V \in \mathbb{V}, \alpha \in V, o^{\pw} \in O^\pw, u^{\pw} \in U^\pw, z^{\pw} \in Z^\pw \\
\sum_{V}\sum_{u^{\pb}}  \theta(V,u^{\pb}|o^{\pb}) = 1,~ \forall o^{\pb} \in O^\pb
\end{array}
\right.\\
\text{variables } &\left|
\begin{array}{l}
\theta(V,u^{\pb}|o^{\pb})\in [0,1],~ \forall V \in \mathbb{V}, o^{\pb} \in O^{\pb}, u^{\pb} \in U^\pb
\end{array}
\right.
\end{aligned}
\end{equation*}

Then, the solution of the linear program in Figure <ref> is the greedy decision rule of player ${\pb}$, which ends the proof.

§ PROOF OF THEOREM <REF>

The proof starts from a formal description of a sound point-based update operator. The updated value function $\mathbb{H}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau, \mathbb{G}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau))$, given by $\mathbb{V}_\tau = \mathbb{V}_\tau \cup \{V_{\mathbb{G}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau)}\}$, is sound if the following inequalities hold:

* $\mathbb{H}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau, \mathbb{G}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau))(s_\tau) \geq \upsilon^{\pb}_\tau(s_\tau) $,

* $\mathbb{H}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau, \mathbb{G}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau))(\bar{s}_\tau)\leq \mathbb{H}^{\pb} (\upsilon^{\pb}_{\tau+1}, \bar{s}_\tau, \mathbb{G}^{\pb} (\upsilon^{\pb}_{\tau+1}, \bar{s}_\tau))(\bar{s}_\tau)$, for $\bar{s}_\tau \neq s_\tau$.

The proof of inequality ($\pmb{A}_1$) follows that of Theorem <ref> since $\mathbb{G}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau)$ is the outcome of greedy action-selection operator at occupancy state $s_\tau$. It only remains to prove inequality ($\pmb{A}_2$). To do so, we need to prove the value generated at occupancy state $\bar{s}_\tau\in \bar{S}_\tau$ by the collection of linear functions across conditional occupancy states, $V_{\mathbb{G}^{\pb} (\upsilon^{\pb}_{\tau+1}, s_\tau)}$, constructed for $s_\tau$.

Figure <ref> constructs a linear function for each conditional occupancy state $\bar{s}^{\mathtt{c},o^{\pw}}$ from occupancy state $\bar{s}_\tau\in \bar{S}_\tau$ assuming a fixed policy of player $\pb$. The constructed linear function for conditional occupancy state $\bar{s}^{\mathtt{c},o^{\pw}}$ minimizes the value of player $\pw$ assuming a fixed policy of player $\pb$. Because the fixed policy of $\pb$ was not constructed to maximize value of player $\pb$ at occupancy state $\bar{s}_\tau$, the resulted linear function at $\bar{s}^{\mathtt{c},o^{\pw}}$ lower-bounds the one that would have been created if player $\pb$ maximized upon occupancy state $\bar{s}_\tau$. As a consequence, inequality ($\pmb{A}_2$) holds. Which ends the proof.

§ PROOF OF THEOREM <REF>

This proof builds upon Theorem <ref>. Let $s^*_\tau$ an occupancy state, never visited during the planning phase by the PBVI algorithm. There exists an occupancy state $s_\tau \in \bar{S}_\tau$ suth that $\|s^*_\tau - s_\tau \|_1 \leq \delta_{ \bar{S}_{0:}}$. Let $\alpha_\tau$ be a linear function, over occupancy states expressed as distributions over conditional occupancy states, computed during the planning phase by the PBVI algorithm at occupancy state $s_\tau$ after a backup. Let $\alpha^*_\tau$ be the optimal linear function at occupancy state $s^*_\tau$ that would have been computed during the planning phase by the PBVI algorithm at occupancy state $s^*_\tau$ after a backup.
Let $\epsilon_\tau = |\alpha^*_\tau(s^*_\tau) - \alpha_\tau(s_\tau)|$, then

\begin{align*}
\epsilon_\tau &= \alpha^*_\tau(s^*_\tau) - \alpha_\tau(s_\tau)\\
&= \alpha^*_\tau(s^*_\tau) - \alpha_\tau(s_\tau) + \textcolor{red}{\alpha^*_\tau(s_\tau)- \alpha^*_\tau(s_\tau)},\quad\text{(add zero)}\\
&\leq \alpha^*_\tau(s^*_\tau) - \alpha_\tau(s_\tau) + \textcolor{red}{\alpha^*_\tau(s_\tau)}- \alpha_\tau(s_\tau),\quad\text{(since $\alpha^*_\tau(s_\tau)\leq \alpha_\tau(s_\tau)$ )} \\
&= (\alpha^*_\tau-\alpha_\tau)\cdot(s^*_\tau-s_\tau),\quad\text{(re-arranging terms)}\\
&\leq \|\alpha^*_\tau-\alpha_\tau\|_\infty \|s^*_\tau-s_\tau\|_1,\quad\text{(by Holder's iniequality)}\\
&\textstyle \leq c \delta_{ \bar{S}_{0:}} \sum_{\tau=t}^{\ell-1} \gamma^{t-\tau},\quad\text{(since $\|s^*_\tau - s_\tau \|_1 \leq \delta_{ \bar{S}_{0:}}$ and $\|r(\cdot,\cdot)\|_\infty \leq c$)} \\
&=c \delta_{ \bar{S}_{0:}} \frac{1-\gamma^{\ell-\tau}}{1-\gamma}.
\end{align*}

Now, after $\ell$ backups, the error the PBVI algorithm makes is given by $\epsilon  = \sum_{\tau} \gamma^\tau \cdot (\alpha^*_\tau(s^*_\tau) - \alpha_\tau(s_\tau)) = \sum_{\tau} \gamma^\tau \cdot\epsilon_\tau = 2c \delta_{ \bar{S}_{0:}} \frac{1+\ell \gamma^{\ell+1}-(\ell+1)\gamma^\ell}{(1-\gamma)^2}$. Which ends the proof.

§ PRUNING METHODS

§.§ Exact Pruning Method

The mixed-integer linear program <ref> tests whether a collection $V_\tau$ is dominated by the collections in $\mathbb{V}_\tau$. This mixed-integer linear program finds the occupancy state $s_\tau$ in which the value function $\upsilon_\tau$ improved the most by added the collection $V_\tau$ to $\mathbb{V}_\tau$. If the value $\delta_{V_\tau}$ maximized by the mixed-integer linear program is non-positive, the collection $V_\tau$ is dominated. Otherwise, the collection $V_\tau$ is not dominated and $\delta_{V_\tau}$ is the amount by which it gives a better value for the occupancy state $s_\tau$ than any collection in $\mathbb{V}_\tau$. While the pruning technique we discussed so far applies over the entire occupancy space, one can drastically reduced time and space complexities by attention of value functions over sample subsets $\bar{S}_{0:} = (\bar{S}_0,\bar{S}_1,\ldots,\bar{S}_{\ell-1})$. A point-based pruning algorithm takes as input a family of collections $\mathbb{V}_\tau$ and returns a subset $\mathbb{V}'_\tau \subseteq \mathbb{V}_\tau$.

\begin{equation}
\begin{aligned}
\text{maximize}&\textstyle   \quad\delta_{V_\tau} \\
\text{subject to } &\left|
\begin{array}{l}
\delta_{V_\tau} \leq \sum_{o^{\pw}\in O^{\pw}} (w^{o^{\pw}}_{V_\tau} - w^{o^{\pw}}_{V^{(\kappa)}_\tau}),\quad \forall V^{(\kappa)}_\tau\in \mathbb{V}_\tau \\
w^{o^{\pw}}_{V_\tau} \leq s_\tau^{\mathtt{m},\pw}(o^{\pw}) \alpha_\tau(s_\tau^{\mathtt{c},o^{\pw}}),\quad \forall \alpha_\tau\in V_\tau  \\
w^{o^{\pw}}_{V^{(\kappa)}_\tau} \leq s_\tau^{\mathtt{m},\pw}(o^{\pw}) \alpha_\tau(s_\tau^{\mathtt{c},o^{\pw}}),\quad \forall V^{(\kappa)}_\tau\in \mathbb{V}_\tau, \forall\alpha_\tau\in V^{(\kappa)}_\tau  \\
w^{o^{\pw}}_{V^{(\kappa)}_\tau} \geq s_\tau^{\mathtt{m},\pw}(o^{\pw}) \alpha^{(\kappa)}_\tau(s_\tau^{\mathtt{c},o^{\pw}}) +  (1-c^{o^{\pw}}_{\alpha^{(\kappa)}_\tau})\pmb{\mathbb{M}},\quad \forall V^{(\kappa)}_\tau\in \mathbb{V}_\tau, \forall \alpha^{(\kappa)}_\tau \in V^{(\kappa)}_\tau  \\
\sum_{V^{(\kappa)}_\tau \in \mathbb{V}_\tau} \sum_{\alpha^{(\kappa)}_\tau \in V^{(\kappa)}_\tau} c^{o^{\pw}}_{\alpha^{(\kappa)}_\tau} = 1\\
\sum_{x\in X}\sum_{o\in O_\tau} s_\tau(x,o) = 1
\end{array}
\right.\\
\text{variables } &\left|
\begin{array}{l}
c^{o^{\pw}}_{\alpha^{(\kappa)}_\tau} \in \{0,1\}, \forall V^{(\kappa)}_\tau\in \mathbb{V}_\tau, \forall \alpha^{(\kappa)}_\tau \in V^{(\kappa)}_\tau \\
s_\tau(x,o) \in [0,1]\\
\delta_{V_\tau}\in \mathbb{R}.
\end{array}
\right.
\end{aligned}
\label{milp:dominance}
\end{equation}

§.§ Bounded Pruning Method

The bounded pruning, Algorithm <ref>, is a pruning algorithm that works under the assumption that the subsets $\bar{S}_{0:}$ of occupancy states are finite. The algorithm is bounded in the sense that the families $\mathbb{V}_{0:}$ of collections of linear functions are guaranteed to be no larger than $|\bar{S}_{0:}|$. It tests whether a collection $V_\tau$ is dominated by the collections in $\mathbb{V}_\tau$ if for any occupancy state $s_\tau\in \bar{S}_\tau$,

$$\max_{V'_\tau\in \mathbb{V}_\tau} \sum_{o^{\pw}\in O^{\pw}} s^{\mathtt{m},\pw}(o^{\pw}) \min_{\alpha\in V'_\tau} \alpha(s^{\mathtt{c},o^{\pw}}) -  \sum_{o^{\pw}\in O^{\pw}} s^{\mathtt{m},\pw}(o^{\pw}) \min_{\alpha\in V_\tau} \alpha(s^{\mathtt{c},o^{\pw}}) \geq 0.$$

Its result $\mathbb{V}'_\tau$ is typically smaller than the minimum-size subset that is sound with
respect to the whole occupancy simplex, resulting from the mixed-integer linear program <ref>.

With catching, the inner products, $\alpha_\tau(s_\tau^{\mathtt{c},o^{\pw}})$, need to be computed only once for each collection $V_\tau\in \mathbb{V}_\tau$, each vector $\alpha_\tau\in V_\tau$ and each conditional occupancy state $s_\tau^{\mathtt{c},o^{\pw}}$, which makes the running time of the bounded pruning method about $\pmb{O}(|\mathbb{V}_\tau||\bar{V}_\tau||\bar{S}_\tau||X||\bar{O}_\tau(s_\tau)|)$ where $\bar{O}_\tau(s_\tau) = \max_{s_\tau\in \bar{S}_\tau}\{o| o\in O_\tau, \Pr\{o|s_\tau\}>0  \}$.

Bounded pruning for $M'$.

${\mathtt{function}~ \mathtt{Bounded\text{-}Pruning}(\mathbb{V},\bar{S}, \delta)}$

$V\in \mathbb{V}$
$\mathtt{refCount}(V) \gets 0$.

$s\in \bar{S}$

$$V^* \gets \argmax_{V\in \mathbb{V}} \sum_{o^{\pw}\in O^{\pw}} s^{\mathtt{m},\pw}(o^{\pw}) \min_{\alpha\in V} \alpha(s^{\mathtt{c},o^{\pw}})$$

increment $\mathtt{refCount}(V^*)$
return $\{V\in \mathbb{V} \mid \mathtt{refCount}(V)>0\}$

IS/.style=sthlmRed, thick,
LM/.style=sthlmRed, thick,
axis/.style=very thick, ->, >=stealth', line join=miter,
important line/.style=thick, dashed line/.style=dashed, thin,
every node/.style=color=black,
dot/.style=circle,fill=red,minimum size=8pt,inner sep=0pt, outer sep=-1pt,

[axis, -, line width=.3em] (-6,2.75) – (-6,0) – (-2.25,0) – (-2.25,2.75);
at (-6.2,-0.3) A;
at (-0.2,-0.3) B;

[-, sthlmRed, line width=.1em] (-6,2) – (-5.07, 2.5) – (-3.5, 2.15) – (-2.25, 1.25);

[-, sthlmGreen, line width=.1em] (-6,1.65) – (-4.6, 2.75) – (-3.25, 2.35) – (-2.25,0);

[-, sthlmBlue, line width=.1em] (-6,0)– (-5.5,1.5) – (-4,2.65) – (-2.75,2.35) – (-2.25, .65);

[scale=1, sthlmYellow] at (-2.75,-0.3) $\pmb{s^{\mathtt{c},o^{\circ}}}$;

[scale=1, sthlmPurple] at (-5.07,-0.3) $\pmb{s^{\mathtt{c},o^{\circ}}}$;

[scale=1, sthlmOrange] at (-3.67,-0.3) $\pmb{s^{\mathtt{c},o^{\circ}}}$;

[-, dotted, sthlmYellow] (-2.75,2.75) – (-2.75,0);
[-, dotted, sthlmYellow] (-6.1,2.35) – (-2.25,2.35);
[rotate=90, scale=2, sthlmYellow] at (-2.75,2.35) $\bullet$;
[scale=.5, sthlmBlue] at (-6.5,2.35) $\omega(\textcolor{sthlmYellow}{\pmb{s^{\mathtt{c},o^{\circ}}}})$;
[scale=1, sthlmYellow] at (-2.75,0) $\bullet$;
[scale=1, sthlmYellow] at (-6,2.35) $\bullet$;

[-, dotted, sthlmOrange] (-3.67,2.75) – (-3.67,0);
[-, dotted, sthlmOrange] (-6.1,2.58) – (-2.25,2.58);
[rotate=90, scale=2, sthlmOrange] at (-3.67,2.58) $\bullet$;
[scale=.5, sthlmBlue] at (-6.5,2.58) $\omega(\textcolor{sthlmOrange}{\pmb{s^{\mathtt{c},o^{\circ}}}})$;
[scale=1, sthlmOrange] at (-3.67,0) $\bullet$;
[scale=1, sthlmOrange] at (-6,2.58) $\bullet$;

[-, dotted, sthlmPurple] (-5.07,2.75) – (-5.07,0);
[-, dotted, sthlmPurple] (-6.1,1.83) – (-2.25,1.83);
[rotate=90, scale=2, sthlmPurple] at (-5.07,1.83) $\bullet$;
[scale=.5, sthlmBlue] at (-6.5,1.83) $\omega(\textcolor{sthlmPurple}{\pmb{s^{\mathtt{c},o^{\circ}}}})$;
[scale=1, sthlmPurple] at (-5.07,0) $\bullet$;
[scale=1, sthlmPurple] at (-6,1.83) $\bullet$;

[axis, -, line width=.3em] (0,2.75) – (0,0) – (3.75,0) – (3.75,2.75);

[-, sthlmGreen, line width=.1em] (3.75,2) – (2.55,1.36015);
[-, sthlmGreen, line width=.1em, dashed] (2.55,1.36015) – (1.2,0.6406);
[-, sthlmGreen, line width=.1em, dashed] (1.2,0.6406) – (0,0);

[-, sthlmBlue, line width=.1em, dashed] (0,1.65)–(1.43, 1.51);
[-, sthlmBlue, line width=.1em] (1.43, 1.51)–(2.57,1.37);
[-, sthlmBlue, line width=.1em, dashed] (2.57,1.37) – (3.75,1.25);

[-, sthlmRed, line width=.1em] (0,2.25)–(0.9, 1.72);
[-, sthlmRed, line width=.1em, dashed] (0.9, 1.72)–(2.55,0.72);
[-, sthlmRed, line width=.1em, dashed] (2.55,0.72)–(3.75,0);

[-, sthlmPurple, line width=.1em, dashed] (0, 2.05)–(0.9, 1.72);
[-, sthlmPurple, line width=.1em] (0.9, 1.72)–(1.43, 1.53);
[-, sthlmPurple, line width=.1em, dashed] (1.43, 1.53)–(3.75, 0.68);

[-, dotted, sthlmBlue] (2.33,-0.1) – (2.33,2.75);
[-, dotted, sthlmBlue] (-.1,1.42) – (3.75,1.42);
[scale=1, sthlmBlue] at (2.33,-0.3) $\pmb{s}$;
[scale=.5, sthlmBlue] at (-.35,1.42) $\omega(\textcolor{sthlmBlue}{\pmb{s}})$;
[rotate=90, scale=2, sthlmBlue] at (2.33,1.42) $\bullet$;
[rotate=90, scale=1, sthlmBlue] at (2.33,0) $\bullet$;
[rotate=90, scale=1, sthlmBlue] at (0,1.42) $\bullet$;

[-, dotted, sthlmRed] (.33,-0.1) – (.33,2.75);
[-, dotted, sthlmRed] (-.1,2.05) – (3.75,2.05);
[scale=1, sthlmRed] at (.33,-0.3) $\pmb{s}$;
[scale=.5, sthlmRed] at (-.35,2.05) $\omega(\textcolor{sthlmRed}{\pmb{s}})$;
[rotate=90, scale=2, sthlmRed] at (.33,2.05) $\bullet$;
[rotate=90, scale=1, sthlmRed] at (.33,0) $\bullet$;
[rotate=90, scale=1, sthlmRed] at (0,2.05) $\bullet$;

[-, dotted, sthlmGreen] (3.33,-0.1) – (3.33,2.75);
[-, dotted, sthlmGreen] (-.1,1.79) – (3.75,1.79);
[scale=1, sthlmGreen] at (3.33,-0.3) $\pmb{s}$;
[scale=.5, sthlmGreen] at (-.35,1.79) $\omega(\textcolor{sthlmGreen}{\pmb{s}})$;
[rotate=90, scale=2, sthlmGreen] at (3.33,1.79) $\bullet$;
[rotate=90, scale=1, sthlmGreen] at (3.33,0) $\bullet$;
[rotate=90, scale=1, sthlmGreen] at (0,1.79) $\bullet$;

[-, dotted, sthlmPurple] (0.9, -0.1) – (0.9, 1.72);
[scale=1, sthlmPurple] at (0.9, -0.3) $\pmb{s}$;
[rotate=90, scale=2, sthlmPurple] at (0.9, 1.72) $\bullet$;
[rotate=90, scale=1, sthlmPurple] at (0.9, 0) $\bullet$;

Comparison between exact and bounded pruning methods.

Figure <ref> compares the results of the exact and bounded pruning approaches on an example family of collections of linear functions. (Right) The purple collection would be pruned under bounded pruning, the foundation point of the purple line being on the red line. However, it would not be pruned under exact pruning, because it is strictly optimal for occupancy points outside of its foundation point (purple point). Best viewed in color.

title=Adversarial Tiger,
ylabel style=yshift=-5mm,
xmin=0, xmax=2000,
xtick=0, 1000, 2000,
ymin=-3, ymax=1,
ytick=-3, -1, 1,
style=ultra thick,
legend pos=south east,
+[smooth,mark=none,sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/adversarialtiger.csv;
+[smooth,mark=none,sthlmBlue] table [col sep=comma, x=time, y=lb] ./paper/results/HSVI_Delage/H4/adversarialtiger.csv;
+[smooth,mark=none,sthlmGreen] table [col sep=comma, x=time, y=ub] ./paper/results/HSVI_Delage/H4/adversarialtiger.csv;
PBVI$_2$, HSVI$_\text{lower}$, HSVI$_\text{upper}$

title=Competitive Tiger,
xmin=0, xmax=2000,
xtick=0, 1000, 2000,
ymin=-2, ymax=2,
ytick=-2, 0, 2,
style=ultra thick,
+[smooth,mark=none,sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/competitivetiger.csv;
+[smooth,mark=none,sthlmBlue] table [col sep=comma, x=time, y=lb] ./paper/results/HSVI_Delage/H4/competitivetiger.csv;
+[smooth,mark=none,sthlmGreen] table [col sep=comma, x=time, y=ub] ./paper/results/HSVI_Delage/H4/competitivetiger.csv;

ylabel style=yshift=-5mm,
xmin=0, xmax=2000,
xtick=0, 1000, 2000,
ymin=-2, ymax=2,
ytick=-2, 0, 2,
style=ultra thick,
+[smooth,mark=none,sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/recycling.csv;
+[smooth,mark=none,sthlmBlue] table [col sep=comma, x=time, y=lb] ./paper/results/HSVI_Delage/H4/recycling.csv;
+[smooth,mark=none,sthlmGreen] table [col sep=comma, x=time, y=ub] ./paper/results/HSVI_Delage/H4/recycling.csv;

xlabel=Time (s),
ylabel style=yshift=-5mm,
xtick=0, 1000, 2000,
ytick=0., 0.25,
style=ultra thick
+[smooth, mark=none, sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/mabc.csv;
+[smooth, mark=none, sthlmBlue] table [col sep=comma, x=time, y=lb] ./paper/results/HSVI_Delage/H4/mabc.csv;
+[smooth, mark=none, sthlmGreen] table [col sep=comma, x=time, y=ub] ./paper/results/HSVI_Delage/H4/mabc.csv;

title=Matching Pennies,
xlabel=Time (s),
xmin=0, xmax=2000,
xtick=0, 1000, 2000,
ymin=-2, ymax=2,
ytick=-2, 0, 2,
style=ultra thick
+[smooth,mark=none,sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/matchingpennies.csv;

A visual representation of the performance of our best performing algorithm (PBVI$_2$) against the HSVI algorithm of Delage et al., 2023 for horizon $\ell = 4$ across five different games. Best viewed in color.

§ ADDITIONAL PLOTS

title=Adversarial Tiger,
ylabel style=yshift=-5mm,
xmin=0, xmax=2000,
xtick=0, 1000, 2000,
ymin=-3, ymax=1,
ytick=-3, -1, 1,
style=ultra thick,
legend pos=south east,
+[smooth,mark=none,sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/adversarialtiger.csv;
+[smooth,mark=none,sthlmBlue] table [col sep=comma, x=time, y=lb] ./paper/results/HSVI_Delage/H4/adversarialtiger.csv;
+[smooth,mark=none,sthlmGreen] table [col sep=comma, x=time, y=ub] ./paper/results/HSVI_Delage/H4/adversarialtiger.csv;
PBVI$_2$, HSVI$_\text{lower}$, HSVI$_\text{upper}$

title=Competitive Tiger,
xmin=0, xmax=2000,
xtick=0, 1000, 2000,
ymin=-2, ymax=2,
ytick=-2, 0, 2,
style=ultra thick,
+[smooth,mark=none,sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/competitivetiger.csv;
+[smooth,mark=none,sthlmBlue] table [col sep=comma, x=time, y=lb] ./paper/results/HSVI_Delage/H4/competitivetiger.csv;
+[smooth,mark=none,sthlmGreen] table [col sep=comma, x=time, y=ub] ./paper/results/HSVI_Delage/H4/competitivetiger.csv;

ylabel style=yshift=-5mm,
xmin=0, xmax=2000,
xtick=0, 1000, 2000,
ymin=-2, ymax=2,
ytick=-2, 0, 2,
style=ultra thick,
+[smooth,mark=none,sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/recycling.csv;
+[smooth,mark=none,sthlmBlue] table [col sep=comma, x=time, y=lb] ./paper/results/HSVI_Delage/H4/recycling.csv;
+[smooth,mark=none,sthlmGreen] table [col sep=comma, x=time, y=ub] ./paper/results/HSVI_Delage/H4/recycling.csv;

xlabel=Time (s),
ylabel style=yshift=-5mm,
xtick=0, 1000, 2000,
ytick=0., 0.25,
style=ultra thick
+[smooth, mark=none, sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/mabc.csv;
+[smooth, mark=none, sthlmBlue] table [col sep=comma, x=time, y=lb] ./paper/results/HSVI_Delage/H4/mabc.csv;
+[smooth, mark=none, sthlmGreen] table [col sep=comma, x=time, y=ub] ./paper/results/HSVI_Delage/H4/mabc.csv;

title=Matching Pennies,
xlabel=Time (s),
xmin=0, xmax=2000,
xtick=0, 1000, 2000,
ymin=-2, ymax=2,
ytick=-2, 0, 2,
style=ultra thick
+[smooth,mark=none,sthlmRed] table [col sep=comma, x=time, y=value] ./paper/results/PBVI_pruning_hyperplane/H4/matchingpennies.csv;

A visual representation of the performance of our best performing algorithm (PBVI$_2$) against the HSVI algorithm of Delage et al., 2023 for horizon $\ell = 4$ across five different games. Best viewed in color.

§ EXPERIMENTS ON LARGER BENCHMARKS

Preliminary experiments on larger benchmarks were already carried out to test the scalability of the method. Both chosen benchmarks exhibit a larger hidden state, action and observation space, yet PBVI$_3$ seems to show very promising results.

Snapshot of empirical results for larger benchmarks (Box pushing and Mars). For each game, we report time (in hours) and the best value for horizons $\ell$ computed with PBVI$_3$. oot means a time limit of 2 hours has been exceeded.

Problem     $\ell$     2cPBVI$_3$

1-2 3-4
pushing     2     0     4.1

3     2.36     4.92

4     OOT     123

5     OOT     216

7     OOT     400

10     OOT     723

1-2 3-4
2*Mars     2     0.08     -1.12

3     40     -4.0

§ EXPERIMENTS ON SUBCLASSES

Snapshot of empirical results. For each subclass of game (Markov Game and Public Observable Markov Game) and algorithms, we report time (in seconds) and the best value for the horizon $\ell$.

Problem     3c|MG     3cPOMG

[0.4pt](lr0.125em)1-4 [0.4pt](lr0.125em)5-7
$\ell$     Time     Value     $\ell$     Time     Value

Adversarial tiger
1     0     0.25     1     0     0.25

50     0     11.9     2     0     0

100     0     23.8     3     0     0.2

1000     2     238     4     2     0.2

Competitive tiger
1     0     0     1     0     0

50     0     0     2     0     0

100     0     0     3     2     0

1000     3     0     4     0     0

1     0     -0.4     1     0     -0.4

50     0     1.36     2     0     0.28

100     0     2.41     3     2     0.34

1000     4     21     4     26     0.38

1     0     0.05     1     0     0.05

50     0     0.52     2     0     0.88

100     0     0.98     3     0     0.99

1000     3     9.15     4     4     0.11

Matching pennies
1     0     0     1     0     0

50     0     -49     2     0     -1

100     0     -99     3     0     -2

1000     2     -999     4     0     -3

§ COMPUTATIONAL RESOURCES

The results presented in this paper were run on CPU. For CFR+, AMD Ryzen was used with 90G of available space. For HSVI/PBVI, a CPU was also used with 30-70G of available space for smaller horizons and 90-110G for higher horizons.


# Classical action for the height within the Kardar-Parisi-Zhang (KPZ)
equation for surface growth

Garry Goldstein1<EMAIL_ADDRESS>
###### Abstract

In this work we write down a classical (not quantum) action for the surface
height for the Kardar-Parisi-Zhang (KPZ) equation for surface growth. We do so
starting with the regular Martin-Siggia-Rose (MSR) action (which is quantum -
contains the constraint field) and integrate out the quantum constraint field
exactly. We analyze the classical action, we thereby obtain, within the
gaussian and one loop approximations and find various instabilities to rough
surfaces. The gaussian analysis predicts instabilities to rough surfaces below
two dimensions while one loop predicts stronger surface stability to roughness
and instabilities to roughness below one dimension rather then two dimensions.
The one loop analysis shows that the KPZ action is incomplete and that we
generate additional terms (not found in the initial action) in the action
perturbatively. In the supplement we also modify the KPZ equation for growing
surfaces to include the effect of surface tilt on the noise (that is have
multiplicatively coupled noise).

###  I  Introduction

An important example of a non-equilibrium statistical mechanics system is a
surface growing under the external deposition of molecules. A mathematical,
stochastic differential, equation that describes a very wide class of such
growing surfaces is known as the Kardar-Parisi-Zhang (KPZ) equation. It is
given by [2, 3, 1]:

$\displaystyle\frac{\partial h}{\partial t}$
$\displaystyle=\Gamma\left(\sqrt{1+\left(\nabla
h\right)^{2}}\right)-D\nabla^{2}h+\xi$
$\displaystyle\cong\Gamma\left(1+\frac{1}{2}\left(\nabla
h\right)^{2}\right)-D\nabla^{2}h+\xi.$ (1)

Here $h$ is the surface height, $D$ is the diffusion coefficient and $\Gamma$
is an overall rate of molecule deposition and we have performed a small
gradient expansion for simplicity. Furthermore $\xi\left(\mathbf{x},t\right)$
is a Gaussian noise function with action:

$\int\mathcal{D}\xi\exp\left(-\int d^{d}\mathbf{x}dt\xi^{2}/2\Delta\right)$
(2)

Also the second term on the RHS of Eq. (1) describes the diffusion of atoms on
the surface which tends to smooth it out. Furthermore for geometric reasons we
see that the growth rate is not constant $\Gamma$ but is given by
$\frac{\Gamma}{\cos\left(\theta\right)}$ where $\theta$ is the angle between
the normal to the surface ($\hat{n}$) and the direction the molecules are
deposited - say z-axis.We now compute the normal to a $2d$ surface in terms of
the gradient $\frac{\partial h}{\partial x}$ and $\frac{\partial h}{\partial
y}$ whereby we obtain:

$\hat{n}\sim\left(\begin{array}[]{ccc}\hat{x}&\hat{y}&\hat{z}\\\
1&0&\frac{\partial h}{\partial x}\\\ 0&1&\frac{\partial h}{\partial
y}\end{array}\right)=-\frac{\partial h}{\partial x}\hat{x}-\frac{\partial
h}{\partial y}\hat{y}+\hat{z}$ (3)

Whereby:

$\Rightarrow\cos\left(\hat{n}\cdot\hat{z}\right)=\frac{1}{\sqrt{1+\left(\frac{\partial
h}{\partial x}\right)^{2}+\left(\frac{\partial h}{\partial y}\right)^{2}}}$
(4)

As such we obtain Eq. (1). Originally the KPZ equation was proposed by Kardar,
Parisi and Zhang to study the growth of surfaces [2, 3] however it was later
realized that the same equations appear in a wide variety of contexts. For
example the KPZ equation arises in the weakly asymmetric simple exclusion
principle dynamics [4], in the partition functions of directed polymers [6,
5], Burgers’ hydrodynamics (which Navier-Stokes hydrodynamics without
vorticity and with noise) [3, 7, 5], polynuclear growth [8, 9, 10], rigid
solid on solid (RSOS) models [11, 12, 13, 14] and represents a whole
universality class of processes with both space and time dependence [15, 5].

The KPZ equation may be studied in a variety of field theoretical ways. It can
be studied using the quantum KPZ action (based on the Martin-Siggia-Rose (MSR)
formalism). The action for this approach is given by [3]:

$S\left(h,p\right)=-\int d^{d}\mathbf{x}dt\left[p\frac{\partial h}{\partial
t}-Dp\nabla^{2}h+\frac{1}{2}\Gamma p\left(\nabla h\right)^{2}-\Delta
p^{2}\right]$ (5)

Here $p$ is the quantum constraint field, or using a Cole-Hopf transformation
[5, 3], with the transformation being given by:

$\varphi=\exp\left(\frac{\Gamma}{2D}h-\frac{\Gamma^{2}\Delta}{4D^{2}}t\right)$
(6)

Whereby using the Martin-Siggia-Rose (MSR) procedure one obtains the action:

$S\left(\varphi,\pi\right)=-\int
d^{d}\mathbf{x}dt\left[\pi\left(\frac{\partial\varphi}{\partial
t}-D\nabla^{2}\varphi\right)+\frac{\Gamma^{2}\Delta}{4D^{2}}\pi^{2}\varphi^{2}\right]$
(7)

Here $\pi$ is the quantum constraint field. For both approaches one then
obtains that for all $d\leq 2$ (in two or less dimensions) the action flows to
a strong coupling fixed point (where $\frac{\Gamma^{2}\Delta}{4D^{2}}$ becomes
large and perturbation theory fails) often associated with rough surfaces.

In this work we study the KPZ equation using the MSR method, without the Cole-
Hopf transform, e.g. using the action in Eq. (5). We integrate out the quantum
constraining field exactly (which can be done at tree level as, after a co-
ordinate change, there is only one connected Feynman diagram relevant to the
constraining field) and transform the KPZ - MSR quantum - action into a
classical action just for the height field (see Eq. (12)). We analyze the
action in Eq. (12) for instabilities to rough surfaces using gaussian and one
loop like analysis. We find the upper critical dimension for rough surfaces is
$d=2$ for the gaussian analysis and $d=2$ is modified using the one loop
analysis with rough surfaces forming for $d<1$. We argue that the system is
partially amenable to Renormalization Group (RG) analysis and propose new self
energy terms and interaction terms that show up perturbatively in the RG
process (ones that do not show up in the original action [16, 17] but are more
relevant in the RG sense).

###  II  Main calculations

Consider the MSR action for the KPZ equation [3, 7] given in Eq. (5) (see also
the supplementary online information [18]). Now we write:

$-\Delta p^{2}+p\frac{\partial h}{\partial
t}-Dp\nabla^{2}h=-\Delta\left[p-\frac{1}{2\Delta}\left(\frac{\partial
h}{\partial
t}-D\nabla^{2}h\right)\right]^{2}+\frac{1}{4\Delta}\left(\frac{\partial
h}{\partial t}-D\nabla^{2}h\right)^{2}$ (8)

and

$\frac{1}{2}\Gamma p\left(\nabla
h\right)^{2}=\frac{1}{2}\Gamma\left[p-\frac{1}{2\Delta}\left(\frac{\partial
h}{\partial t}-D\nabla^{2}h\right)\right]\left(\nabla
h\right)^{2}+\frac{\Gamma}{4\Delta}\left(\frac{\partial h}{\partial
t}-D\nabla^{2}h\right)\left(\nabla h\right)^{2}$ (9)

As such we have rewritten the action in Eq. (5) in terms of two fields $h$ and
$P=p-\frac{1}{2\Delta}\left(\frac{\partial h}{\partial
t}-D\nabla^{2}h\right)$. Now we write:

$\displaystyle\mathcal{A}$
$\displaystyle=\int\mathcal{D}h\mathcal{D}p\exp\left(-\int
d^{d}\mathbf{x}dt\left[p\frac{\partial h}{\partial t}-Dp\nabla^{2}h-\Delta
p^{2}+\frac{1}{2}\Gamma p\left(\nabla h\right)^{2}\right]\right)$
$\displaystyle=\int\mathcal{D}h\mathcal{D}P\exp\left(-\int
d^{d}\mathbf{x}dt\left[-\Delta P^{2}-\frac{1}{4\Delta}\left(\frac{\partial
h}{\partial t}-D\nabla^{2}h\right)^{2}+\frac{1}{2}\Gamma P\left(\nabla
h\right)^{2}+\frac{\Gamma}{4\Delta}\left(\frac{\partial h}{\partial
t}-D\nabla^{2}h\right)\left(\nabla h\right)^{2}\right]\right)$
$\displaystyle=\int\mathcal{D}h\exp\left(-\int
d^{d}\mathbf{x}dt\left[\frac{1}{4\Delta}\left(\frac{\partial h}{\partial
t}-D\nabla^{2}h\right)^{2}+\frac{\Gamma^{2}}{4\Delta}\left(\nabla
h\right)^{4}+\frac{\Gamma}{4\Delta}\left(\frac{\partial h}{\partial
t}-D\nabla^{2}h\right)\left(\nabla h\right)^{2}\right]\right)$ (10)

where we have performed a change of variables
$\mathcal{D}h\mathcal{D}p\rightarrow\mathcal{D}h\mathcal{D}P$. We note that
the determinant of the Jacobian of the transformation is unity as the Jacobian
of the transformation is upper triangular. We have integrated out $P$ to tree
level (which is exact as there is only one connected Feynman diagram for $P$
and we use exponentiation of disconnected diagrams [19]) and we have
introduced the integral:

$\frac{\int\exp\left(\Delta P^{2}\right)P^{2}dP}{\int\exp\left(\Delta
P^{2}\right)dP}=\frac{-\int\exp\left(-\Delta
P^{2}\right)P^{2}d\left[iP\right]}{\int\exp\left(-\Delta
P^{2}\right)d\left[iP\right]}=-\frac{1}{\Delta}$ (11)

where the variable $P$ was Wick rotated as a regularization. As such we have
obtained a new classical KPZ action:

$S\left(h\right)=-\int
d^{d}\mathbf{x}dt\left[\frac{1}{4\Delta}\left(\frac{\partial h}{\partial
t}-D\nabla^{2}h\right)^{2}+\frac{\Gamma}{4\Delta}\left(\frac{\partial
h}{\partial t}-D\nabla^{2}h\right)\left(\nabla
h\right)^{2}+\frac{\Gamma^{2}}{4\Delta}\left(\nabla h\right)^{4}\right]$ (12)

This is the main result of this work as it integrates out the quantum action
for KPZ into a classical action just for the height field.

###  III Analysis of the action in Eq. (12)

We will study the properties of the action in Eq. (12). We will do gaussian
and one loop analysis of the action. We will not do Renormalization Group (RG)
analysis due to current questions about its accuracy [21] for obtaining fixed
point positions and coefficients and because preliminary one loop analysis
shows that RG will generate new RG relevant couplings not found in Eq. (12).

####  III.1 Gaussian Analysis

We now Fourier transform to obtain:

$h\left(\mathbf{x},t\right)=\frac{1}{\left(2\pi\right)^{d+1}}\int
d^{d}\mathbf{k}d\omega
h\left(\mathbf{k},\omega\right)\exp\left(i\left[\mathbf{k}\cdot\mathbf{x}-\omega
t\right]\right)$ (13)

Now lets first focus on the quadratic action from Eq. (12):

$S_{Quad}\left(h\right)=-\frac{1}{\left(2\pi\right)^{d+1}}\int
d^{d}\mathbf{k}d\omega\left|h\left(\mathbf{k}\right)\right|^{2}\frac{1}{2\Delta}\left[\omega^{2}+D^{2}\mathbf{k}^{4}\right]$
(14)

This means that [20]:

$\displaystyle\left\langle\left[h\left(\mathbf{x},t\right)-h\left(\mathbf{0},0\right)\right]^{2}\right\rangle$
$\displaystyle=\frac{2\Delta}{\left(2\pi\right)^{d+1}}\int
d^{d}\mathbf{k}d\omega\frac{\left[1-\exp\left(i\left[\mathbf{k}\cdot\mathbf{x}-\omega
t\right]\right)\right]}{\left(\omega^{2}+D^{2}\mathbf{k}^{4}\right)}$ (15)

We now do the $\omega$ integration first, close the contour in the lower half
plane and pick up the pole at $\omega=-iD\mathbf{k}^{2}$ to obtain:

$\displaystyle\frac{2\Delta}{\left(2\pi\right)^{d+1}}\int
d^{d}\mathbf{k}d\omega\frac{\left[1-\exp\left(i\left[\mathbf{k}\cdot\mathbf{x}-\omega
t\right]\right)\right]}{\left(\omega^{2}+D^{2}\mathbf{k}^{4}\right)}$
$\displaystyle\cong\frac{\Delta
V\left(S^{d-1}\right)}{\left(2-d\right)D\left(2\pi\right)^{d}}\left[a^{2-d}-\sqrt{Dt+\left|\mathbf{x}\right|^{2}}^{2-d}\right]$
(16)

Here $V\left(S^{d-1}\right)$ is the volume of a unit radius $d-1$ dimensional
sphere. Indeed we have that:

$\displaystyle\frac{1}{\left(2\pi\right)^{d+1}}\int
d^{d}\mathbf{k}d\omega\frac{\left[1-\exp\left(i\left[\mathbf{k}\cdot\mathbf{x}-\omega
t\right]\right)\right]}{\left(\omega^{2}+D^{2}\mathbf{k}^{4}\right)}$
$\displaystyle=\frac{1}{\left(2\pi\right)^{d}}\int
d^{d}\mathbf{k}\frac{1}{2D\mathbf{k}^{2}}\left[1-\exp\left(i\mathbf{k}\cdot\mathbf{x}-D\mathbf{k}^{2}t\right)\right]$
$\displaystyle\cong\frac{V\left(S^{d-1}\right)}{2D\left(2\pi\right)^{d}}\left[\frac{1}{2-d}\left[a^{2-d}-L^{2-d}\right]-\int_{1/L}^{1/\sqrt{Dt+\left|\mathbf{x}\right|^{2}}}k^{d-3}dk\right]$
$\displaystyle=\frac{V\left(S^{d-1}\right)}{\left(2-d\right)2D\left(2\pi\right)^{d}}\left[a^{2-d}-\sqrt{Dt+\left|\mathbf{x}\right|^{2}}^{2-d}\right]$
(17)

We did the $\omega$ integration first, closed the contour in the lower half
plane and picked up the pole at $\omega=-iD\mathbf{k}^{2}$. We now see that
for:

$\left\\{\begin{array}[]{cc}d>2&smooth\,surface\\\ d=2&marginal\,surface\\\
d<2&rough\,surface\end{array}\right.$ (18)

Indeed the term $a^{2-d}-\sqrt{Dt+\left|\mathbf{x}\right|^{2}}^{2-d}$ becomes
large for $d<2$ for large distances and times showing non-smooth surfaces.
Here $a$is the typical size of a molecule which serves as a cutoff and is
considered finite, that is it is not a divergent term in the calculations.

####  III.2  One loop analysis for self energy

We notice that there are only two one loop diagrams for self energy
$\Sigma\left(\mathbf{k},\omega\right)$. Let us only pick out terms which are
proportional to $\mathbf{k}^{2}$ and $\omega^{2}$ that modify the dispersion
(these are the most divergent term). We will see that the terms
$\sim\omega^{2}$ will be non-analytic but can be regularized to be analytic in
an RG way 17 [17]. At one loop there are two Feynman diagrams contributing
diagrams with their values given by:

$\Sigma\left(\mathbf{k},\omega\right)=\Sigma_{1}\left(\mathbf{k},\omega\right)+\Sigma_{2}\left(\mathbf{k},\omega\right)+\Sigma_{3}\left(\mathbf{k},\omega\right)+\Sigma_{4}\left(\mathbf{k},\omega\right)$
(19)

Where:

$\displaystyle\Sigma_{1}\left(\mathbf{k},\omega\right)$
$\displaystyle=2\Gamma^{2}\mathbf{k}^{2}\int\frac{d\Omega
d^{d}\mathbf{q}}{\left(2\pi\right)^{d+1}}\frac{\mathbf{q}^{2}}{\Omega^{2}+D^{2}\mathbf{q}^{4}}$
$\displaystyle=2\Gamma^{2}\mathbf{k}^{2}\int\frac{1}{\left(2\pi\right)^{d}}\frac{d^{d}\mathbf{q}}{2D\mathbf{q}^{2}}\mathbf{q^{2}}$
$\displaystyle=\frac{\Gamma^{2}\mathbf{k}^{2}V\left(S^{d-1}\right)}{\left(2\pi\right)^{d}D\cdot
d\cdot a^{d}}$ (20)

$\displaystyle\Sigma_{2}\left(\mathbf{k},\omega\right)$
$\displaystyle=\frac{2}{d}\Gamma^{2}\mathbf{k}^{2}\int\frac{d\Omega
d^{d}\mathbf{q}}{\left(2\pi\right)^{d+1}}\frac{\mathbf{q}^{2}}{\Omega^{2}+D^{2}\mathbf{q}^{4}}$
$\displaystyle=\frac{2}{d}\Gamma^{2}\mathbf{k}^{2}\int\frac{1}{\left(2\pi\right)^{d}}\frac{d^{d}\mathbf{q}}{2D\mathbf{q}^{2}}\mathbf{q^{2}}$
$\displaystyle=\frac{\Gamma^{2}\mathbf{k}^{2}V\left(S^{d-1}\right)}{\left(2\pi\right)^{d}D\cdot
d^{2}\cdot a^{d}}$ (21)

$\displaystyle\Sigma_{3}\left(\mathbf{k},\omega\right)$
$\displaystyle=-\frac{2}{d}\Gamma^{2}\mathbf{k}^{2}\int\frac{d\Omega
d^{d}\mathbf{q}}{\left(2\pi\right)^{d+1}}\frac{\mathbf{q}^{2}}{\Omega^{2}+D^{2}\mathbf{q}^{4}}$
$\displaystyle=-\frac{2}{d}\Gamma^{2}\mathbf{k}^{2}\int\frac{1}{\left(2\pi\right)^{d}}\frac{d^{d}\mathbf{q}}{2D\mathbf{q}^{2}}\mathbf{q^{2}}$
$\displaystyle=-\frac{\Gamma^{2}\mathbf{k}^{2}V\left(S^{d-1}\right)}{\left(2\pi\right)^{d}D\cdot
d^{2}\cdot a^{d}}$ (22)

And:

$\displaystyle\Sigma_{4}\left(\mathbf{k},\omega\right)$
$\displaystyle\cong-2\Gamma^{2}\omega^{2}\int\frac{d\Omega
d^{d}\mathbf{q}}{\left(2\pi\right)^{d+1}}\frac{\mathbf{q}^{4}}{\left[\Omega^{2}+D^{2}\mathbf{q}^{4}\right]^{2}}$
$\displaystyle=-2\Gamma^{2}\omega^{2}\int\frac{d\Omega
d^{d}\mathbf{q}}{\left(2\pi\right)^{d+1}}\frac{\mathbf{q}^{4}}{\left[\Omega+iD\mathbf{q}^{2}\right]^{2}\left[\Omega-
iD\mathbf{q}^{2}\right]^{2}}$
$\displaystyle=-2\Gamma^{2}\omega^{2}\int\frac{d^{d}\mathbf{q}d\Omega}{\left(2\pi\right)^{d+1}}\frac{\mathbf{q}^{4}}{\Omega^{2}\left[\Omega+i2D\mathbf{q}^{2}\right]^{2}}$
$\displaystyle=-2\Gamma^{2}\omega^{2}\int\frac{d\Omega
d^{d}\mathbf{q}}{\left(2\pi\right)^{d+1}}\frac{\mathbf{q}^{4}}{-4\Omega^{2}D\mathbf{q}^{4}}\left[1-\frac{\Omega}{iD\mathbf{q^{2}}}+...\right]$
$\displaystyle=-\frac{1}{2}\Gamma^{2}\omega^{2}\int\frac{d^{d}\mathbf{q}}{\left(2\pi\right)^{d}}\frac{1}{D^{2}\mathbf{q}^{2}}$
(23)

Now we regularize the action by inserting the incoming momenta

$\displaystyle\Rightarrow\Sigma_{4}\left(\mathbf{k},\omega\right)\cong$
$\displaystyle-\frac{1}{2}\Gamma^{2}\omega^{2}\int\frac{d^{d}\mathbf{q}}{\left(2\pi\right)^{d}}\frac{1}{D^{2}\left[\mathbf{q}^{2}+\left(\mathbf{k}^{2}+\omega^{2}\right)\right]}$
$\displaystyle=-\frac{1}{2}\Gamma^{2}\omega^{2}\frac{V\left(S^{d-1}\right)}{\left(2\pi\right)^{d}D^{2}\cdot\left(d-2\right)\cdot
a^{d-2}}$
$\displaystyle\;+\frac{1}{2}\Gamma^{2}\omega^{2}\frac{V\left(S^{d-1}\right)\left(\mathbf{k}^{2}+\omega^{2}\right)^{d-2}}{\left(2\pi\right)^{d}D^{2}\cdot\left(d-2\right)}$
(24)

We now do RG regularization of the non-analytical terms (see [17] section
3.3.2):

$\Rightarrow\Sigma_{4}\left(\mathbf{k},\omega\right)\cong-\frac{1}{2}\Gamma^{2}\omega^{2}\frac{V\left(S^{d-1}\right)}{\left(2\pi\right)^{d}D^{2}\cdot\left(d-2\right)\cdot
a^{d-2}}$ (25)

Indeed RG would in introduce momentum shell integrals whereby the lower cutoff
in Eq. (24) would no longer be introduced and we have dropped a constant of
order unity in the final answer (this constant cannot be reliably computed see
Ref. [21]). We see that $d=2$ is the upper critical dimension for the self
energy. As such we may write

$\displaystyle\left\langle\left[h\left(\mathbf{x},t\right)-h\left(\mathbf{0},0\right)\right]^{2}\right\rangle$
$\displaystyle=\frac{1}{\left(2\pi\right)^{d+1}}\int
d^{d}\mathbf{k}d\omega\frac{\left[1-\exp\left(i\left[\mathbf{k}\cdot\mathbf{x}-\omega
t\right]\right)\right]}{E\left(\mathbf{k},\omega\right)}$ (26)

With:

$\displaystyle E\left(\mathbf{k},\omega\right)$
$\displaystyle=\left[\frac{1}{2\Delta}-\frac{\Gamma^{2}V\left(S^{d-1}\right)}{2\left(2\pi\right)^{d}D^{2}\cdot\left(d-2\right)\cdot
a^{d-2}}\right]\omega^{2}$
$\displaystyle+\frac{\Gamma^{2}V\left(S^{d-1}\right)}{\left(2\pi\right)^{d}D\cdot
d\cdot a^{d}}\mathbf{k}^{2}$ (27)

We now see that for:

$\left\\{\begin{array}[]{cc}d>1&smooth\,surface\\\ d=1&marginal\,surface\\\
d<1&rough\,surface\end{array}\right.$ (28)

This is similar to Eq. (18). We note that without RG regularization we would
have obtained non-derivative couplings similar to Hertz-Millis theory [22, 23,
16]. Based on our experience with one loop diagrams we now propose an RG
action for the system of the form:

$S\left(h\right)=-\int d^{d}\mathbf{x}dt\left[A\left(\frac{\partial
h}{\partial t}\right)^{2}+B\left(\nabla h\right)^{2}+C\frac{\partial
h}{\partial t}\left(\nabla h\right)^{2}+D\left(\frac{\partial h}{\partial
t}\right)^{3}+E\left(\nabla h\right)^{4}+F\left(\nabla
h\right)^{2}\left(\frac{\partial h}{\partial
t}\right)^{2}+G\left(\frac{\partial h}{\partial t}\right)^{4}\right]$ (29)

Here $A,B,C,D,E,F,G$ are coupling constants. All these terms will be generated
under perturbative RG and are the most RG relevant ones. However in view of
Ref. [21] we now mention the limited reliability of obtaining specific values
of the constants $A,B,C,D,E,F,G$ (say at a fixed point) due to various forms
of the cutoff (which is so far unknown). As such, we do not do full RG
analysis of this action as we will not reliably obtain the values of the
coupling coefficients $A,B,C,D,E,F,G$.

###  IV Conclusion

In this work we started with the MSR based quantum action for the KPZ equation
and integrated out the Lagrange multiplier introduced in the MSR procedure
exactly to obtain a classical action e.g. an action purely for the height
field in Eq. (12) which is the main result of the work. We did gaussian and
one loop analysis on the action in Eq. (12). The gaussian action led us to
conclude that surfaces form smoothly for $d>2$. The one loop analysis also
predicts that $d>1$ is sufficient for smooth surface growth. We had used RG
regularization to get rid of non-derivative (non-analytic) interactions. This
is somewhat similar to Hertz-Millis theory [16, 22, 23] however can be
regularized. However there are also some other concerns with the RG approach
in this situation [21] so we did not pursue this further. We did propose a
general RG like action for KPZ (see Eq. (29) where additional relevant terms
will be generated perturbatively. In the future it would be of interest to
study the action in Eqs. (12) and (29) much more thoroughly in order to
understand surface smoothness and roughness [2, 3] as well as to study
possible applications to catalysis on surfaces [24].

Acknowledgements: We would like to thank Davide Venturelli for useful
discussions.

## Supplementary Online Information

### KPZ with multiplicative noise

Here we extend the KPZ equations by claiming that the noise $\xi$ should
couple to the gradient the same way as the main molecule deposition rate
$\Gamma$ does so we should consider a new KPZ (nKPZ) equation with
multiplicatively coupled noise:

$\displaystyle\frac{\partial h}{\partial t}$
$\displaystyle=\left(\Gamma+\xi\right)\left(\sqrt{1+\left(\nabla
h\right)^{2}}\right)-D\nabla^{2}h$
$\displaystyle\cong\left(\Gamma+\xi\right)\left(1+\frac{1}{2}\left(\nabla
h\right)^{2}\right)-D\nabla^{2}h$ (30)

From now on, in the supplement, we focus only on nKPZ. We perform a MSR
analysis [3, 7] on this stochastic differential equation and introduce
Faddeev-Popov ghosts [25, 19] because of the multiplicative noise in the
system. We note that this approximation means that most of the noise comes
because of the deposition term while the usual approximation means that most
of the noise comes because of the diffusion term. A more general approach
(that incorporates both limits) is:

$\frac{\partial h}{\partial t}\cong\Gamma\left(1+\frac{1}{2}\left(\nabla
h\right)^{2}\right)+\xi\left(1+\frac{\alpha}{2}\left(\nabla
h\right)^{2}\right)-D\nabla^{2}h$ (31)

####  .1  Action for KPZ equation with multiplicative noise

We now study the stochastic differential equation in Eq. (31). We now perform
MSR analysis [3, 7] on this stochastic differential equation in Eq. (30) and
introduce Faddeev-Popov ghosts [19, 25] for the functional determinant
$\det\left[1+\frac{1}{2}\left(\nabla h\right)^{2}\right]$ and change variables
$h\rightarrow h-\Gamma t$:

$\displaystyle\mathcal{Z}$
$\displaystyle=\int\mathcal{D}\xi\mathcal{D}h\exp\left(-\int
d^{d}\mathbf{x}dt\xi^{2}/2\Delta\right)\delta\left(\frac{\partial h}{\partial
t}-\Gamma\left(1+\frac{1}{2}\left(\nabla
h\right)^{2}\right)-\xi\left(1+\frac{\alpha}{2}\left(\nabla
h\right)^{2}\right)+D\nabla^{2}h\right)\det\left(1+\frac{1}{2}\left(\nabla
h\right)^{2}\right)$
$\displaystyle=\int\mathcal{D}\xi\mathcal{D}h\mathcal{D}p\exp\left(-\int
d^{d}\mathbf{x}dt\left[\xi^{2}/2\Delta+p\left(\frac{\partial h}{\partial
t}-\Gamma\left(1+\frac{1}{2}\left(\nabla
h\right)^{2}\right)-\xi\left(1+\frac{\alpha}{2}\left(\nabla
h\right)^{2}\right)+D\nabla^{2}h\right)+c^{\dagger}\left[1+\frac{1}{2}\left(\nabla
h\right)^{2}\right]c\right]\right)$
$\displaystyle=\int\mathcal{D}\xi\mathcal{D}h\mathcal{D}p\exp\left(-\int
d^{d}\mathbf{x}dt\left[\frac{1}{2\Delta}\left(\xi-\Delta
p\right)^{2}+\frac{\alpha}{2}\xi p\left(\nabla
h\right)^{2}+p\left(\frac{\partial h}{\partial
t}-\frac{1}{2}\Gamma\left(\nabla h\right)^{2}+D\nabla^{2}h-\Delta
p\right)\right.\right.$
$\displaystyle\qquad\qquad\qquad\left.\left.+c^{\dagger}\left[1+\frac{1}{2}\left(\nabla
h\right)^{2}\right]c\right]\right)$ (32)

Whereby:

$\displaystyle\mathcal{Z}$
$\displaystyle=\int\mathcal{D}\xi\mathcal{D}h\mathcal{D}p\exp\left(-\int
d^{d}\mathbf{x}dt\left[\frac{1}{2\Delta}\left(\xi-\Delta
p\right)^{2}+\frac{\alpha}{2}\left(\xi-\Delta p\right)p\left(\nabla
h\right)^{2}+\frac{\alpha}{2}\Delta p^{2}\left(\nabla
h\right)^{2}\right.\right.$
$\displaystyle\qquad\qquad\qquad\left.\left.+p\left(\frac{\partial h}{\partial
t}-\frac{1}{2}\Gamma\left(\nabla h\right)^{2}+D\nabla^{2}h-\Delta
p\right)+c^{\dagger}\left[1+\frac{1}{2}\left(\nabla
h\right)^{2}\right]c\right]\right)$
$\displaystyle=\int\mathcal{D}\Xi\mathcal{D}h\mathcal{D}p\exp\left(-\int
d^{d}\mathbf{x}dt\left[\frac{1}{2\Delta}\Xi^{2}+\frac{\alpha}{2}\Xi
p\left(\nabla h\right)^{2}+\frac{\alpha}{2}\Delta p^{2}\left(\nabla
h\right)^{2}+p\left(\frac{\partial h}{\partial
t}-\frac{1}{2}\Gamma\left(\nabla h\right)^{2}+D\nabla^{2}h-\Delta
p\right)\right.\right.$
$\displaystyle\qquad\qquad\qquad\left.\left.+c^{\dagger}\left[1+\frac{1}{2}\left(\nabla
h\right)^{2}\right]c\right]\right)$
$\displaystyle=\int\mathcal{D}h\mathcal{D}p\exp\left(-\int
d^{d}\mathbf{x}dt\left[\frac{\alpha^{2}}{4\Delta}p^{2}\left(\nabla
h\right)^{4}+\frac{\alpha}{2}\Delta p^{2}\left(\nabla
h\right)^{2}+p\left(\frac{\partial h}{\partial
t}-\frac{1}{2}\Gamma\left(\nabla h\right)^{2}+D\nabla^{2}h-\Delta
p\right)\right.\right.$
$\displaystyle\qquad\qquad\qquad\left.\left.+c^{\dagger}\left[1+\frac{1}{2}\left(\nabla
h\right)^{2}\right]c\right]\right)$ (33)

Where we have performed a change of variables
$\mathcal{D}\xi\mathcal{D}h\mathcal{D}p\rightarrow\mathcal{D}\Xi\mathcal{D}h\mathcal{D}p$
with $\Xi=\xi-\Delta p$. We note that the determinant of the Jacobian of the
transformation being one as the Jacobian is upper triangular and integrated
out $\Xi$ to tree level (which is exact as there is only one connected Feynman
diagram involved (then one can use exponentiation of disconnected diagrams))
to obtain the action:

$S\left(h,p,\left\\{c^{\dagger},c\right\\}\right)=-\int
d^{d}\mathbf{x}dt\left[p\frac{\partial h}{\partial
t}-Dp\nabla^{2}h+\frac{1}{2}\Gamma p\left(\nabla h\right)^{2}-\Delta
p^{2}+\frac{\alpha^{2}}{4\Delta}p^{2}\left(\nabla
h\right)^{4}+\frac{\alpha}{2}\Delta p^{2}\left(\nabla
h\right)^{2}+c^{\dagger}\left[1+\frac{1}{2}\left(\nabla
h\right)^{2}\right]c\right]$ (34)

Note that we did not use the same prescription as in Ref 3 [3] for
multiplicative noise for generality. We now integrate out the Faddeev-Poppov
ghost fermions to leading order loop level to obtain the effective action for
the ghosts:

$S_{G}=\int d^{d}\mathbf{x}dtd^{d}\mathbf{x}^{\prime}dt^{\prime}\left(\nabla
h\left(x,t\right)\right)^{2}\left(\nabla
h\left(x^{\prime},t^{\prime}\right)\right)^{2}G^{-1}\left(x-x^{\prime},t-t^{\prime}\right)^{2}$
(35)

Now we have that $G^{-1}\left(k,\omega\right)=1$ and
$G^{-1}\left(\mathbf{x},t\right)=\delta^{d}\left(\mathbf{x}\right)\delta\left(t\right)$
as such it is important to introduce some sort of regulator associated with
the time a deposed molecule attaches and its size ($T$ and $a$) and write:

$S\left(h,p\right)=-\int d^{d}\mathbf{x}dt\left[p\frac{\partial h}{\partial
t}-Dp\nabla^{2}h+\frac{1}{2}\Gamma p\left(\nabla h\right)^{2}-\Delta
p^{2}+p^{2}\left[\frac{\alpha^{2}}{4\Delta}\left(\nabla
h\right)^{4}+\frac{\alpha}{2}\Delta\left(\nabla
h\right)^{2}\right]-\mathcal{C}\left(\nabla h\right)^{4}\right]$ (36)

Where $\mathcal{C}=\frac{1}{T\cdot a}$.

### References

  * 1 [1977] D. Forster, D. R. Nelson, and M. J. Stephen, Phys. Rev. A 16, 732 (1977).
  * 2 [1986] M. Kardar, G. Parisi, Y.-C. Zhang, Phys. Rev. Lett. 56, 889 (1986).
  * 3 [2011] A. Kamenev, Field Theories of Non-Equilibrium Systems (Cambridge University Press, Cambridge, 2011).
  * 4 [1997] L. Beretini, and G. Giacomin, Comm. Math. Phys. 183, 571 (1997).
  * 5 [2022] K. J. Wiese, Rep. Prog. Phys. 85, 086502 (2022).
  * 6 [2000] E. Brunet, and B. Derrida, Phys. Rev. E 61, 6789 (2000).
  * 7 [1973] P. C. Martin, E. D. Siggia and H. A. Rose, Phys. Rev. A 8, 423 (1973).
  * 8 [2000] M. Prahofer, and H. Spohn, Physica A 279, 342 (2000).
  * 9 [2000] M. Prahofer and H. Sphon, Phys. Rev. Lett. 84, 4882 (2000).
  * 10 [2002] M. Prahofer and H. Sphon, J. Stat. Phys. 108, 1071 (2002).
  * 11 [2002] E. Martini, A. Pagnani, and G. Parisi, J. Phys. A 33, 8181 (2000).
  * 12 [2002] E. Martini, A. Pagnani, G. Parisi and R. Racz, Phys. Rev. E 65, 026136 (2002).
  * 13 [2014] S. G. Alves, T. J. Oliveira, and S. C. Ferriera, Phys. Rev. E 90, 020103 (2014).
  * 14 [2019] W. P. Gomes, A. L. A. Penna and F. A. Oliveira, Phys. Rev. E 100, 02101 (2019).
  * 15 [2012] I. Corwin, Random Matrices 1, 1130001 (2012).
  * 16 [2017] M. Continentino, Quantum Scaling in Many Body Systems: An Approach to Quantum Phase Transitions (Cambridge University Press, Cambridge, 2017).
  * 17 [2011] S. Sachdev, Quantum Phase Transitions (Cambridge University Press, Cambridge, 2011).
  * 18 [2024] See supplementary online information.
  * 19 [1995] M. E. Peskin and D. V. Schroeder, Introduction to Quantum Field Theory (Perseus Books, Reading, 1995).
  * 20 [1994] A. Auerbach, Interacting Electrons and Quantum Magnetism (Springer, New York, 1994).
  * 21 [2024] G. Goldstein arXiv 2403.12085.
  * 22 [1976] J. A. Hertz, Phys. Rev. B 14, 1165 (1976).
  * 23 [1993] A. J. Millis, Phys. Rev. B 48, 7183 (1993).
  * 24 [2003] L. Cherendoff and J. W. Niermantsverdiert, Concepts of Modern Catalysis and Kinetics (John Wiley & Sons, Toronto, 2003).
  * 25 [1967] L. D. Fadeev and V. N. Popov, Phys. Lett. B 25, 29 (1967).