An Adaptive Optimal Controller for Discrete-Time Markov Environments

By Ian H. Witten. 1977

This paper describes an adaptive controller for discrete-time stochastic environments. The controller receives the environment's current state and a reward signal which indicates the desirability of that state. In response, it selects an appropriate control action and notes its effect. The cycle repeats indefinitely. The control environments to be tackled include the well-known n -armed bandit problem, and the adaptive controller comprises an ensemble of n -armed bandit controllers, suitably interconnected. The design of these constituent elements is not discussed. It is shown that, under certain conditions, the controller's actions eventually become optimal for the particular control task with which it is faced, in the sense that they maximize the expected reward obtained in the future.

Subfields: Reinforcement Learning

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

Towards Coherent and Cohesive Long-form Text Generation (2018, neutral): “This difference relates to reward with baseline in actor-critic methods (Barto et al., 1983; Witten, 1977; Williams, 1992; Sutton et al., 1999) that typically require a separate critic function as a baseline.”
Deep Reinforcement Learning and the Deadly Triad (2018, methodology): “Bootstrapping is also commonly used within policy-gradient and actor-critic methods to learn value functions (Witten, 1977; Barto et al., 1983; Peters and Schaal, 2008; Bhatnagar et al., 2009; van Hasselt, 2012; Degris et al., 2012; Mnih et al., 2016).”
An Off-policy Policy Gradient Theorem Using Emphatic Weightings (2018, methodology): “In policy gradient methods, a parameterized policy is improved using gradient ascent [Williams, 1992], with seminal work in actor-critic algorithms [Witten, 1977, Barto et al., 1983] and many techniques since proposed to reduce variance of the estimates of this gradient [Konda and Tsitsiklis, 2000,…”
The convergence of TD(λ) for general λ (1992, methodology): “Sutton acknowledged the influence of Klopf [9, 10] and in [17] discusses Holland’s bucket brigademethod for classifier systems [8], and a procedure byWitten [22].”
Reinforcement Learning: A Tutorial Survey and Recent Advances (2009, unknown): “Adaptive critics: Adaptive-critic, also called actor-critic, algorithms (Witten , 1977; Barto et al., 1983; Werbös, 1992), are based on combing notions of PI (Howard, 1960) and adaptive function approximation (Werbös, 1987).”
Reinforcement Learning is Direct Adaptive Optimal Control (1992, methodology): “Bycombining methods foradjusting actionselections withmethods forestimating thelong-term consequences ofactions, reinforcement learning methodscanbedevised that areapplicable tocontrol problemsinvolving temporally extended behavior (e.g., [3,4,7,13,14,30,34,35,36, 40 ]).”
Learning to predict by the methods of temporal differences (1988, background): “Witten (1977) presented a sketch of a convergence proof for a TD procedure that predicted discounted costs in a Markov decision problem, but many steps were left out, and it now appears that the theorem he proposed is not true.”
Online Model Learning Algorithms for Actor-Critic Control (2015, methodology): “One specific type of RL algorithms, called actor-critic algorithms (Barto et al., 1983; Konda and Tsitsiklis, 2003; Witten, 1977), split the two entities into two separate functions.”
Introduction to spiking neural networks: Information processing, learning and applications. (2011, methodology): “This technique is often used in neural implementations of the actor-critic model (Witten 1977, Sutton and Barto 2002) , where supervised learning is applied to function approximation in networks representing actor or critic modules (Tham 1995, Jaksa et al. 1999 ).”
Reinforcement learning in robotic applications: a comprehensive survey (2021, methodology): “In-depth knowledge of actor-critic methods can be obtained from (Konda and Tsitsiklis 2000; Witten 1977; Barto et al.”
A comprehensive survey on machine learning for networking: evolution, applications and research opportunities (2018, methodology): “Cerebellar Model Articulation Controller (CMAC) NN model [11], the Expectation Maximization (EM) algorithm [115], the to-be-referred-to as Temporal Difference (TD) learning [478], and the Iterative Dichotomiser 3 (ID3) algorithm [373].”
Basis Function Adaptation in Temporal Difference Reinforcement Learning (2005, methodology): “ferred to as an actor-critic architecture (e.g., Witten, 1977; Barto et al., 1983).”
Ieee Transactions on Systems, Man and Cybernetics—part C: Applications and Reviews 1 a Survey of Actor-critic Reinforcement Learning: Standard and Natural Policy Gradients (unknown): “Actor-critic methods [45], [46] aim to combine the advantages of actor-only and critic-only methods.”