Game-Theoretic Foundations for Undiscounted Bisimulation Metrics
Abstract
Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when γ=1. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally, we prove that these metrics bound total-reward and, when the optimal gain is state-independent, optimal relative value differences. We also provide error and suboptimality guarantees for aggregation-based planning in total- and average-reward settings.
Related
- A Deterministic Game-Theoretic Approach to Convexity-Preserving Property and Finite-Time Extinction of Level Sets for Geometric Equations
- A Cooperative Game-Theoretic Framework for Real-Time Deviation Settlement in Local Energy Communities
- The Normalized Maximum Likelihood for Regular Non-Smooth Models: Measure-Theoretic Foundations and Geometric Sampling
- Information Disclosure Strategies of Live-Streaming E-Commerce Supply Chains in the AI Era: A Game-Theoretic Analysis
- When Does Text Inform? Benchmarking Information-Theoretic Metrics for Multimodal Time-Series Forecasting
BibTeX
@misc{zurek2026gametheoretic,
title = {{Game-Theoretic Foundations for Undiscounted Bisimulation Metrics}},
author = {Matthew Zurek and Yudong Chen and Josiah P. Hanna},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38313},
eprint = {2610.38313},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38313},
}
RIS
TY - UNPB
TI - Game-Theoretic Foundations for Undiscounted Bisimulation Metrics
AU - Matthew Zurek
AU - Yudong Chen
AU - Josiah P. Hanna
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38313
UR - https://arxiv.org/abs/2610.38313
AB - Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when γ=1. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally, we prove that these metrics bound total-reward and, when the optimal gain is state-independent, optimal relative value differences. We also provide error and suboptimality guarantees for aggregation-based planning in total- and average-reward settings.
ER -