BZBruno Ziliotto

Bruno Ziliotto

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Uniform Value and Decidability in Ergodic Blind Stochastic Games

    by Krishnendu Chatterjee, David Lurie, Raimundo Saona, Bruno Ziliotto

    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].

  • Stochastic homogenization of HJ equations: A differential game approach

    by Andrea Davini, Raimundo Saona, Bruno Ziliotto

    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

    Residual Prophet Inequalities

    by Dana Pizarro, Jose Correa, Sebastian Perez-Salazar, Bruno Ziliotto

  • Open Access

    Prophet Inequalities Require Only a Constant Number of Samples

    by Andrés Cristi, Bruno Ziliotto

    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.


  • Percolation Games

    by Guillaume Garnier, Bruno Ziliotto

    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

    by Olivier Catoni, Miquel Oliu-Barton, Bruno Ziliotto

    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.

  • Finite-Memory Strategies in POMDPs with Long-Run Average Objectives

    by Krishnendu Chatterjee, Raimundo Saona, Bruno Ziliotto

    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.


  • Open Access

    Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility

    by José Correa, Paul Dütting, Felix Fischer, Kevin Schewior, Bruno Ziliotto

    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.