1
$\begingroup$

I was looking at this implementation for creating an agent for playing Tetris using DeepRL.

This model uses "a state based on the statistics of the board after a potential action. All predictions would be compared but the action with the best state would be used".

So at each iteration, it's feeding a set of future states, computed based on the current state (future state made up of statistics of the game like nb of holes in the board, cleared rows, total height...) to a neural network and outputs one "value" per future state.

So at every step, you predict N "values" from the neural network for all N possible future states for the one you are currently in and choose the greatest one as your future state and thus associated action.

Now, my issue: the implementation says it's "deep Q-learning", but I do not see it that way. The action, nor some sort of current state is given as input of the network.

Since it is feeding the "future states", for me, it looks more like a value iteration algorithm with a neural network or at least something where you know the transition model?

Did I miss something and it is actually DQN? If not, do you have any references for this kind of RL model? Does this have a name?

$\endgroup$
1
$\begingroup$

This is a variant of RL value-based approach using afterstate values. These are similar to action values, but have the following properties:

  • Afterstates treat an action as "choosing a next state". This works well for deterministic environments, or in games where setting a board state is at least deterministic before any random factors might apply (such as an opponent's turn).

  • Afterstates can result in efficient functions (and efficient learning) when there are multiple paths to a given state and where the details of how that state was achieved do not matter much.

  • An afterstate value function is pretty similar to an action value function, provided the agent can predict all the state features that will result. This is not necessarily the same as needing a full model, as it does not need to account for changes after the state is selected due the environment - or opponent - but before the next time step. However, it is often more than a simple action selection, for example in tetris you may have actions which are rotate, shift, drop, but the afterstate selection will be a model of what happens to state for each allowed action selection. So some functions are needed to:

    • Convert allowed actions to afterstates before passing them to an afterstate selection algorithm.

    • Convert selected next states to actions before passing back to the environment.

Environments can also be written to present valid next states and only accept a valid next state as a selection from the agent. It is possible to code Tic Tac Toe agents to do this for example - the environment generates all possible next states, and the agent can select one. The environment may also check that the selected next state is a valid change from the current state. In that case you do not need any conversion between actions and afterstates, everything is handled by passing states between agent and environment. I would not expect a Tetris game and agent to be written so directly like this though.

Due to the similarity of afterstate values with action values, it is straightforward to adjust other value-based methods like Q-learning or SARSA to use afterstates.

$\endgroup$

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.