PaperlayerView exact revision on arXiv

Source-linked AI summary

Symmetric solution of the Bellman optimality equation for repeated harmony game

Hisato Komatsu

arXiv:2609.16289v1cs.GTcs.AIcs.LG

TL;DR

The paper asks how symmetric Bellman-optimal strategies behave in a repeated harmony game, an idealized setting for studying additional rewards. It derives the possible solutions and examines learned strategies with Q-learning. Three symmetric solutions are identified, and agents frequently learn WSLS or FH under specified initial conditions and sufficiently weak exploration noise.

  • Problem

    The paper examines an idealized case where additional payoffs transform a game into a harmony game, while nontrivial strategies may still arise in repeated play.

    Source: §1 · pp. 1–2

  • Method

    The study analyzes symmetric solutions of the repeated harmony game’s Bellman optimality equation and runs Q-learning experiments under several initial conditions.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Three symmetric solutions are identified—All-C, WSLS, and Frequent Handshake (FH)—and agents frequently learn WSLS or FH with sufficiently weak exploration noise and biased initial Q-functions.

    Source: §5 · p. 10

  • Takeaways & Limitations

    The existence of nontrivial strategies in the harmony game makes designing additional rewards complex; FH frequently chooses D and consequently receives less reward than All-C and WSLS.

    Source: §5 · p. 10

    The analysis focuses on memory-1 strategies and assumes symmetry between the agents’ Q-functions.

    Source: §2 · p. 2, §3 · p. 3

Abstract

from arXiv · show

In social dilemma games, additional rewards or punishments have been studied as means of promoting cooperation. Therefore, it is important to investigate the ideal situation, in which such an additional payoff would change the game. In this study, we investigated the symmetric solution of the Bellman optimality equation for a repeated harmony game. The calculations showed that three types of symmetric solutions exist. One of them corresponds to the trivial All-C strategy, and another to the Win-stay Lose-shift strategy of the prisoners dilemma game. The nontrivial behavior of the strategy corresponding to the last solution is also discussed in detail. In addition, we numerically investigated which strategy the agents actually learn by the reinforcement learning algorithm.

1. Introduction

The introduction situates Bellman-equation analysis and reinforcement learning among approaches to cooperation, then motivates studying the repeated harmony game as an idealized setting for additional rewards. The paper analyzes symmetric solutions and uses Q-learning experiments to examine which strategies agents learn.

1. Introduction

  • Prior work studied additional rewards or punishments, reinforcement learning in repeated games, and Bellman-equation solutions for the repeated prisoner’s dilemma and fixed-strategy opponents.Usui and Ueda found All-D creates an equilibrium regardless of conditions, while WSLS and Grim do so under specific conditions.Source: §1 · p. 1
  • The harmony game has cooperation as the dominant strategy in the one-shot game, yet prior studies report that cooperation can still collapse under some dynamics or spatial structures.The repeated-game folk theorem also permits a wide range of average payoffs, motivating analysis before adding further rewards.Source: §1 · p. 2
  • The study derives possible symmetric strategies for the repeated harmony game and uses Q-learning experiments to examine which strategies agents learn under several initial conditions.The paper considers this game an ideal case in which additional payoffs completely transform the game into a harmony game.Source: §1 · p. 2

2. Model

The model is a repeated two-agent harmony game with actions C and D, where rewards depend on the joint action. The analysis focuses on memory-1 strategies and uses the specified harmony-game reward ordering.

2. Model

  • At each time step, agents A and B choose C or D, and each agent’s reward depends on their joint action.The paper uses “reward” rather than “payoff” to match reinforcement-learning terminology.Source: §2 · p. 2
  • The model’s harmony-game rewards satisfy R > T > P and R > S > P, making C dominant for both agents in the one-shot game.The one-shot Nash equilibrium is (C, C), unlike the prisoner’s dilemma, the one-shot game lacks a social dilemma.Source: §2 · p. 2
  • The analysis restricts attention to memory-1 strategies, with the previous joint action as the agents’ observation.Agents forget actions from two or more steps earlier.Source: §2 · pp. 2–3

3. Bellman optimality equation and its symmetric solution

The paper studies symmetric Bellman-optimal solutions under greedy action selection and derives constraints on possible Q-function orderings. Its lemmas limit the allowed ordering patterns, including by ruling out an ordering through an inequality involving S and P.

3. Bellman optimality equation and its symmetric solution

  • The Bellman optimality equation is analyzed with exploration noise ignored and agents assumed to choose greedily.Under the assumed symmetry between agents’ Q-functions, the equation is reduced to the form considered in the analysis.Source: §3 · p. 3

