The Impatient May Use Limited Optimism to Minimize Regret

Michaël Cadilhac, Guillermo A. Pérez, Marie van den Bogaard

Abstract

Discounted-sum games provide a formal model for the study of reinforcement learning, where the agent is enticed to get rewards early since later rewards are discounted. When the agent interacts with the environment, she may regret her actions, realizing that a previous choice was suboptimal given the behavior of the environment. The main contribution of this paper is a PSPACE algorithm for computing the minimum possible regret of a given game. To this end, several results of independent interest are shown. (1) We identify a class of regret-minimizing and admissible strategies that first assume that the environment is collaborating, then assume it is adversarial—the precise timing of the switch is key here. (2) Disregarding the computational cost of numerical analysis, we provide an NP algorithm that checks that the regret entailed by a given time-switching strategy exceeds a given value. (3) We show that determining whether a strategy minimizes regret is decidable in PSPACE.

Introduction: Regret in Discounted-Sum Games

In reinforcement learning, an agent interacts with an unknown environment. Standard game theory often assumes the environment is either perfectly collaborative (best-case) or perfectly adversarial (worst-case). However, real-world environments are rarely so binary. Regret minimization offers a more robust middle ground: the agent seeks to minimize the difference between the reward they actually received and the reward they could have received if they had known the environment's behavior in advance (hindsight).

Figure 1: A discounted-sum game graph where circles represent the agent (Eve) and squares represent the environment (Adam).

While regret has been studied in other contexts, applying it to discounted-sum games—where future rewards are worth less than immediate ones—is difficult. The infinite horizon and the numerical nature of the rewards make it computationally challenging to determine which strategy is truly "best" and how hard it is to find it.

The "Optipess" Strategy: Balancing Optimism and Pessimism

The authors introduce a novel class of "bipositional" strategies called optipess (optimistic-then-pessimistic). These strategies follow a best-case optimal path for a specific number of steps before switching to a worst-case optimal path. The core insight is that an agent does not need to be optimistic forever; there is a precise "time-switching" threshold after which an agent should stop hoping for collaboration and start protecting against the worst case to minimize regret.

Figure 2: A more complex game graph illustrating the intricate interactions between agent choices and environmental responses that necessitate time-switching strategies.

Furthermore, the authors prove that optipess strategies are admissible. In game theory, an admissible strategy is one that isn't "dominated" by another—meaning there's no other strategy that performs at least as well in all environments and strictly better in at least one. This bridges the gap between minimizing regret (a hindsight measure) and making a rational choice a priori.

Technical Hurdles and Succinctness

A major technical hurdle in these games is that "witnesses" (histories that prove a certain regret value) can be exponentially long. The authors overcome this using a Cycle Decomposition Lemma, showing that any long history can be represented succinctly as a simple path followed by an iterated simple cycle ($\alpha \cdot \beta^k \cdot \gamma$).

To handle the precision issues of comparing discounted sums, which involve high-degree polynomials, the authors link the problem to PosSLP (Positive Straight-Line Program). This is a known problem in computational complexity used to determine if an arithmetic circuit evaluates to a positive value.

Key Results and Complexity Bounds

The paper establishes several significant complexity results:

  • Decidability: Determining whether a strategy minimizes regret is decidable in PSPACE, a significant improvement over previous implicit algorithms.
  • Complexity Bounds: Determining if the agent's regret is bounded by a value $x$ is decidable in NP^PosSLP, which is contained within PSPACE.
  • Existence: The authors confirm that positional "Strongly Best-Worst-Case Optimal" (SBWO) strategies always exist in every discounted-sum game.

Limitations and Future Work

The reliance on the PosSLP oracle highlights a major bottleneck: the computational cost of comparing sums of the form $\sum a_i \cdot \lambda^{b_i}$. The authors note that the exact complexity of this specific numerical problem remains open. Additionally, while they provide a PSPACE upper bound, the only known lower bound is that the problem is at least as hard as solving parity games. Finally, translating these theoretical PSPACE algorithms into practical reinforcement learning heuristics remains a task for future engineering research.

Summary updated

Abstract

Discounted-sum games provide a formal model for the study of reinforcement learning, where the agent is enticed to get rewards early since later rewards are discounted. When the agent interacts with the environment, she may regret her actions, realizing that a previous choice was suboptimal given the behavior of the environment. The main contribution of this paper is a PSPACE algorithm for computing the minimum possible regret of a given game. To this end, several results of independent interest are shown. (1) We identify a class of regret-minimizing and admissible strategies that first assume that the environment is collaborating, then assume it is adversarial---the precise timing of the switch is key here. (2) Disregarding the computational cost of numerical analysis, we provide an NP algorithm that checks that the regret entailed by a given time-switching strategy exceeds a given value. (3) We show that determining whether a strategy minimizes regret is decidable in PSPACE.
BibTeX
@inproceedings{cadilhac2019impatient,
  author = {Michaël Cadilhac and Guillermo A. Pérez and Marie van den Bogaard},
  title = {{The Impatient May Use Limited Optimism to Minimize Regret}},
  booktitle = {FoSSaCS},
  year = {2019},
  doi = {10.1007/978-3-030-17127-8\_8},
}
Figure