Bisimulation metrics give a principled notion of task‑relevant state similarity in reinforcement learning, yet existing constructions are largely confined to discounted MDPs, where contraction arguments guarantee well‑defined fixed points and downstream performance bounds. This work shifts the perspective from operators to games: prior metric operators are interpreted as Bellman‑Shapley operators of zero‑sum turn‑based games, and the metrics are defined as the corresponding game value functions, yielding unique definitions even when $\gamma=1$.
With this game‑theoretic foundation, dynamic‑programming convergence results, policy iteration, and related algorithms transfer directly to total‑reward and average‑reward settings. The authors also analyze how metric finiteness depends on structural properties of the underlying MDP, proposing directed metrics that remain bounded in weakly communicating MDPs.
An abstract framework for modifying the games' action spaces is introduced, allowing general transition coupling sets. This framework recovers many existing bisimulation metrics and guides the design of new ones.
Theoretically, the metrics are shown to bound total‑reward errors and, when the optimal gain is state‑independent, to bound optimal relative value differences. Finally, error and suboptimality guarantees for aggregation‑based planning are provided for both total‑reward and average‑reward problems.
Review: By embedding bisimulation metrics into zero‑sum games, the paper removes the discount‑factor restriction and offers a unified, actionable metric framework for undiscounted reinforcement learning, with solid theoretical guarantees and algorithmic implications.