Is it possible for a reinforcement learning agent to create or generate additional features

Question

Based on what I've read, the best model-free reinforcement learning algorithm to this date is Q-Learning, where each state, action pair in the agent's world is given a Q-value, and at each state the action with the highest Q-value is chosen. The Q-value is then updated as follows:

$$Q(s,a) = (1-\alpha)Q(s,a) +\alpha(R(s,a,s') + (\max_{a'} Q(s',a')))$$

where $\alpha$ is the learning rate.

Apparently, for problems with high dimensionality, the number of states become astronomically large making q-value table storage infeasible.

So the practical implementation of Q-Learning requires using Q-value approximation via generalization of states aka features. For example if the agent was Pacman then the features would be:

• Distance to closest dot
• Distance to closest ghost
• Is Pacman in a tunnel?

And then instead of q-values for every single state you would only need to have q-values for every single feature.

So my question is, is it possible for a reinforcement learning agent to create or generate additional features?

Geramifard's iFDD method is a way of "discovering feature dependencies", but I'm not sure if that is feature generation, as the paper assumes that you start off with a set of binary features.

Another paper that I found apropos is Playing Atari with Deep Reinforcement Learning, which "extracts high level features using a range of neural network architectures".

I need to flesh out/fully understand their algorithm. Is this what I'm looking for?

Answer 1

Context can be very important in the application of RL algorithms. A very interesting method for determining feature vectors (particularly in problems with unique state-space geometries) is using proto-value functions (PVF). The essential idea is that on any state space, there exist basis functions which can be used to approximate any value function you might place on that state-space. This set of functions is based on the intrinsic geometry of the state space and is 'coordinate free' in a sense.

You can read about PVF in the works by Mahadevan and Maggioni. In particular, their journal paper:

Mahadevan, S., & Maggioni, M. (2007). Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes. Journal of Machine Learning Research, 8(10) PDF.

Additionally, you may want to look at both basis function refinement and selection methods. Some references to get you started can be found on pg 98-99 of Busoniu et al.