Modeling Uncertainty: Constraint-Based Belief States in Imperfect-Information Games

• URL: http://arxiv.org/abs/2507.19263v1
• Date: Fri, 25 Jul 2025 13:38:44 GMT
• Title: Modeling Uncertainty: Constraint-Based Belief States in Imperfect-Information Games
• Authors: Achille Morenville, Éric Piette,
• Abstract summary: In imperfect-information games, agents must make decisions based on partial knowledge of the game state.<n>The Belief Game model addresses this challenge by delegating state estimation to the game model itself.<n>This paper investigates two approaches to represent beliefs in games with hidden piece identities.
• Score: 0.5524804393257919
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In imperfect-information games, agents must make decisions based on partial knowledge of the game state. The Belief Stochastic Game model addresses this challenge by delegating state estimation to the game model itself. This allows agents to operate on externally provided belief states, thereby reducing the need for game-specific inference logic. This paper investigates two approaches to represent beliefs in games with hidden piece identities: a constraint-based model using Constraint Satisfaction Problems and a probabilistic extension using Belief Propagation to estimate marginal probabilities. We evaluated the impact of both representations using general-purpose agents across two different games. Our findings indicate that constraint-based beliefs yield results comparable to those of probabilistic inference, with minimal differences in agent performance. This suggests that constraint-based belief states alone may suffice for effective decision-making in many settings.

Related papers

• Who's Gaming the System? A Causally-Motivated Approach for Detecting Strategic Adaptation [12.528928000871405]
  We consider a multi-agent setting where the goal is to identify the "worst offenders:" agents that are gaming most aggressively.<n>We introduce a framework in which each agent's tendency to game is parameterized via a scalar.<n>By recasting the problem as a causal effect estimation problem where different agents represent different "treatments," we prove that a ranking of all agents by their gaming parameters is identifiable.
  arXiv  Detail & Related papers  (2024-12-02T22:07:48Z)
• State-Constrained Zero-Sum Differential Games with One-Sided Information [19.964883571758502]
  We study zero-sum differential games with state constraints and one-sided information. Our contribution is an extension to games with state constraints and the derivation of the primal and dual subdynamic principles necessary for computing behavioral strategies.
  arXiv  Detail & Related papers  (2024-03-05T07:51:38Z)
• Statistical Games [0.0]
  We show that Fisher and Bayesian games can be viewed as limiting cases of Statistical games. The main motivation for this work was to embed Bayesian statistics into a broader decision-making framework.
  arXiv  Detail & Related papers  (2024-02-24T19:59:15Z)
• Auto-Encoding Bayesian Inverse Games [36.06617326128679]
  We consider the inverse game problem, in which some properties of the game are unknown a priori. Existing maximum likelihood estimation approaches to solve inverse games provide only point estimates of unknown parameters. We take a Bayesian perspective and construct posterior distributions of game parameters. This structured VAE can be trained from an unlabeled dataset of observed interactions.
  arXiv  Detail & Related papers  (2024-02-14T02:17:37Z)
• On Imperfect Recall in Multi-Agent Influence Diagrams [57.21088266396761]
  Multi-agent influence diagrams (MAIDs) are a popular game-theoretic model based on Bayesian networks. We show how to solve MAIDs with forgetful and absent-minded agents using mixed policies and two types of correlated equilibrium. We also describe applications of MAIDs to Markov games and team situations, where imperfect recall is often unavoidable.
  arXiv  Detail & Related papers  (2023-07-11T07:08:34Z)
• Formalizing the Problem of Side Effect Regularization [81.97441214404247]
  We propose a formal criterion for side effect regularization via the assistance game framework. In these games, the agent solves a partially observable Markov decision process. We show that this POMDP is solved by trading off the proxy reward with the agent's ability to achieve a range of future tasks.
  arXiv  Detail & Related papers  (2022-06-23T16:36:13Z)
• Exploring the Trade-off between Plausibility, Change Intensity and Adversarial Power in Counterfactual Explanations using Multi-objective Optimization [73.89239820192894]
  We argue that automated counterfactual generation should regard several aspects of the produced adversarial instances. We present a novel framework for the generation of counterfactual examples.
  arXiv  Detail & Related papers  (2022-05-20T15:02:53Z)
• Rigidity for Monogamy-of-Entanglement Games [0.6091702876917281]
  We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. We also show rigidity for multiple copies of the game played in parallel.
  arXiv  Detail & Related papers  (2021-11-15T20:59:17Z)
• A Variational Inequality Approach to Bayesian Regression Games [90.79402153164587]
  We prove the existence of the uniqueness of a class of convex and generalize it to smooth cost functions. We provide two simple algorithms of solving them with necessarily strong convergence.
  arXiv  Detail & Related papers  (2021-03-24T22:33:11Z)
• End-to-End Learning and Intervention in Games [60.41921763076017]
  We provide a unified framework for learning and intervention in games. We propose two approaches, respectively based on explicit and implicit differentiation. The analytical results are validated using several real-world problems.
  arXiv  Detail & Related papers  (2020-10-26T18:39:32Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.