Exact finite approximations of average-cost countable Markov decision processes

By Xi-Ren Cao, Arie Leizarowitz, Adam Shwartz. 2007

796 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Control and Systems Engineering, Hardware and Architecture, Reinforcement Learning, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Control and Systems Engineering

In Hardware and Architecture

In Reinforcement Learning

In Mathematical Optimization

Citations in the corpus

RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “If we perform this iteration for a policy π instead of the optimal policy, then this procedure is called “policy evaluation algorithm” [82, 83].”
Behavior Regularized Offline Reinforcement Learning (2019, methodology): “We consider the standard fully-observed Markov Decision Process (MDP) setting (Puterman, 1990).”
Approximate Policy Iteration Schemes: A Comparison (2014, methodology): “We consider an inﬁnite-horizon discounted Markov Decision Process (MDP) (Puterman, 1994; Bertsekas & Tsit-siklis, 1996) ( S , A , P, r, γ ) , where S is a possibly inﬁ-nite state space, A is a ﬁnite action space, P ( ds (cid:48) | s, a ) , for all ( s, a ) , is a probability kernel on S , r : S → [ ”
A unified view of entropy-regularized Markov decision processes (2017, background): “MDP theory (see, e.g., Puterman (1994)) stipulates that under mild conditions, the average-reward criterion can be maximized by stationary policies.”
Imitation Learning via Off-Policy Distribution Matching (2019, methodology): “We consider environments represented as a Markov Decision Process (MDP) (Puterman, 2014), deﬁned by the tuple, ( S , A , p 0 ( s ) , p ( s (cid:48) | s, a ) , r ( s, a ) , γ ) , where S and A are the state and action space, respectively, p 0 ( s ) is an initial state distribution, p ( s (cid:48) |…”
Learning Planning Rules in Noisy Stochastic Worlds (2005, methodology): “We implemented a simple planner based on the sparse sampling algorithm (Kearns, Mansour, & Ng 2002), which treats the domain as a Markov Decision Problem (MDP) (Puterman 1999).”
Risk-averse dynamic programming for Markov decision processes (2010, neutral): “Several excellent textbooks and monographs [5,6,21,27,32,39,50] discuss various aspects of this vast area.”
Transfer in Reinforcement Learning via Shared Features (2012, positive): “When the agent's environment is characterized by a finite number of distinct states, it is usually modeled as a finite Markov Decision Process (Puterman, 1994) described by a tuple M = S, A, P, R, where S is the finite set of environment states that the agent may encounter; A is a finite set of acti”
Why Does Hierarchy (Sometimes) Work So Well in Reinforcement Learning? (2019, background): “Furthermore, in Markovian systems, there is no theoretical representational beneﬁt to imposing temporally extended, hierarchical structures, since non-hierarchical policies that make a decision at every step can be optimal (Puterman, 2014).”
Gymnasium: A Standard Interface for Reinforcement Learning Environments (2025, neutral): “Observation space”
Keepaway Soccer: From Machine Learning Testbed to Benchmark (2005, positive): “To handle such situations, it is convenient to treat the problem as a semi-Markov decision process, or SMDP [13, 5].”
FF-Replan: A Baseline for Probabilistic Planning (2007, methodology): “When the first international probabilistic planning competition (Younes & Littman 2004a) was held in 2004, as expected, most of the entries were based on MDP solvers.”
Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems (2006, methodology): “AE procedures are standard practice in solving large practical MDPs and are considered state-of-the-art; see Puterman (1994) for more details.”
Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor (2010, methodology): “…importantly, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement) algorithm, a generalization of Howard s policy iteration algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards.”
Self-Attentional Credit Assignment for Transfer in Reinforcement Learning (2019, neutral): “Background We place ourselves in the classical Markov Decision Process (MDP) formalism (Puterman, 1994).”
The Laplacian in RL: Learning Representations with Efficient Approximations (2018, neutral): “We consider the standard MDP setting (Puterman, 1990).”
Goal-directed decision making as probabilistic inference: a computational framework and potential neural correlates. (2012, background): “…algorithms that have developed in artificial intelligence, machine learning, and operations research for solving multistep decision problems based on preestablished contingency and incentive knowledge (see Bertsekas & Tsitsiklis, 1996; Puterman, 2005; Russell & Norvig, 2002; Sutton & Barto, 1998).”