Learning Finite-State Controllers for Partially Observable Environments

By Nicolas Meuleau, Leonid Peshkin, Kee-Eung Kim, Leslie Pack Kaelbling. 1999

Reactive (memoryless) policies are sufficient in completely observable Markov decision processes (MDPS), but some kind of memory is usually necessary for optimal control of a partially observable MDP. Policies with finite memory can be represented as finite-state automata. In this paper, we extend Baird and Moore's VAPS algorithm to the problem of learning general finite-state automata. Because it performs stochastic gradient descent, this algorithm can be shown to converge to a locally optimal finitestate controller. We provide the details of the algorithm and then consider the question of under what conditions stochastic gradient descent will outperform exact gradient descent. We conclude with empirical results comparing the performance of stochastic and exact gradient descent, and showing the ability of our algorithm to extract the useful information contained in the sequence of past observations to compensate for the lack of observability at each time-step.

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

Deep learning in neural networks: An overview (2014, background): “Many variants of traditional RL exist (e.g., Barto et al., 1983; Watkins, 1989; Watkins and Dayan, 1992; Moore and Atkeson, 1993; Schwartz, 1993; Baird, 1994; Rummery and Niranjan, 1994; Singh, 1994; Baird, 1995; Kaelbling et al., 1995; Peng and Williams, 1996; Mahadevan, 1996; Tsitsiklis and van Ro”
Infinite-Horizon Policy-Gradient Estimation (2001, methodology): “An extension of GPOMDP to policies with parameterized internal belief states is described by Aberdeen and Baxter (2001), similar in spirit to the extension of VAPS and REINFORCE described by Meuleau et al. (1999).”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, methodology): “The parameters or weights of C are trained to maximize reward by a standard RL method such as Q-learning or similar methods [17, 292, 293, 172, 254, 212, 262, 10, 122, 188, 157, 281, 26, 216, 197, 272, 311, 9, 163, 174, 22, 27, 2, 137, 276, 156, 284].”
Learning from Scarce Experience (2002, methodology): “Following Williams’s REINFORCE algorithm (Williams, 1992), searching by gradient descent has been considered for a variety of policy classes (Marbach, 1998; Baird & Moore, 1999; Meuleau et al., 1999; Sutton et al., 1999; Baxter & Bartlett, 2000).”
A survey and critique of multiagent deep reinforcement learning (2018, neutral): “There are also other approaches to deal with partial observability such as finite state controllers [100] (where action selection is performed according to the complete observation history) and using an initiation set of options conditioned”
Inverse Reinforcement Learning in Swarm Systems (2016, background): “Note that, in case of a single agent, this is equivalent to the belief-state value in a partially observable Markov decision process [18, 16].”
Multi-task Reinforcement Learning in Partially Observable Stochastic Environments (2009, background): “The finite policy graphs (Meuleau et al. 1999), finite state controllers (Aberdeen and Baxter 2002), and utile distinction HMMs (Wierstra and Wiering 2004) use internal states to memorize the full history, however, their state transitions are driven by observations only.”
On the undecidability of probabilistic planning and related stochastic optimization problems (2003, background): “Algorithms generating finite controllers show promise in efficiently finding optimal or near optimal policies in many POMDP problems [21,23,36].”
Learning deep neural network policies with continuous memory states (2015, methodology): “Finite state controllers have previously been applied to smaller RL tasks where value function approximation is practical [2], and policy gradient methods have been extended to recurrent neural networks (RNNs) [8].”
A Function Approximation Approach to Estimation of Policy Gradient for POMDP with Structured Policies (2005, methodology): “1(Meuleau et al., 1999) uses the value function to parameterize the policy and uses the path-dependent random cost for gradient estimation in episodic settings.”
Policy Learning with Continuous Memory States for Partially Observed Robotic Control (2015, methodology): “While most policy search methods are concerned with reactive policies, a number of methods have been proposed that augment the policy with internal state, including methods based on finite state controllers [9, 14] and explicit memory states that the policy can alter using memory storage actions [11”
Learning to Cooperate via Policy Search (2000, background): “There are many possibilities for constructing policies with memory [13, 10].”
Point-Based Value Iteration for Continuous POMDPs (2006, methodology): “Model-free techniques such as neuro-dynamic programming (Bertsekas and Tsitsiklis, 1996), and stochastic gradient descent (Meuleau et al., 1999; Ng and Jordan, 2000; Baxter and Bartlett, 2001; Aberdeen and Baxter, 2002) directly optimize a policy by simulation.”
Interactive POMDPs with finite-state models of other agents (2017, background): “Finite-state controllers (FSC) represent in some cases the optimal solution to a POMDP [33]; in fact, some algorithms search directly for a solution in the space of finite state controllers [25,41,51].”