3.1. Limitation on the symmetric solution

  • The proof uses the minimum per-step reward P to derive a lower bound when constraining the Q-function ordering.The resulting inequality compares the value of choosing D after (D,D) with the alternative ordering assumption.Source: §3.1 · p. 4
  • The proposed ordering Q*A((D,D),C) < Q*A((D,D),D) is ruled out because the resulting inequality implies S − P > 0.This contradicts the assumed ordering, so Q*A((D,D),C) > Q*A((D,D),D).Source: §3.1 · p. 4, A ((D, D) , D). Thus, Q∗ · p. 4
  • Only two pairwise ordering patterns for the Q-function are permitted under the symmetric-solution analysis.The proof assumes symmetry between agents’ Q-functions and excludes cases where the two action values coincide.Source: §3 · p. 3, A ((D, D) , D). Thus, Q∗ · p. 4

A ((D, C) , D) and Q∗

The derivation establishes that only the stated order-relation patterns are permitted, then obtains explicit solutions for the cases allowed by the lemmas. The explicit solutions share the form in Ref. because the Bellman-equation structure depends on Q-function ordering rather than the reward ordering.

A ((D, C) , D) and Q∗

  • The derivation concludes that Eqs. (14) and (15) are the only permitted order-relation patterns.The proof rejects assumed orderings for the Q-functions associated with (D,C) and (C,D).Source: A ((D, C) , D) and Q∗ · p. 4

3.2. Explicit solutions

  • Explicit solutions are derived for four cases allowed by the lemmas, and have the same form as in Ref..The Bellman-equation structure depends on the assumed pairwise Q-function ordering, not directly on the relationship among R, T, S, and P.Source: §3.2 · p. 5

A ((D, C) , D), and Q∗

The symmetric solutions include All-C and WSLS, plus a third strategy called Frequent Handshake (FH), which cooperates only after both agents defected in the previous step. The section also compares the strategies’ consistency conditions and describes their repeated-game behavior.

A ((D, C) , D), and Q∗

  • The All-C solution has Q∗A((D,D),D) = T + γR/(1−γ) and is always consistent with the harmony-game condition.The passage identifies this solution with All-C.Source: A ((D, C) , D), and Q∗ · p. 5
  • The WSLS solution has Q∗A((D,C),D) = P + γR/(1−γ) and is consistent with the game condition when γ > (S−P)/(R−S).The authors use “WSLS” for convenience, while noting that “win” and “lose” differ from their prisoner’s-dilemma meanings in this game.Source: A ((D, C) , D), and Q∗ · p. 5
  • One candidate solution is rejected because it contradicts the harmony-game condition S > P.This candidate assigns values involving R and P to states with payoffs T and S.Source: A ((D, C) , D), and Q∗ · p. 6
  • FH cooperates if and only if both agents chose D in the previous step; the authors name it Frequent Handshake because cooperation requires appropriately timed D handshakes.The strategy is also called “anti-Grim trigger” in some studies, but the authors avoid that term because its definition varies across the literature.Source: A ((D, C) , D), and Q∗ · p. 6
  • When both agents use FH, their sequence converges to a limit cycle and agent A’s long-term average reward is R+P.The passage also states that FH has the highest long-term average among the three strategies under a specified condition.Source: A ((D, C) , D), and Q∗ · pp. 6–7
  • With agent A using WSLS, the sequence converges to a limit cycle and its long-term average reward is R+S+P; with All-C, it converges to a fixed point with reward S.Source: A ((D, C) , D), and Q∗ · p. 7

4. Numerical experiments

The numerical experiments use independent Q-learning agents to test how exploration and initial Q-functions shape learned strategies, then compare Q-function trajectories with theoretical symmetric solutions.

4. Numerical experiments

  • Agents independently updated their Q-functions after each reward using Q-learning, with ϵ-greedy action selection and three initial Q-functions.The experiments compared ϵinit=1 and ϵinit=0.02, with Qinit set to Qzero, QWSLS, or QFH.Source: §4 · pp. 7–8
  • With ϵinit=1, agents almost always learned All-C; at ϵinit=0.02, learned strategies depended on Qinit, with WSLS and FH most often learned from matching initializations.Results summarize trials in which both agents learned the same strategy.Source: §4 · p. 8, Table 1 · p. 10
  • For Qinit=Qzero, All-C was learned more often with ϵinit=1 than with ϵinit=0.02; the authors suggest random opponents make choosing C appropriate, as in the one-shot game.Source: §4 · p. 9
  • Q-function medians converged to the symmetric solution for the most frequently learned strategy, while low-frequency strategies acted as outliers that shifted trial averages.Figure 1 compares median trajectories and interquartile intervals with theoretical solutions for All-C, WSLS, and FH.Source: §4 · p. 9, Figure 1 · p. 9

