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 only 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 was apropos is Playing Atari with Deep Reinforcement Learning, which "extracts high level features using a range of neural network architectures".

I've read over the paper but still need to flesh out/fully understand their algorithm. Is this what I'm looking for?

  • $\begingroup$ Several attempts have been made to outperform that paper and some of them include time dependencies using Recurrent Neural Networks with LSTM cells, you can have a look at this post reddit.com/r/MachineLearning/comments/2hdc59/… as well as the blog link. $\endgroup$ May 29, 2015 at 16:29

1 Answer 1


I know I'm late to the party, but in case anybody sees this and is looking for a response here are some thoughts.

Context can be very important in the application of RL algorithms (so forgive me if this is of no use to you). 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: http://www.jmlr.org/papers/volume8/mahadevan07a/mahadevan07a.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:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.