Simulation-based optimization of Markov reward processes

By Peter Marbach, John N. Tsitsiklis. 1998

We propose a simulation-based algorithm for optimizing the average reward in a Markov reward process that depends on a set of parameters. As a special case, the method applies to Markov decision processes where optimization takes place within a parametrized set of policies. The algorithm involves the simulation of a single sample path, and can be implemented online. A convergence result (with probability 1) is provided.

How researchers see this paper

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

Citations in the corpus

Generalized Off-Policy Actor-Critic (2019, methodology): “Reinforcement learning (RL) algorithms based on the policy gradient theorem (Sutton et al., 2000; Marbach and Tsitsiklis, 2001) have recently enjoyed great success in various domains, e.g., achieving human-level performance on Atari games (Mnih et al., 2016).”
An Off-policy Policy Gradient Theorem Using Emphatic Weightings (2018, background): “This theorem [Sutton et al., 2000, Marbach and Tsitsiklis, 2001] simpliﬁes estimation of the gradient, which would otherwise require difﬁcult-to-estimate gradients with respect to the stationary distribution of the policy and potentially of the action-values if they are used.”
Linear Off-Policy Actor-Critic (2012, methodology): “In the conventional on-policy theory of policy-gradient methods, the policy-gradient theorem (Marbach & Tsitsiklis, 1998; Sutton et al., 2000) establishes the relationship between the gradient of the objective function and the expected action values.”
The Optimal Reward Baseline for Gradient-Based Reinforcement Learning (2001, methodology): “" (Marbach and Tsitsiklis, 1998) employ a differential reward, which is the expectation of the sum of the differ ences between the rewards received and the average reward (i.”
Infinite-Horizon Policy-Gradient Estimation (2001, methodology): “A similar estimate to (11)was also proposed by Marbach and Tsitsiklis (1998), but this time withr(Xt)zt( ) replaced by(r(Xt) ̂( ))zt( ), wherê( ) is an estimate of the average reward, and withzt zeroed on visits to an identifiable recurrent state.”
Learning to Control a 6-Degree-of-Freedom Walking Robot (2007, methodology): “Episodic REINFORCE [8] and derivative algorithms such as OLPOMDP [9], the method introduced in [ 10 ], and others.”
An Actor-Critic based controller for glucose regulation in type 1 diabetes (2013, background): “[40] P.”
Reinforcement Learning Through Modulation of Spike-Timing-Dependent Synaptic Plasticity (2007, background): “…by considering an approximation to the gradient of the long-term average of the external reward received by the agent with respect to the parameters w. Results related to the convergence of OLPOMDP to local maxima have been obtained (Bartlett & Baxter, 2000a; Marbach & Tsitsiklis, 1999, 2000).”
Natural actor-critic algorithms (2009, background): “Previous works [48, 61, 11] have shown that the gradient of the average reward for parameterized policies that satisfy (A1) and (A2) is given by1 ∇J(π) = ∑”
Optimizing Average Reward Using Discounted Rewards (2001, unknown): “A promising recent approach to finding the gradient of the average reward was presented by Baxter and Bartlett [2], where a discount parameter controls the bias and variance of the gradient estimate (also see a related approach by Marbach and Tsitsiklis [ 5 ]).”
Model-Free Machine Learning in Biomedicine: Feasibility Study in Type 1 Diabetes (2016, unknown): “Various versions of Actor have been proposed, mainly distinguished by the approximation strategy for the gradientry aðyÞ [41]-[44].”
Reinforcement Learning in POMDP's via Direct Gradient Ascent (2000, unknown): “Approximate algorithms for computing the gradient were also given in Marbach and Tsitsiklis (1998); Marbach (1998), one that sought to solve the aforementioned recurrence problem by demanding only recurrence to one of a set of recurrent states, and another that abandoned recurrence and used…”
A basic formula for online policy gradient algorithms (2005, background): “This note presents a basic formula for policy gradients, based on which many policy-gradient algorithms, including those that have previously appeared in literature (e.g., [1], [2], [12], [19], and [20]), can be developed.”