5. Summary

The paper identifies three symmetric solutions for the repeated harmony game and reports that Q-learning can also learn nontrivial strategies under particular conditions.

5. Summary

  • The Bellman optimality equation for the repeated harmony game has three symmetric solutions: All-C, WSLS, and Frequent Handshake (FH).Source: §5 · p. 10
  • When both agents use FH, they alternate (C, C) and (D, D), choosing D to punish deviations from that pattern.The authors note that FH frequently chooses D and consequently receives less reward than All-C and WSLS.Source: §5 · p. 10
  • Q-learning frequently produced WSLS or FH when exploration noise was sufficiently weak and initial Q-values favored those strategies.Source: §5 · p. 10
  • The source code for the work is uploaded to GitHub.The paper provides the repository address: https://github.com/Hisato-Komatsu/Repeated_Harmony.Source: §5 · p. 10

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

The author reports using generative AI tools for several manuscript-preparation tasks, then reviewing and editing the content and taking responsibility for it.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

Appendix A. Details of the numerical experiment

Against fixed strategies, the optimal response can depend on the discount factor, yielding WSLS, FH, All-C, or other memory-1 strategies. The appendix also specifies the Q-learning simulation procedure used for reproducibility.

Appendix A. Details of the numerical experiment

  • The simulation initializes Q-functions and observations, selects actions by ε-greedy exploration, updates Q-values, decays exploration, and periodically resets the episode.Algorithm 1 and Table A.2 provide pseudocode and hyperparameters for reproducibility.Source: Appendix A · p. 11

Appendix B.1. Optimal strategy against the WSLS strategy (The case (C, D, D, C))

  • Against WSLS, the optimal response is WSLS when γ > S−P; when γ < (S−P)/(R−P), it is All-C.The passage reports the corresponding Q-function orderings for these cases.Source: Appendix B.1 · p. 12

Appendix B.2. Optimal strategy against the FH strategy (The case (D, D, D, C))

  • Against FH, the optimal response is FH when γ > S−P; when γ < (S−P)/(R−P), it is All-C.The reported Q-function orderings distinguish these two solutions.Source: Appendix B.2 · p. 13

Appendix B.3. Optimal strategy against the All-C strategy (The case (C, C, C, C))

  • Against All-C, All-C is also optimal, and the matching symmetric solutions are Nash equilibria when strategies are restricted to memory-1.Neither agent can unilaterally increase cumulative reward under that restriction.Source: Appendix B.3 · p. 13

Appendix B.4. Optimal strategies against other fixed strategies

Appendix B.4.4. The case (D, C, C, C)

  • Against (D,C,C,C), the optimal response is All-C below the stated γ threshold and Grim above it; here Grim means choosing C only after (C,C).The threshold separates the Q-function orderings reported for the two responses.Source: Appendix B.4.4 · p. 15

Appendix B.4.5. The case (C, C, D, D)

Appendix B.4.7. The case (D, C, C, D)

Appendix B.4.9. The case (D, D, C, C)

For the fixed strategy (D,D,C,C), the optimal response varies across stated parameter conditions and includes All-C, alternating strategies, and All-D. The other two cases in this section yield All-C responses.

Appendix B.4.9. The case (D, D, C, C)

  • Against (D,D,C,C), the solutions across the stated conditions correspond to All-C, (D,C,D,C), (C,D,C,D), and All-D.The passage gives distinct inequalities for the reported Q-function orderings; it does not map each listed strategy to an individual inequality in the supplied text.Source: Appendix B.4.9 · p. 18

Appendix B.4.10. The case (C, D, D, D)

Appendix B.4.11. The case (D, C, D, D)

Appendix B.4.12. The case (D, D, C, D)

The fixed-strategy cases yield All-C or another conditional response, while the best-response network has three absorbing states and a cycle among them.

Appendix B.4.12. The case (D, D, C, D)

  • Against (D,D,C,D), the optimal response is All-C or (C,D,C,C), depending on γ.The supplied condition identifies the non-All-C solution when γ > (R−T)/(R−S).Source: Appendix B.4.12 · p. 20

Appendix B.4.13. The case (D, D, D, D) (the All-D strategy)

  • Against All-D, the optimal response is All-C; the network has absorbing states for All-C, WSLS, and FH, with convergence also possible to a cycle among them.In the network, edges connect each strategy to its optimal response.Source: Appendix B.4.13 · p. 20, Figure B.2 · p. 20
Loading 2609.16289v1…