On Satisficing in Quantitative Games

2021-01-06 · Suguman Bansal, Krishnendu Chatterjee, Moshe Y. Vardi

Several problems in planning and reactive synthesis can be reduced to the analysis of two-player quantitative graph games. {\em Optimization} is one form of analysis. We argue that in many cases it may be better to replace the optimization problem with the {\em satisficing problem}, where instead of searching for optimal solutions, the goal is to search for solutions that adhere to a given threshold bound. This work defines and investigates the satisficing problem on a two-player graph game with the discounted-sum cost model. We show that while the satisficing problem can be solved using numerical methods just like the optimization problem, this approach does not render compelling benefits over optimization. When the discount factor is, however, an integer, we present another approach to satisficing, which is purely based on automata methods. We show that this approach is algorithmically more performant -- both theoretically and empirically -- and demonstrates the broader applicability of satisficing overoptimization.

📄 PDF Abstract BibTeX arXiv:2101.02594

Code (1)

suguman/DSGame 공식 구현

Satisficing Equilibrium

2024-09-01 · Bary S. R. Pradelski, Bassel Tarbush

We propose a solution concept in which each agent $i$ does not necessarily optimize but selects one of their top $k_i$ actions. Our concept accounts for heterogeneous agents' bounded rationality. We show that there exist…

All

Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Games

2021-10-09 · Bora Yongacoglu, Gürdal Arslan, Serdar Yüksel

In multi-agent reinforcement learning (MARL), independent learners are those that do not observe the actions of other agents in the system. Due to the decentralization of information, it is challenging to design independ…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective

2025-09-27 · Yanqing Fu, Chao Huang, Chenrun Wang, Zhuping Wang arxiv

In game theory and multi-agent reinforcement learning (MARL), each agent selects a strategy, interacts with the environment and other agents, and subsequently updates its strategy based on the received payoff. This proce…

Multi-agent Reinforcement Learning

Paths to Equilibrium in Games

2024-03-26 · Bora Yongacoglu, Gürdal Arslan, Lacra Pavel, Serdar Yüksel

In multi-agent reinforcement learning (MARL) and game theory, agents repeatedly interact and revise their strategies as new data arrives, producing a sequence of strategy profiles. This paper studies sequences of strateg…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

Contextual Exploration Using a Linear Approximation Method Based on Satisficing

2021-12-13 · Akane Minami, Yu Kono, Tatsuji Takahashi

Deep reinforcement learning has enabled human-level or even super-human performance in various types of games. However, the amount of exploration required for learning is often quite large. Deep reinforcement learning al…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)