Author name cluster

John Tsitsiklis

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

NeurIPS Conference 1999 Conference Paper

Actor-Critic Algorithms

Vijay Konda
John Tsitsiklis

We propose and analyze a class of actor-critic algorithms for simulation-based optimization of a Markov decision process over a parameterized family of randomized stationary policies. These are two-time-scale algorithms in which the critic uses TD learning with a linear approximation architecture and the actor is updated in an approximate gradient direction based on information pro(cid: 173) vided by the critic. We show that the features for the critic should span a subspace prescribed by the choice of parameterization of the actor. We conclude by discussing convergence properties and some open problems.

PDF Details

NeurIPS Conference 1997 Conference Paper

Reinforcement Learning for Call Admission Control and Routing in Integrated Service Networks

Peter Marbach
Oliver Mihatsch
Miriam Schulte
John Tsitsiklis

We provide a model of the standard watermaze task, and of a more challenging task involving novel platform locations, in which rats exhibit one-trial learning after a few days of training. The model uses hippocampal place cells to support reinforcement learning, and also, in an integrated manner, to build and use allocentric coordinates.

PDF Details

NeurIPS Conference 1996 Conference Paper

Analysis of Temporal-Diffference Learning with Function Approximation

John Tsitsiklis
Benjamin Van Roy

We present new results about the temporal-difference learning al(cid: 173) gorithm, as applied to approximating the cost-to-go function of a Markov chain using linear function approximators. The algo(cid: 173) rithm we analyze performs on-line updating of a parameter vector during a single endless trajectory of an aperiodic irreducible finite state Markov chain. Results include convergence (with probability 1), a characterization of the limit of convergence, and a bound on the resulting approximation error. In addition to establishing new and stronger results than those previously available, our analysis is based on a new line of reasoning that provides new intuition about the dynamics of temporal-difference learning. Furthermore, we discuss the implications of two counter-examples with regards to the Significance of on-line updating and linearly parameterized function approximators.

PDF Details

NeurIPS Conference 1996 Conference Paper

Approximate Solutions to Optimal Stopping Problems

John Tsitsiklis
Benjamin Van Roy

We propose and analyze an algorithm that approximates solutions to the problem of optimal stopping in a discounted irreducible ape(cid: 173) riodic Markov chain. The scheme involves the use of linear com(cid: 173) binations of fixed basis functions to approximate a Q-function. The weights of the linear combination are incrementally updated through an iterative process similar to Q-Iearning, involving sim(cid: 173) ulation of the underlying Markov chain. Due to space limitations, we only provide an overview of a proof of convergence (with prob(cid: 173) ability 1) and bounds on the approximation error. This is the first theoretical result that establishes the soundness of a Q-Iearning(cid: 173) like algorithm when combined with arbitrary linear function ap(cid: 173) proximators to solve a sequential decision problem. Though this paper focuses on the case of finite state spaces, the results extend naturally to continuous and unbounded state spaces, which are ad(cid: 173) dressed in a forthcoming full-length paper.

PDF Details

NeurIPS Conference 1995 Conference Paper

Stable LInear Approximations to Dynamic Programming for Stochastic Control Problems with Local Transitions

Benjamin Van Roy
John Tsitsiklis

We consider the solution to large stochastic control problems by means of methods that rely on compact representations and a vari(cid: 173) ant of the value iteration algorithm to compute approximate cost(cid: 173) to-go functions. While such methods are known to be unstable in general, we identify a new class of problems for which convergence, as well as graceful error bounds, are guaranteed. This class in(cid: 173) volves linear parameterizations of the cost-to- go function together with an assumption that the dynamic programming operator is a contraction with respect to the Euclidean norm when applied to functions in the parameterized class. We provide a special case where this assumption is satisfied, which relies on the locality of transitions in a state space. Other cases will be discussed in a full length version of this paper.

PDF Details