Efficient Computation of Blackwell Optimal Policies using Rational Functions
Markov Decision Problems (MDPs) provide a foundational framework for modelling sequential decision-making across diverse domains, guided by optimality criteria such as discounted and average rewards. However, these criteria have inherent limitations: discounted optimality may overly prioritise short-term rewards, while average optimality relies on strong structural assumptions. Blackwell optimality addresses these challenges, offering a robust and comprehensive criterion that ensures optimality under both discounted and average reward frameworks. Despite its theoretical appeal, existing algorithms for computing Blackwell Optimal (BO) policies are computationally expensive or hard to implement. In this paper we describe procedures for computing BO policies using an ordering of rational functions in the vicinity of $1$. We adapt state-of-the-art algorithms for deterministic and general MDPs, replacing numerical evaluations with symbolic operations on rational functions to derive bounds independent of bit complexity. For deterministic MDPs, we give the first strongly polynomial-time algorithms for computing BO policies, and for general MDPs we obtain the first subexponential-time algorithm. We further generalise several policy iteration algorithms, extending the best known upper bounds from the discounted to the Blackwell criterion.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Issues concerning realizability of Blackwell optimal policies in reinforcement learning
N-discount optimality was introduced as a hierarchical form of policy- and value-function optimality, with Blackwell optimality lying at the top level of the hierarchy Veinott (1969); Blackwell (1962). We formalize notio…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor
We introduce the Blackwell discount factor for Markov Decision Processes (MDPs). Classical objectives for MDPs include discounted, average, and Blackwell optimality. Many existing approaches to computing average-optimal …
Provably Efficient Algorithms for Multi-Objective Competitive RL
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 r…
Multi-Objective Reinforcement LearningReinforcement Learning (RL)Blackwell Equilibrium in Repeated Games
We apply Blackwell optimality to repeated games. An equilibrium whose strategy profile is sequentially rational for all high enough discount factors simultaneously is a Blackwell (subgame-perfect, perfect public, etc.) e…
Towards Blackwell Optimality: Bellman Optimality Is All You Can Get
Although average gain optimality is a commonly adopted performance measure in Markov Decision Processes (MDPs), it is often too asymptotic. Further incorporating measures of immediate losses leads to the hierarchy of bia…