The question is basically

  1. What should I do if state vector has variable length?
  2. If the action is bounded and continuous, how can I obtain max(Q(state,action)) without using painfully slow global maximization?

So I was studying reinforcement learning in Space-Invader-like games.

The game itself actually is quite complex, with 5 types of invaders (straight, circle, chasing, random-walk and almost stationary mothership) and lots of randomness inside. Player can choose its velocity(0-1) and direction. A special MP bar is used to generate AOE attack, with MP regen ~ (1-vel)^2

Because the system is way too complex for Q-learning to learn with reasonable speed, I applied a preprocessing ANN first, to identify invaders, lasers and player status (HP, MP, scores, etc).

So I got a list of identified invaders with features like position, velocity, predicted velocity, HP, ticks from fire laser.

However the features now is no longer a fixed-length vector. Also the action is continuous.

I have some ideas but not sure if they're efficient or not.

  1. One neural network per input size. So maybe I have to create dozens of ANNs to cover the entire state-space. (however I'm sure this is not the best way. How can 39 invaders be any different from 40 invaders...)
  2. Discretize the action into, say, 314 points (so 314 output neurons) and use interpolation to get Q-function (but the massive size of network surely will kill the performance)
  • 1
    $\begingroup$ Win Space Invaders, aren't the actions just: go left, go right, fire? $\endgroup$
    – Don Reba
    Jun 1 '15 at 4:16
  • 1
    $\begingroup$ Well it's a space-invader-like game. The state is a velocity vector (v_x,v_y) with v_x^2+v_y^2<=1 BTW, the player spacecraft fires automatically per 6 ticks $\endgroup$ Jun 1 '15 at 4:23
  • $\begingroup$ typo again...The action is a velocity vector, not state :S The state a list of invaders + player information $\endgroup$ Jun 1 '15 at 4:30
  • $\begingroup$ Another way to deal with continuous action would be a NN function approximater w/ input {state,action} and output {Q(state,action),Q_max(state),a_max}. Back-propagation can be implemented easily. However the convergence and performance of this NN would be a big question mark. $\endgroup$ Jun 1 '15 at 6:16
  • $\begingroup$ @AmibaGelos were you able to find a solution to the variable length state space problem? $\endgroup$
    – gnjago
    Jul 1 '16 at 9:00

Sometimes transfoming states is a good thing. You could use distance to reduce your state vectors

E.g. Sample state: vx,vy,evx,evy as states 1,1,2,2 3,3,4,4 1,1,3,....

Transformation is: distance of vx,vy,evx,evy 2 2 1...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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