Markov Decision Processes: Discrete Stochastic Dynamic Programming

By Martin L. Puterman. 1994

How researchers see this paper

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

In Reinforcement Learning

Citations in the corpus

Bayesian Structure Learning with Generative Flow Networks (2022, methodology): “A GFlowNet is structurally equivalent to a Markov Decision Process (MDP; Puterman, 1994) with deterministic dynamics, or a Markov Reward Process (Howard, 1971).”
Mastering Atari, Go, chess and shogi by planning with a learned model (2019, methodology): “Once a model has been constructed, it is straightforward to apply MDP planning algorithms, such as value iteration [31] or Monte-Carlo tree search (MCTS) [7], to compute the optimal value or optimal policy for the MDP.”
DeepMDP: Learning Continuous Latent Space Models for Representation Learning (2019, background): “Background Define a Markov Decision Process (MDP) in standard fashion:M “ xS,A,R,P, γy (Puterman, 1994).”
Observe and Look Further: Achieving Consistent Performance on Atari (2018, background): “While there may be several optimal policies, they all share a common optimal action-value function Q ∗ [16].”
IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures (2018, background): “We consider the problem of discounted inﬁnite-horizon RL in Markov Decision Processes (MDP), see (Puterman, 1994; Sutton & Barto, 1998) where the goal is to ﬁnd a policy π that maximises the expected sum of future discounted rewards: ≥ , where γ ∈ [0 , 1) is the discount factor, r t = r ( x t , a t…”
Neural Approaches to Conversational AI (2018, positive): “will lead to algorithmic considerations that are often unique to RL. As illustrated in Fig. 2.5, the agent-environment interaction is often modeled as a discrete-time Markov decision process, or MDP (Puterman, 1994), described by a ﬁve-tuple M= hS;A;P;R; i: Sis a possibly inﬁnite set of states the e”
Generative Adversarial Imitation Learning (2016, neutral): “2, we need the basic result that the set of valid occupancy measuresD , {ρπ : π ∈ Π} can be written as a feasible set of affine constraints [19]: if p0(s) is the distribution of starting states andP (s′|s, a) is the dynamics model, then D = { ρ : ρ ≥ 0 and ∑ a ρ(s, a) = p0(s) + γ ∑ s′,a P (s|s′, a)ρ”
Safe and Efficient Off-Policy Reinforcement Learning (2016, background): “The Bellman optimality operator introduces a maximization over the set of policies: Its ﬁxed point is Q ∗ , the unique optimal value function (Puterman, 1994).”
Value-Decomposition Networks For Cooperative Multi-Agent Learning (2017, methodology): “This is typically modelled as a Markov decision process (MDP) (e.g. Puterman, 1994) deﬁned by a tuple (cid:104)S , A , T 1 , T , R (cid:105) comprising the state space S , action space A , a (possibly stochastic) reward function R : S × A × S → R start state distribution T 1 ∈ P ( S ) and…”
RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “0 we obtain (Tˇ)t[0] = tX 1 k=0 Pk!: (A89) For ﬁnite horizon MDPs, the values Vˇ= 0 are correct for time step T+ 1 since there is no reward for t>T+ 1. Therefore the “backward induction algorithm” [82,83] gives the correct solution: Vˇ = (Tˇ)T[0] = TX 1 k=0 Pk!: (A90) The product of square stocha”
Improving Robot Controller Transparency Through Autonomous Policy Explanation (2017, background): “Researchers have identified Markov decision processes [33] as a promising basis for the design and implementation of these desired diagnostic and explanatory capabilities.”
Reinforcement learning in robotics: A survey (2013, background): “…approaches Much of the reinforcement learning literature has focused on solving the optimization problem in Equations (1)–(3) in its dual form (Puterman, 1994; Gordon, 1999).2 Using Lagrange multipliers Vπ ( s′ ) and R̄, we can express the Lagrangian of the problem by L = ∑ s,a μπ ( s)π (s,…”
Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning (2020, background): “We should note that B π is indeed diﬀerent from the Bellman operator [33]; although they have some similarities.”
GenDICE: Generalized Offline Estimation of Stationary Values (2020, background): “Consider a Markov Decision Process (MDP) M = 〈S,A,P, R, γ, μ0〉 (Puterman, 2014), where S is a state space, A is an action space, P (s′|s, a) denotes the transition dynamics, R is a reward function, γ ∈ (0, 1] is a discounted factor, and μ0 is the initial state distribution.”
GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values (2020, background): “, 2020a), where we want to estimate the performance of a target policy (average reward in the continuing setting or expected total discounted reward in the episodic setting (Puterman, 2014)), from data generated by one or more behavior policies.”
Reinforcement Learning via Fenchel-Rockafellar Duality (2020, methodology): “Is there a better way? There is a more direct way to frame the policy optimization problem as a convex problem, and it is given by the V -LP (Puterman, 1994; Bertsekas et al., 1995; Bertsekas and Tsitsiklis, 1996; Wang et al., 2007).”
AlgaeDICE: Policy Gradient from Arbitrary Experience (2019, methodology): “This objective may be equivalently written in its dual form (Puterman, 1994; Wang et al., 2008) in terms of the policy’s normalized state visitation distribution as where As we will discuss in Section 4 and Appendix A, these objectives are the primal and dual of the same linear programming (LP)…”
Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation (2019, methodology): “…The fact that the density function dπ forms a dual variable of the value function V π is widely known in the optimal control and reinforcement learning literature (e.g., Bertsekas, 2000; Puterman, 2014; de Farias & Van Roy, 2003), and has been leveraged in various works for policy optimization.”