0
$\begingroup$

For a DQN algorithm, where my state is a list of values, say: [5, 3, 4, 7, 8, 2, 6]

How can I define an action space that allows me to move a value in the list from one position to another? For example, the action should tell to move the '7' to the first position in the list. Here assume that the reward is a function of the order of values in the list.

This is likely similar to how chess would be played, where the action is a combination of picking a piece and choosing a position to put it in.

Note: this is an overgeneralization of what I actually want to do, but conceptually this is representative enough.

$\endgroup$

1 Answer 1

1
$\begingroup$

I had tried working on a problem similar to this using combinatorial scoring games. I ran into other issues with the players competing, but I think I can give some advice to how I handled this.

In my scenario, I had an array with game pieces for each (two) player. They had to pick a piece to play on, and a direction to move it. I was able to teach the policy to pick its own piece by:

  • reward of +1 when it picked a moveable piece
  • reward of -1 if it chose an unmovable piece, and forced it to choose a new piece to move

The policy was able to learn "I need to pick a playable piece to optimize the reward".

For your case, your action space could be two indices (move a value from the first index to the second). If you have arrays of varying sizes/dimensions, possibly that could be an observation? By forcing the policy to choose pairs of indices until one is valid, you will hopefully be able to teach it to pick viable pairs immediately.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer! So am I correct in assuming that the action space would be a discrete space? If so, do you have any suggestion which RL method to use? In my understanding, DQN is probably not the best way since the Q-network's output is a scalar value for each action, which would likely be telling us "move this piece" but won't tell us "where to move the piece". In other words, how to define a tuple of actions using a neural network? A common answer I found was to have the number of neurons in final layer equal to the product of number of actions and dimensionality of the actions. $\endgroup$
    – sbk
    Mar 7 at 5:54
  • $\begingroup$ Yes the action space would be discrete of size 2. The ranges would be equal to the dimension of your array, since we can move any piece to any other location. Not sure which algorithm would be best for this, you could try and integrate your algorithm with OpenAI's Gym environments and try some open source packages for RL algorithms (stable-baselines, for example). Good luck! $\endgroup$
    – Elfurd
    Mar 8 at 12:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .