Gaussian Based Non-linear Function Approximation for Reinforcement Learning

Reinforcement learning (RL) problems with continuous states and discrete actions (CSDA) can be found in classic examples
such as Cart Pole and Puck World, as well as real world applications such as Market Making. Solutions to CSDA problems
typically involve a function approximation (FA) of the mapping from states to actions and can be linear or nonlinear. Linear
FAs such as tile-coding (Sutton and Barto in Reinforcement learning, 2nd ed, 2009) suffer from state information loss due to
state discretization, whilst non-linear FAs such as DQN (Mnih et al. in Playing atari with deep reinforcement learning, https://
arxiv.org/abs/1312.5602, 2013) are practically infeasible in infinitely large state spaces due to their cubic time complexity
(O(n3)). In this paper, we propose a novel, general solution to CSDA problems, called Gaussian distribution based nonlinear function approximation (GBNLFA). Experimentation on three CSDA RL problems (Cart Pole, Puck World, Market
Marking) demonstrates the superiority of GBNLFA over state-of-the-art FAs, namely tile-coding and DQN. In particular,
GBNLFA resolves the state information loss problem with linear FAs and provides an asymptotically faster algorithm (O(n))
than linear FAs (O(n2)) and neural network based nonlinear FAs (O(n3)).