Learning Finite-State Controllers for Partially Observable Environments
This work addresses the need for memory-based policies in partially observable environments, offering an incremental improvement by adapting an existing algorithm to learn finite-state automata.
The paper tackles the problem of learning finite-state controllers for partially observable Markov decision processes by extending the VAPS algorithm to perform stochastic gradient descent, achieving convergence to locally optimal controllers and demonstrating improved performance over exact gradient descent in empirical tests.
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 finite-state 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.