1
$\begingroup$

I have tried several environment libraries like OpenAI gym/gridworld but now I am trying to create a toy environment for experimentation. The environment I've created is as follows:

  1. State: grid with n rows by m columns, represented by a boolean matrix. Each grid cell can be empty or filled and the grid starts empty.

  2. Action: one of the m columns to be filled, which must have at least the top row empty.

  3. Next state: Once a column is chosen, the lowest unfilled cell in that column is filled. This works from bottom up like a very simple version of Tetris.

  4. Reward: after every action, a reward equal to the number of empty columns is awarded.

Therefore in a sample world of 5 rows by 3 column, starting off with an empty grid, the maximum attainable reward would be by filling column wise first. This policy will give a maximum total reward of 2*5 + 1*5 = 15. (2 free columns by 5 row action, once first column is filled then 1 free column by 5 row action.)

This very simple environment is trained using DQN with a single ff layer. The agent only took a few episodes to converge and is able to produce the maximum attainable reward.

In a next toy environment, I've made it a little more complex. I modified the very first action to be random choice of any column. I have retrained the RL model with the new environment modification. However, after convergence, the agent does not attain max score of 15 for all possible starting columns. I.e. If column 1 was randomly chosen first, max score might be 15, however column 2 or 3 was randomly chosen first, max score might only reach 11 or 9. In theory, the optimum policy would be for the agent to fill column that was randomly chosen first - i.e. repeat the first randomly chosen action.

I have tried several ways to tweak my input parameters (e.g. episilon_decay_rate, learning_rate, batch_size, number of hidden nodes) to see if the agent could act optimally for all possible starting columns. I also tried DDQN and Sarsa. The only way I could make the agent perform optimally is by reducing gamma (discount factor) to 0.5 or below. Are there any explanations to why the agent only works for small discount factors in this example? Also, are there alternative ways to obtain the optimum policy?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The description of your environment seems incomplete. I cannot make sense of it. For example you say "Once a column is chosen, that row of the column is filled from bottom up like in a tetris fashion." [emphasis mine]. But at no point has a row been described or selected by the agent or the environment . . . some visualised steps of the game might help, but also review whether you have given a complete and valid description. You definitely have some kind of implementation issue, since for an episodic problem it should be fine to set $\gamma = 1$ and still expect to find optimal solution $\endgroup$
    – Neil Slater
    Feb 3, 2018 at 9:53
  • 1
    $\begingroup$ Sorry for being unclear, indeed my description of action is incomplete. I will try to explain it again. Action: one of the m columns chosen to be filled. Or more precisely. If column j is chosen, S_ij will be set to 1, where i is the min row i such that S_ij != 0. (Here S is the boolean matrix representation of the states) $\endgroup$
    – terenceflow
    Feb 3, 2018 at 15:07
  • 1
    $\begingroup$ Regarding: "This very simple environment is trained using DQN with a single ff layer." If I understand this correctly, you have a linear regression here, there is no hidden layer. Could you confirm the NN architecture? I am imagining it is 15/3 linear network, with 15 inputs -> 3 outputs predicting reward for each of the 3 actions? $\endgroup$
    – Neil Slater
    Feb 3, 2018 at 17:28
  • 1
    $\begingroup$ Yes state matrix is flatten, the network has 15 input and 3 output. Hidden layer has 10 nodes, learning rate is 1e-3. In the first environment, after 20+ episodes the agent is able to obtain the maximum score for any chosen m and n. But not after the modification. $\endgroup$
    – terenceflow
    Feb 4, 2018 at 2:31

1 Answer 1

Reset to default
1
$\begingroup$

This is an episodic problem, and there should be no issue in theory with most learning algorithms coping without a discount factor (or setting gamma = 1).

Are there any explanations to why the agent only works for small discount factors in this example?

The most likely explanations are:

  • You have a mistake in your implementation or use of DQN.

  • You have an incorrect setting of a neural network hyperparameter. My initial thought would be you have mistakenly put a non-linearity like softmax or sigmoid on the NN outputs (it needs to be a linear output). Or it could just be that 10 hidden neurons is not enough for this representation

  • Convergence requires far longer to train than you thought, once you introduce non-linear relationships between state and expected reward.

It is not surprising that the simpler puzzle trains more easily, as the agent can reduce it down to a linear counting puzzle without really needing to "look" at the representation. I would expect the Q values to be very poor approximations to the correct values after so few iterations, but the problem is simple enough that the incorrect values still produce an optimal behaviour.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks so much for your reply! I have tried more hidden nodes, output layer is linear and have waited more than 10k episodes for convergence. I think it might be a mistake in my implementation. Something that I have suspected is due to my implementation of illegal moves. During the choose action step: If the entire column is already filled (S_ij = 1, forall i), I enforced that the column is not allowed to be chosen. And I would choose the next highest action value as the best action. Will this be the main cause of the problem? $\endgroup$
    – terenceflow
    Feb 7, 2018 at 1:22
  • 1
    $\begingroup$ @terenceflow: I don't think that would be a direct cause of a problem - although you should look how you handle the data around that change. I would actually recommend changing the problem so that you terminate the episode on an illegal move, meaning the agent scores whatever it got so far (this is what would happen in Tetris). Note that filling the last column is not necessary for optimal behaviour, the agent scores 0 whatever it does, so it doesn't matter and you should not expect an agent to fill all columns. $\endgroup$
    – Neil Slater
    Feb 7, 2018 at 8:20

You must log in to answer this question.

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