Arrow Research search

Author name cluster

Hugo Gimbert

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

AAAI Conference 2025 Conference Paper

Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives

  • Marius Belly
  • Nathanaël Fijalkow
  • Hugo Gimbert
  • Florian Horn
  • Guillermo A. Pérez
  • Pierre Vandenhove

Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. We are interested in constructing algorithms with theoretical guarantees to determine whether the agent has a strategy ensuring a given specification with probability 1. This well-studied problem is known to be undecidable already for very simple omega-regular objectives, because of the difficulty of reasoning on uncertain events. We introduce a revelation mechanism which restricts information loss by requiring that almost surely the agent has eventually full information of the current state. Our main technical results are to construct exact algorithms for two classes of POMDPs called weakly and strongly revealing. Importantly, the decidable cases reduce to the analysis of a finite belief-support Markov decision process. This yields a conceptually simple and exact algorithm for a large class of POMDPs.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Simplifying Imperfect Recall Games

  • Hugo Gimbert
  • Soumyajit Paul
  • B. Srivathsan

In games with imperfect recall, players may forget the sequence of decisions they made in the past. When players also forget whether they have already encountered their current decision point, they are said to be absent-minded. Solving one-player imperfect recall games is known to be NP-hard, even when the players are not absent-minded. This motivates the search for polynomial-time solvable subclasses. A special type of imperfect recall, called A-loss recall, is amenable to efficient polynomial-time algorithms. In this work, we present novel techniques to simplify non-absent-minded imperfect recall games into equivalent A-loss recall games. The first idea involves shuffling the order of actions, and leads to a new polynomial-time solvable class of imperfect recall games that extends A-loss recall. The second idea generalises the first one, by constructing a new set of action sequences which can be “linearly combined” to give the original game. The equivalent game has a simplified information structure, but it could be exponentially bigger in size (in accordance with the NP-hardness). We present an algorithm to generate an equivalent A-loss recall game with the smallest size.

PDF

Highlights Conference 2024 Conference Abstract

Controlling a Random Population: complexity

  • Hugo Gimbert

The population control problem asks whether an arbitrarily large population of finite state machines can be successfully controlled using a discrete time control where at every step, the chosen action is uniformly applied to all machines. The goal of the controller is to eventually put all machines in a final state. This is typically what happens if you organize a conference and have to chose every day a unique program for the whole audience which is interesting enough so that all participants to attend all talks. The larger the audience, the harder it is. The case where the machines are non-deterministic is called the population control problem. It has been tackled by Bertrand et al. in https: //arxiv. org/abs/1807. 00893. The case where the machines are MDPs is called the random population control problem. It has been shown decidable by Colcombet et al. in https: //arxiv. org/abs/1911. 01195 using Dickson's Lemma, the min-cut max-flow duality and distance automata. The exact complexity is still opened. A lower bound is EXPTIME, as shown by Mascle at al. https: //arxiv. org/abs/1909. 06420. We show that Corto's conjecture about the random case: an arbitrarily large random population can be controlled using solely 0, 1, \omega's and small quadratic constants. This almost-surely closes the complexity gap.

Details

Highlights Conference 2016 Conference Abstract

A Class of Zielonka Automata with a Decidable Controller Synthesis Problem

  • Hugo Gimbert

The decidability of the distributed version of the Ramadge and Wonham control problem, where both the plant and the controllers are modelled as Zielonka automata is a challenging open problem. There exists three classes of plants for which the existence of a correct controller has been shown decidable in the distributed setting: when the dependency graph of actions is series-parallel, when the processes are connectedly communicating and when the dependency graph of processes is a tree. We generalize these three results by showing that a larger class of plants, called broadcast plants, has a decidable controller synthesis problem. We give new examples of plants for which controller synthesis is decidable.

Details

Highlights Conference 2016 Conference Abstract

Deciding Maxmin Reachability in Half-Blind Stochastic Games

  • Edon Kelmendi
  • Hugo Gimbert

