title: In Q-learning with function approximation, is it possible to avoid hand-crafting features?
body: <p>I have little background knowledge of Machine Learning, so please forgive me if my question seems silly.</p>
  
  <p>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:</p>
  
  <p>Q(s,a) = (1-α)Q(s,a) + α(R(s,a,s') + (max_a' * Q(s',a'))) where α is the learning rate.</p>
  
  <p>Apparently, for problems with high dimensionality, the number of states become astronomically large making q-value table storage infeasible. </p>
  
  <p>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:</p>
  
  <ul>
  <li>Distance to closest dot</li>
  <li>Distance to closest ghost</li>
  <li>Is Pacman in a tunnel?</li>
  </ul>
  
  <p>And then instead of q-values for every single state you would only need to only have q-values for every single feature.</p>
  
  <p>So my question is:</p>
  
  <p><strong>Is it possible for a reinforcement learning agent to create or generate additional features?</strong></p>
  
  <p>Some research I've done:</p>
  
  <p><a href="https://stackoverflow.com/a/26601252/800735">This post</a> mentions A Geramifard's iFDD method </p>
  
  <ul>
  <li><a href="http://www.icml-2011.org/papers/473_icmlpaper.pdf" rel="nofollow noreferrer">http://www.icml-2011.org/papers/473_icmlpaper.pdf</a></li>
  <li><a href="http://people.csail.mit.edu/agf/Files/13RLDM-GQ-iFDD+.pdf" rel="nofollow noreferrer">http://people.csail.mit.edu/agf/Files/13RLDM-GQ-iFDD+.pdf</a></li>
  </ul>
  
  <p>which 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.</p>
  
  <p>Another paper that I found was apropos is <a href="http://arxiv.org/pdf/1312.5602v1.pdf" rel="nofollow noreferrer">Playing Atari with Deep Reinforcement Learning</a>, which "extracts high level features using a range of neural network architectures".</p>
  
  <p>I've read over the paper but still need to flesh out/fully understand their algorithm. Is this what I'm looking for?</p>
  
  <p>Thanks</p>