Yahtzee: Reinforcement Learning Techniques for Stochastic Combinatorial Games

• URL: http://arxiv.org/abs/2601.00007v1
• Date: Thu, 18 Dec 2025 20:03:32 GMT
• Title: Yahtzee: Reinforcement Learning Techniques for Stochastic Combinatorial Games
• Abstract summary: We formulate an optimal policy for solitaire Yahtzee using Markov Decision Process (MDP) methods.<n>We train self-play agents using various policy gradient methods.<n>All models struggle to learn the upper bonus strategy, overindexing on four-of-a-kind's.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Yahtzee is a classic dice game with a stochastic, combinatorial structure and delayed rewards, making it an interesting mid-scale RL benchmark. While an optimal policy for solitaire Yahtzee can be computed using dynamic programming methods, multiplayer is intractable, motivating approximation methods. We formulate Yahtzee as a Markov Decision Process (MDP), and train self-play agents using various policy gradient methods: REINFORCE, Advantage Actor-Critic (A2C), and Proximal Policy Optimization (PPO), all using a multi-headed network with a shared trunk. We ablate feature and action encodings, architecture, return estimators, and entropy regularization to understand their impact on learning. Under a fixed training budget, REINFORCE and PPO prove sensitive to hyperparameters and fail to reach near-optimal performance, whereas A2C trains robustly across a range of settings. Our agent attains a median score of 241.78 points over 100,000 evaluation games, within 5.0\% of the optimal DP score of 254.59, achieving the upper section bonus and Yahtzee at rates of 24.9\% and 34.1\%, respectively. All models struggle to learn the upper bonus strategy, overindexing on four-of-a-kind's, highlighting persistent long-horizon credit-assignment and exploration challenges.

Related papers

• Reproducing AlphaZero on Tablut: Self-Play RL for an Asymmetric Board Game [0.6574517227976925]
  This work investigates the adaptation of the AlphaZero reinforcement learning algorithm to Tablut, an asymmetric historical board game.<n>Over 100 self-play iterations, the modified model demonstrated steady improvement, achieving a BayesElo rating of 1235.<n>Ultimately, the experiments confirm that AlphaZero's self-play framework can transfer to highly asymmetric games.
  arXiv  Detail & Related papers  (2026-04-07T06:16:19Z)
• Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback [0.0]
  This work investigates two-player zero-sum matrix games with an unknown payoff matrix and bandit feedback.<n>We propose Competitive Co-evolutionary Bandit Learning (coebl), a novel algorithm that integrates evolutionary algorithms into the bandit framework.<n>We prove that coebl achieves sublinear regret, matching the performance of deterministic optimism-based methods.
  arXiv  Detail & Related papers  (2025-05-19T10:05:55Z)
• Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guarantees [91.88803125231189]
  Reinforcement Learning from Human Feedback (RLHF) has been highly successful in aligning large language models with human preferences.<n>While prevalent methods like DPO have demonstrated strong performance, they frame interactions with the language model as a bandit problem.<n>In this paper, we address these challenges by modeling the alignment problem as a two-player constant-sum Markov game.
  arXiv  Detail & Related papers  (2025-02-18T09:33:48Z)
• Scalable Reinforcement Post-Training Beyond Static Human Prompts: Evolving Alignment via Asymmetric Self-Play [52.3079697845254]
  eva is the first method that allows language models to adaptively create training prompts in both offline and online RL post-training.<n>We show eva can create effective RL curricula and is robust across ablations.
  arXiv  Detail & Related papers  (2024-10-31T08:15:32Z)
• Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning [55.65738319966385]
  We propose a novel online algorithm, iterative Nash policy optimization (INPO)<n>Unlike previous methods, INPO bypasses the need for estimating the expected win rate for individual responses.<n>With an LLaMA-3-8B-based SFT model, INPO achieves a 42.6% length-controlled win rate on AlpacaEval 2.0 and a 37.8% win rate on Arena-Hard.
  arXiv  Detail & Related papers  (2024-06-30T08:00:34Z)
• Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge [5.071342645033634]
  We extend the Descent framework, which enables learning and planning in the context of two-player games with perfect information. We evaluate them on the game Ein wurfelt! against state-of-the-art algorithms. It is our generalization of Descent which obtains the best results.
  arXiv  Detail & Related papers  (2023-02-08T20:27:45Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  We study the problem of finding an approximate Nash equilibrium of games with continuous action sets. We propose two new methods that minimize an approximation of exploitability with respect to the strategy profile.
  arXiv  Detail & Related papers  (2023-01-20T23:55:30Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• Temporal Induced Self-Play for Stochastic Bayesian Games [32.88124137877018]
  We propose Temporal-Induced Self-Play (TISP) to find strategies with decent performances from any decision point onward. TISP uses belief-space representation, backward induction, policy learning, and non-parametric approximation. We prove that TISP-based algorithms can find approximate Perfect Bayesian Equilibrium in zero-sum one-sided games with finite horizon.
  arXiv  Detail & Related papers  (2021-08-21T05:36:42Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization [42.33734089361143]
  We propose a technique for discovering diverse strategic policies in complex multi-agent games. We derive a new algorithm, Reward-Randomized Policy Gradient (RPG) RPG is able to discover multiple distinctive human-interpretable strategies in challenging temporal trust dilemmas.
  arXiv  Detail & Related papers  (2021-03-08T06:26:55Z)
• Provably Efficient Algorithms for Multi-Objective Competitive RL [54.22598924633369]
  We study multi-objective reinforcement learning (RL) where an agent's reward is represented as a vector. In settings where an agent competes against opponents, its performance is measured by the distance of its average return vector to a target set. We develop statistically and computationally efficient algorithms to approach the associated target set.
  arXiv  Detail & Related papers  (2021-02-05T14:26:00Z)
• Agent57: Outperforming the Atari Human Benchmark [15.75730239983062]
  Atari games have been a long-standing benchmark in reinforcement learning. We propose Agent57, the first deep RL agent that outperforms the standard human benchmark on all 57 Atari games.
  arXiv  Detail & Related papers  (2020-03-30T11:33:16Z)

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.