Body: <p>I've recently read much about feature engineering in continuous (uncountable) feature spaces. Now I am interested what methods exist in the setting of large discrete state spaces. For example consider a board game with grid as a basic layout. Each position on a grid can contain exactly one of multiple elements and the agent makes decisions according to the current board position. If the grid is large enough, say 30x30, and there are only two different elements we could model the states as a linear model with <span class="math-container">$2*30*30 = 1800$</span> variables (using dummy variables) and this model can't even distinguish relationships between positions. For this we would need to use <span class="math-container">$\binom{90}{2}$</span> or even <span class="math-container">$\binom{90}{k}$</span>, <span class="math-container">$k = 2, 3, 4$</span> more features.</p>
  <p>How would one approach this problem? Are the methods for feature selection for linear approximations, which even automatically find/learn non-linear combinations? What was the approach to solving these problems when NN where not around?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-08T12:38:22.630Z
Comments.Text: @DuttaA So it's almost necessary to rely on hand crafted features?
Comments.UserDisplayName: s1624210
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-08T13:24:23.180Z
Comments.Text: @DuttaA Ok, of course NN do feature engineering themselves, but for linear models the features have to be selected separately (and we can't use all features).
Comments.UserDisplayName: s1624210
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-08T13:39:22.260Z
Comments.Text: @DuttaA Thank you really much for the insight, I'll check out the lecture as well as deep blue.
Comments.UserDisplayName: s1624210
Tags: <reinforcement-learning><function-approximation><feature-engineering><heuristic-functions><discrete-state-spaces>
Title: How to find good features for a linear function approximation in RL with large discrete state set?
UserDisplayName: s1624210
ThreadText: # How to find good features for a linear function approximation in RL with large discrete state set?
  
  (Asked by: username_0 on 2021-03-07)
  
  I've recently read much about feature engineering in continuous (uncountable) feature spaces. Now I am interested what methods exist in the setting of large discrete state spaces. For example consider a board game with grid as a basic layout. Each position on a grid can contain exactly one of multiple elements and the agent makes decisions according to the current board position. If the grid is large enough, say 30x30, and there are only two different elements we could model the states as a linear model with $2\*30\*30 = 1800$ variables (using dummy variables) and this model can't even distinguish relationships between positions. For this we would need to use $\binom{90}{2}$ or even $\binom{90}{k}$, $k = 2, 3, 4$ more features.
  
  How would one approach this problem? Are the methods for feature selection for linear approximations, which even automatically find/learn non-linear combinations? What was the approach to solving these problems when NN where not around?
  
  **Tags:** reinforcement-learning, function-approximation, feature-engineering, heuristic-functions, discrete-state-spaces
  > **Comments:**
  > **username_0**: @DuttaA So it's almost necessary to rely on hand crafted features?  
  > **username_0**: @DuttaA Ok, of course NN do feature engineering themselves, but for linear models the features have to be selected separately (and we can't use all features).  
  > **username_0**: @DuttaA Thank you really much for the insight, I'll check out the lecture as well as deep blue.  
  
  ---
  
  ## 0 answers
  
  