Two-player, turn-based, stochastic games with reachability conditions are considered, where the maximizer has no information (he is blind) and is restricted to deterministic strategies whereas the minimizer is perfectly informed. We ask the question of whether the game has maxmin, in other words we ask whether for all 0" title="Rendered by QuickLaTeX. com" height="12" width="40" style="vertical-align: 0px" /> there exists a deterministic strategy for the (blind) maximizer such that against all the strategies of the minimizer, it is possible to reach the set of final states with probability larger than. This problem is undecidable in general, but we define a class of games, called leaktight half-blind games where the problem becomes decidable. We also show that mixed strategies in general are stronger for both players and that optimal strategies for the minimizer might require infinite-memory.

Details

I&C Journal 2015 Journal Article

Randomness for free

  • Krishnendu Chatterjee
  • Laurent Doyen
  • Hugo Gimbert
  • Thomas A. Henzinger

We consider two-player zero-sum games on finite-state graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (players interact simultaneously); and (b) turn-based (players interact in turn). The two sources of randomness in these games are randomness in the transition function and randomness in the strategies. In general, randomized strategies are more powerful than deterministic strategies, and probabilistic transitions give more general classes of games. We present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function (probabilistic transitions can be simulated by deterministic transitions); and (b) strategies (pure strategies are as powerful as randomized strategies). As a consequence of our characterization we obtain new undecidability results for these games.

Details DOI

GandALF Workshop 2010 Workshop Paper

Blackwell-Optimal Strategies in Priority Mean-Payoff Games

  • Hugo Gimbert
  • Wiesław Zielonka

We examine perfect information stochastic mean-payoff games - a class of games containing as special sub-classes the usual mean-payoff games and parity games. We show that deterministic memoryless strategies that are optimal for discounted games with state-dependent discount factors close to 1 are optimal for priority mean-payoff games establishing a strong link between these two classes.

PDF Details DOI

MFCS Conference 2010 Conference Paper

Randomness for Free

  • Krishnendu Chatterjee
  • Laurent Doyen 0001
  • Hugo Gimbert
  • Thomas A. Henzinger

Abstract We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (players interact simultaneously); and (b) turn-based (players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. We present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function (probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games.

Details

SODA Conference 2010 Conference Paper

Solving Simple Stochastic Tail Games

  • Hugo Gimbert
  • Florian Horn 0001

Infinite stochastic games are a natural model for open reactive processes: one player represents the controller and the other represents a hostile environment. The evolution of the system depends on the decisions of the players, supplemented by chance. There are two main algorithmic problems on such games: computing the values of the vertices (quantitative analysis) and deciding whether a player can win with probability one, or arbitrarily close to one (qualitative analysis). In this paper, we reduce the quantitative analysis of simple stochastic tail games (where both players have perfect information and the winner does not depend on finite prefixes) to the qualitative analysis: we provide an algorithm computing values which uses qualitative analysis sub-procedure. The correctness proof of this algorithm reveals several nice properties of perfect-information stochastic tail games, in particular the existence of optimal strategies. We apply these results to games whose winning conditions are boolean combinations of mean-payoff and Büchi conditions.

Details

CSL Conference 2004 Conference Paper

Parity and Exploration Games on Infinite Graphs

  • Hugo Gimbert

Abstract This paper examines two players’ turn-based perfect-information games played on infinite graphs. Our attention is focused on the classes of games where winning conditions are boolean combinations of the following two conditions: (1) the first one states that an infinite play is won by player 0 if during the play infinitely many different vertices were visited, (2) the second one is the well known parity condition generalized to a countable number of priorities. We show that, in most cases, both players have positional winning strategies and we characterize their respective winning sets. In the special case of pushdown graphs, we use these results to show that the sets of winning positions are regular and we show how to compute them as well as positional winning strategies in exponential time.

Details

MFCS Conference 2004 Conference Paper

When Can You Play Positionally?

  • Hugo Gimbert
  • Wieslaw Zielonka

Abstract We consider infinite antagonistic games over finite graphs. We present conditions that, whenever satisfied by the payoff mapping, assure for both players positional (memoryless) optimal strategies. To verify the robustness of our conditions we show that all popular payoff mappings, such as mean payoff, discounted, parity as well as several other payoffs satisfy them.

Details