Bruno Ziliotto
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Bruno Ziliotto has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Raimundo Saona
Institute of Science and Technology Austria, 3400 Klosterneuburg, Austria
3 shared publications - José Correa
Department of Industrial Engineering, Universidad de Chile, Santiago, Chile
2 shared publications - Jérôme Renault
Toulouse School of Economics University of Toulouse Capitole Toulouse France
2 shared publications - Andrea Davini
Sapienza Università di Roma, Rome, Italy
1 shared publication - Andrés Cristi
EPFL, College of Management of Technology, Lausanne, Switzerland
1 shared publication - Camille Cornand
Univ Lyon, CNRS, GATE UMR 5824, F-69130 Ecully, France
1 shared publication
Latest Publications
- 10 November 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Uniform Value and Decidability in Ergodic Blind Stochastic Games
We study a class of two-player zero-sum stochastic games known as blind stochastic games, where players neither observe the state nor receive any information about it during the game. A central concept for analyzing long-duration stochastic games is the uniform value. A game has a uniform value v if for every [Formula: see text], Player 1 (resp., Player 2) has a strategy such that, for all sufficiently large n, his average payoff over n stages is at least [Formula: see text] (resp., at most [Formula: see text]). Prior work has shown that the uniform value may not exist in general blind stochastic games. To address this, we introduce a subclass called ergodic blind stochastic games, defined by imposing an ergodicity condition on the state transitions. For this subclass, we prove the existence of the uniform value and provide an algorithm to approximate it, establishing the decidability of the approximation problem. Notably, this decidability result is novel even in the single-player setting of Partially Observable Markov Decision Processes (POMDPs). Furthermore, we show that no algorithm can compute the uniform value exactly, emphasizing the tightness of our result. Finally, we establish that the uniform value is independent of the initial belief. Funding: This research was supported by the French Association Nationale de la Recherche et de la Technologie (ANRT) under the French CIFRE Ph.D. program [Grant CIFRE 2022/0513], through a collaboration between Paris-Dauphine University-PSL and NyxAir (France), by the French Agence Nationale de la Recherche (ANR) under [Grants ANR-21-CE40-0020 (CONVERGENCE project) and ANR-17-EURE-0010 (Investissements d’Avenir program)], by the European Research Council (ERC) under [Grant ERC CoG 863818 (ForM-SMArt)], and by the Austrian Science Fund (FWF) under [Grant 10.55776/COE12].
- 10 November 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Uniform Value and Decidability in Ergodic Blind Stochastic Games
We study a class of two-player zero-sum stochastic games known as blind stochastic games, where players neither observe the state nor receive any information about it during the game. A central concept for analyzing long-duration stochastic games is the uniform value. A game has a uniform value v if for every [Formula: see text], Player 1 (resp., Player 2) has a strategy such that, for all sufficiently large n, his average payoff over n stages is at least [Formula: see text] (resp., at most [Formula: see text]). Prior work has shown that the uniform value may not exist in general blind stochastic games. To address this, we introduce a subclass called ergodic blind stochastic games, defined by imposing an ergodicity condition on the state transitions. For this subclass, we prove the existence of the uniform value and provide an algorithm to approximate it, establishing the decidability of the approximation problem. Notably, this decidability result is novel even in the single-player setting of Partially Observable Markov Decision Processes (POMDPs). Furthermore, we show that no algorithm can compute the uniform value exactly, emphasizing the tightness of our result. Finally, we establish that the uniform value is independent of the initial belief. Funding: This research was supported by the French Association Nationale de la Recherche et de la Technologie (ANRT) under the French CIFRE Ph.D. program [Grant CIFRE 2022/0513], through a collaboration between Paris-Dauphine University-PSL and NyxAir (France), by the French Agence Nationale de la Recherche (ANR) under [Grants ANR-21-CE40-0020 (CONVERGENCE project) and ANR-17-EURE-0010 (Investissements d’Avenir program)], by the European Research Council (ERC) under [Grant ERC CoG 863818 (ForM-SMArt)], and by the Austrian Science Fund (FWF) under [Grant 10.55776/COE12].
- 26 February 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l'Institut Henri Poincaré C, Analyse non linéaire
- Vol. 43 (4) , 883-925
Stochastic homogenization of HJ equations: A differential game approach
We prove stochastic homogenization for a class of nonconvex and noncoercive first-order Hamilton–Jacobi equations in a finite-range dependence environment for Hamiltonians that can be expressed by a max-min formula. Exploiting the representation of solutions as value functions of differential games, we develop a game-theoretic approach to homogenization. We furthermore extend this result to a class of Lipschitz Hamiltonians that need not admit a global max-min representation. Our methods allow us to get a quantitative convergence rate for solutions with linear initial data toward the corresponding ones of the effective limit problem.
- 26 February 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l'Institut Henri Poincaré C, Analyse non linéaire
- Vol. 43 (4) , 883-925
Stochastic homogenization of HJ equations: A differential game approach
We prove stochastic homogenization for a class of nonconvex and noncoercive first-order Hamilton–Jacobi equations in a finite-range dependence environment for Hamiltonians that can be expressed by a max-min formula. Exploiting the representation of solutions as value functions of differential games, we develop a game-theoretic approach to homogenization. We furthermore extend this result to a class of Lipschitz Hamiltonians that need not admit a global max-min representation. Our methods allow us to get a quantitative convergence rate for solutions with linear initial data toward the corresponding ones of the effective limit problem.
- Open Access
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 96
Residual Prophet Inequalities
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 96
Open AccessResidual Prophet Inequalities
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 491-502
Prophet Inequalities Require Only a Constant Number of Samples
In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. In the classic setting, the order is fixed, and the optimal ratio is known to be 1/2. Three variants of this problem have been extensively studied: the prophet-secretary model, where variables arrive in uniformly random order; the free-order model, where the gambler chooses the arrival order; and the i.i.d. model, where the distributions are all the same, rendering the arrival order irrelevant. Most of the literature assumes that distributions are known to the gambler. Recent work has considered the question of what is achievable when the gambler has access only to a few samples per distribution. Surprisingly, in the fixed-order case, a single sample from each distribution is enough to approximate the optimal ratio, but this is not the case in any of the three variants. We provide a unified proof that for all three variants of the problem, a constant number of samples (independent of n) for each distribution is good enough to approximate the optimal ratios. Prior to our work, this was known to be the case only in the i.i.d. variant. Previous works relied on explicitly constructing sample-based algorithms that match the best possible ratio. Remarkably, the optimal ratios for the prophet-secretary and the free-order variants with full information are still unknown. Consequently, our result requires a significantly different approach than for the classic problem and the i.i.d. variant, where the optimal ratios and the algorithms that achieve them are known. We complement our result showing that our algorithms can be implemented in polynomial time. A key ingredient in our proof is an existential result based on a minimax argument, which states that there must exist an algorithm that attains the optimal ratio and does not rely on the knowledge of the upper tail of the distributions. A second key ingredient is a refined sample-based version of a decomposition of the instance into “small” and “large” variables, first introduced by Liu et al. [EC’21]. The universality of our approach opens avenues for generalization to other sample-based models. Furthermore, we uncover structural properties that might help pinpoint the optimal ratios in the full-information cases.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 491-502
Open AccessProphet Inequalities Require Only a Constant Number of Samples
In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. In the classic setting, the order is fixed, and the optimal ratio is known to be 1/2. Three variants of this problem have been extensively studied: the prophet-secretary model, where variables arrive in uniformly random order; the free-order model, where the gambler chooses the arrival order; and the i.i.d. model, where the distributions are all the same, rendering the arrival order irrelevant. Most of the literature assumes that distributions are known to the gambler. Recent work has considered the question of what is achievable when the gambler has access only to a few samples per distribution. Surprisingly, in the fixed-order case, a single sample from each distribution is enough to approximate the optimal ratio, but this is not the case in any of the three variants. We provide a unified proof that for all three variants of the problem, a constant number of samples (independent of n) for each distribution is good enough to approximate the optimal ratios. Prior to our work, this was known to be the case only in the i.i.d. variant. Previous works relied on explicitly constructing sample-based algorithms that match the best possible ratio. Remarkably, the optimal ratios for the prophet-secretary and the free-order variants with full information are still unknown. Consequently, our result requires a significantly different approach than for the classic problem and the i.i.d. variant, where the optimal ratios and the algorithms that achieve them are known. We complement our result showing that our algorithms can be implemented in polynomial time. A key ingredient in our proof is an existential result based on a minimax argument, which states that there must exist an algorithm that attains the optimal ratio and does not rely on the knowledge of the upper tail of the distributions. A second key ingredient is a refined sample-based version of a decomposition of the instance into “small” and “large” variables, first introduced by Liu et al. [EC’21]. The universality of our approach opens avenues for generalization to other sample-based models. Furthermore, we uncover structural properties that might help pinpoint the optimal ratios in the full-information cases.
- 16 December 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48 (4) , 2156-2166
Percolation Games
This paper introduces a discrete-time stochastic game class on [ ], which plays the role of a toy model for the well-known problem of stochastic homogenization of Hamilton–Jacobi equations. Conditions are provided under which the n-stage game value converges as n tends to infinity, and connections with homogenization theory are discussed. Funding: The second author acknowledges the support of the French Agence Nationale de la Recherche (ANR) [Grant ANR-21-CE40-0020] (CONVERGENCE project).
- 16 December 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48 (4) , 2156-2166
Percolation Games
This paper introduces a discrete-time stochastic game class on [ ], which plays the role of a toy model for the well-known problem of stochastic homogenization of Hamilton–Jacobi equations. Conditions are provided under which the n-stage game value converges as n tends to infinity, and connections with homogenization theory are discussed. Funding: The second author acknowledges the support of the French Agence Nationale de la Recherche (ANR) [Grant ANR-21-CE40-0020] (CONVERGENCE project).
- Open Access
Constant payoff in zero-sum stochastic games
In a zero-sum stochastic game, at each stage, two adversary players take decisions and receive a stage payoff determined by them and by a controlled random variable representing the state of nature. The total payoff is the normalized discounted sum of the stage payoffs. In this paper we solve the "constant payoff" conjecture formulated by Sorin, Vigeral and Venel (2010): if both players use optimal strategies, then for any alpha>0, the expected discounted payoff between stage 1 and stage alpha/lambda tends to the limit discounted value of the game, as the discount rate lambda goes to 0.
Open AccessConstant payoff in zero-sum stochastic games
In a zero-sum stochastic game, at each stage, two adversary players take decisions and receive a stage payoff determined by them and by a controlled random variable representing the state of nature. The total payoff is the normalized discounted sum of the stage payoffs. In this paper we solve the "constant payoff" conjecture formulated by Sorin, Vigeral and Venel (2010): if both players use optimal strategies, then for any alpha>0, the expected discounted payoff between stage 1 and stage alpha/lambda tends to the limit discounted value of the game, as the discount rate lambda goes to 0.
- 1 February 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 100-119
Finite-Memory Strategies in POMDPs with Long-Run Average Objectives
Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function.
- 1 February 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 100-119
Finite-Memory Strategies in POMDPs with Long-Run Average Objectives
Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function.
- 1 April 2021
- Published by Elsevier in Journal of Differential Equations
- Vol. 280, 464-476
An example of failure of stochastic homogenization for viscous Hamilton-Jacobi equations without convexity
- 1 April 2021
- Published by Elsevier in Journal of Differential Equations
- Vol. 280, 464-476
An example of failure of stochastic homogenization for viscous Hamilton-Jacobi equations without convexity
- Open Access
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility
A prophet inequality states, for some $\alpha\in[0,1]$, that the expected value achievable by a gambler who sequentially observes random variables $X_1,\dots,X_n$ and selects one of them is at least an $\alpha$ fraction of the maximum value in the sequence. We obtain three distinct improvements for a setting that was first studied by Correa et al. (EC, 2019) and is particularly relevant to modern applications in algorithmic pricing. In this setting, the random variables are i.i.d. from an unknown distribution and the gambler has access to an additional $\beta n$ samples for some $\beta\geq 0$. We first give improved lower bounds on $\alpha$ for a wide range of values of $\beta$; specifically, $\alpha\geq(1+\beta)/e$ when $\beta\leq 1/(e-1)$, which is tight, and $\alpha\geq 0.648$ when $\beta=1$, which improves on a bound of around $0.635$ due to Correa et al. (SODA, 2020). Adding to their practical appeal, specifically in the context of algorithmic pricing, we then show that the new bounds can be obtained even in a streaming model of computation and thus in situations where the use of relevant data is complicated by the sheer amount of data available. We finally establish that the upper bound of $1/e$ for the case without samples is robust to additional information about the distribution, and applies also to sequences of i.i.d. random variables whose distribution is itself drawn, according to a known distribution, from a finite set of known candidate distributions. This implies a tight prophet inequality for exchangeable sequences of random variables, answering a question of Hill and Kertz (Contemporary Mathematics, 1992), but leaves open the possibility of better guarantees when the number of candidate distributions is small, a setting we believe is of strong interest to applications.Open AccessUnknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility
A prophet inequality states, for some $\alpha\in[0,1]$, that the expected value achievable by a gambler who sequentially observes random variables $X_1,\dots,X_n$ and selects one of them is at least an $\alpha$ fraction of the maximum value in the sequence. We obtain three distinct improvements for a setting that was first studied by Correa et al. (EC, 2019) and is particularly relevant to modern applications in algorithmic pricing. In this setting, the random variables are i.i.d. from an unknown distribution and the gambler has access to an additional $\beta n$ samples for some $\beta\geq 0$. We first give improved lower bounds on $\alpha$ for a wide range of values of $\beta$; specifically, $\alpha\geq(1+\beta)/e$ when $\beta\leq 1/(e-1)$, which is tight, and $\alpha\geq 0.648$ when $\beta=1$, which improves on a bound of around $0.635$ due to Correa et al. (SODA, 2020). Adding to their practical appeal, specifically in the context of algorithmic pricing, we then show that the new bounds can be obtained even in a streaming model of computation and thus in situations where the use of relevant data is complicated by the sheer amount of data available. We finally establish that the upper bound of $1/e$ for the case without samples is robust to additional information about the distribution, and applies also to sequences of i.i.d. random variables whose distribution is itself drawn, according to a known distribution, from a finite set of known candidate distributions. This implies a tight prophet inequality for exchangeable sequences of random variables, answering a question of Hill and Kertz (Contemporary Mathematics, 1992), but leaves open the possibility of better guarantees when the number of candidate distributions is small, a setting we believe is of strong interest to applications. - 1 November 2020
- Published by Elsevier in Games and Economic Behavior
- Vol. 124, 122-139
Hidden stochastic games and limit equilibrium payoffs
- 1 November 2020
- Published by Elsevier in Games and Economic Behavior
- Vol. 124, 122-139
Hidden stochastic games and limit equilibrium payoffs