3
$\begingroup$

I have a scenario where, in an ideal situation, the greedy approach is the best, but when non-idealities are introduced which can be learned, DQN starts doing better. So, after checking what DQN achieved, I tried C51 using the standard implementation from tf.agents (link). A very nice description is given here. But, as shown in the image, C51 does extremely bad.

enter image description here

As you can see, C51 stays at the same level throughout. When learning, the loss right from the first iteration is around 10e-3 and goes on to 10e-5, which definitely impacts the change in the weights. But I am not sure how this can be solved.

The scenario is

  • 1 episode consists of 10 steps and the episode only ends after the 10th step, the episode never ends earlier.

  • states at each step are integer values and can take values between 0 and 1. In the image, states are of shape 20*1.

  • actions have the shape 20*1

  • learning rate = 10e-3

  • exploration factor $\epsilon$ starts out at 0.2 and decays up to 0.01

C51 has 3 additional parameters, which help it to learn the distribution of q-values

num_atoms = 51 # u/param {type:"integer"} 
min_q_value = -20 # u/param {type:"integer"} 
max_q_value = 20 # u/param {type:"integer"}

num_atoms is the number of support that the learned distribution will have, and min_q_value and max_q_value are the endpoints of the q-value distribution. I set them as 51 (the first paper and other implementations keep it as 51 and hence the name 51), and the min and max are set as the min and max possible rewards.

So, if anyone could help me with fine-tuning the parameters for C51 to work, I would be very grateful.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I guess you haven't tried yet to use some kind of hyper-parameter optimization technique (such as random search or a grid search), which will probably be costly, but, without domain knowledge, that may be one solution to your problem, assuming that you do not have bugs in your code and C51 isn't supposed to work (well) on this problem with the given hyper-parameters. I am currently not familiar with C51, so I can't help you further. $\endgroup$
    – nbro
    Nov 21, 2020 at 22:13
  • $\begingroup$ @nbro I see, I used the standard implementation from the website linked and only changed the num_atoms, min_1_value, max_q_value along with the replay memory size. So yes I haven't tweaked a lot of things around it. I will see if I could use any hyper-parameter optimization technique, should be a good learning experience. $\endgroup$
    – user3656142
    Nov 21, 2020 at 22:21
  • 1
    $\begingroup$ Any luck? Looking for information on tuning these parameters myself. $\endgroup$
    – Alexander Higgins
    May 3, 2021 at 3:25

1 Answer 1

Reset to default
3
$\begingroup$

Here is what I discovered empirically, trial and error. Since tuning the parameters are going to be environment specific, I'll lay out mine to give a better understanding of what I found to work for my case. Hopefully someone with better understanding of the algorithm will weigh in:

Environment: A 2D map where an agent controls a simulated PC mouse pad and must navigate from a random spawn point to a random reward point.

Action Space: Discrete(24) -- This was flattened from the original implementation to allow for use in the Q* algorithms.

  • 0-7, mouse buttons, each with one of two states pressed or depressed
public ButtonPressState Left;
public ButtonPressState Middle;
public ButtonPressState Right;
public ButtonPressState Touch;
public ButtonPressState ScrollUp;
public ButtonPressState ScrollDown;
public ButtonPressState IncreaseScroll;
public ButtonPressState DecreaseScroll;
  • 8-15: Angle to move if Touch is in state pressed, incremented by 45°, starting at 0 °up to 315°
public enum D8Dir
{
    UP = 0,         //   0°
    UP_RIGHT = 1,   //  45°
    RIGHT = 2,      //  90°
    DOWN_RIGHT = 3, // 135°
    DOWN = 4,       // 180°
    DOWN_LEFT = 5,  // 225°
    LEFT = 6,       // 270°
    UP_LEFT = 7     // 315°
}
  • 16-23: Speed, an exponent of 2^N representing how may cells to move per step.

Distance normalization: Trial and error led me to normalizing the space. This also brings the benefit of allowing the same trained algorithm to be used for different world sizes, eg a 2x3 vs a 3x2 vs a 3x3 on up to large common monitor dimensions. Specifically, distances are normalized between -1 and 1 for the height and the width of the space. So no matter the dimensions all points map to x and y between -1 and 1. In the case the height and the width differ the smaller is scaled to the size of the larger.

Reward space: After having agents reward exploit iteration after iteration of reward scheme, Rewards are given when an agent moves closer to the target - with closer taking into consideration both "birds eye" and Euclidian distance. After first, took "theoretical" maximum sum of the total rewards summed up to 1 and were assigned by taking the maximum distance an agent might move in a given 2D space to gain a reward. This works out to be the diagonal of the 2D space. I say "theoretical" because unless the agent randomly spawns exactly in one corner and the reward is placed exactly in the other corner, the actual total reward that can be achieved is lower. So in practice the maximum reward for a given episode is the sum of normalized distances between the agent and the reward.

To avoid reward exploitation, only .70% of the reward if the agent moves closer vertically or horizontally when a diagonal move was available. This is to get the agent to take the shortest path moving diagonally with only the sqrt(2) bird's eye reward. Otherwise and agent might move up, then left and collect a reward of 2 normalized units instead of the ~=1.4142 normalized reward units collected for moving diagonally. The .70% keeps the reward for an vertical then horizontal (or vice versa) move to 1.4 which is less than the ~=1.4142 diagonal reward.

Originally, the agent could collect up to a total reward of up to 1 and then 3 additional reward points for reach the target. Using the stock TensorFlow c51 DQN agent against this reward scheme, using the default min_q_value=-10 and max_q_value=10 values (I believe they are referred to as VMIN and VMAX in the literature) I found learning achieved the following results on very small world sizes:

[5/2/2021 5:39:19 PM] Training Started
[5/2/2021 5:39:33 PM] Training Environment (1, 2): 5/2/2021 5:39:33 PM
[5/2/2021 5:40:11 PM] Converged (1, 2) in 00:00:38.8244035 - Steps 2565 Episode 948  Average: 3.000000000000002 
[5/2/2021 5:40:11 PM] Training Environment (2, 1): 5/2/2021 5:40:11 PM
[5/2/2021 5:41:01 PM] Converged (2, 1) in 00:00:49.1426355 - Steps 5802 Episode 1242  Average: 3.000000000000002 
[5/2/2021 5:41:01 PM] Training Environment (2, 2): 5/2/2021 5:41:01 PM
[5/2/2021 5:43:42 PM] Converged (2, 2) in 00:02:41.2581146 - Steps 16573 Episode 3248  Average: 3.0551471839999977 
[5/2/2021 5:43:42 PM] Training Environment (2, 3): 5/2/2021 5:43:42 PM
[5/2/2021 5:53:44 PM] Converged (2, 3) in 00:10:01.8163250 - Steps 56732 Episode 11226  Average: 3.0981306360000063 
[5/2/2021 5:53:44 PM] Training Environment (3, 2): 5/2/2021 5:53:44 PM
[5/2/2021 5:59:13 PM] Converged (3, 2) in 00:05:29.5753945 - Steps 78612 Episode 6276  Average: 3.108986006000001 
[5/2/2021 5:59:13 PM] Training Environment (3, 3): 5/2/2021 5:59:13 PM
[5/2/2021 6:22:50 PM] Converged (3, 3) in 00:23:37.2302437 - Steps 173577 Episode 25603  Average: 3.1401708113999938 
[5/2/2021 6:22:50 PM] Training Environment (4, 4): 5/2/2021 6:22:50 PM
[5/2/2021 7:10:04 PM] Converged (4, 4) in 00:47:13.5879491 - Steps 363685 Episode 46441  Average: 3.1596743723999965 
[5/2/2021 7:10:04 PM] Training Environment (5, 5): 5/2/2021 7:10:04 PM
[5/2/2021 7:20:08 PM] Converged (5, 5) in 00:10:04.1529582 - Steps 404256 Episode 8916  Average: 3.182016046800004 
[5/2/2021 7:20:08 PM] Training Environment (6, 6): 5/2/2021 7:20:08 PM
[5/3/2021 12:33:49 AM] Killed 6x6 - No Convergence: Step 1671400: Reward 1.8765 loss = 2.90894175 (00:00:02.9459997) (eps: 2.9459996999999998)

As can be seen, even for a simple 6x6 world C-51 DQN did not converge even after over 4 hours of wall time on GTX-3080 sampling 1,671,400 steps so I killed it.

So I modified the total possible reward to for the agent moving to sum up to .5. This was simply a matter of dividing the old reward scheme in half (or rather *.5).

I then changed the target reached reward from 3 to .5.

The theoretical maximum reward then totaled to 1, so I changed min_q_value=0 and max_q_value=1 to match the sum of the rewards an agent might achieve. This resulted in wall times ever larger than before.

My latest attempt I used min_q_value=0 and max_q_value=.5 to match the maximum cumulative reward the agent could recieve before the collecting the .5 target reached reward, (which BTW is also a terminal state in my environment).

The new rewards, normalized to total to 1 run orders of a magnitude faster for the larger spaces. The 6x6 world "converged" after 05 minutes, 43 secs using 88721 total steps in 88721 in 4624 total episodes.

I still find this slow, but clearly the q values matching the range of cumulative rewards is an improvement.

[5/3/2021 12:49:35 AM] Training Environment (1, 2): 5/3/2021 12:49:35 AM
[5/3/2021 12:50:12 AM] Converged (1, 2) in 00:00:36.8244207 - Steps 2424 Episode 981  Average: 0.5000000000000002 
[5/3/2021 12:50:12 AM] Training Environment (2, 1): 5/3/2021 12:50:12 AM
[5/3/2021 12:50:37 AM] Converged (2, 1) in 00:00:24.6645133 - Steps 4075 Episode 700  Average: 0.5000000000000002
[5/3/2021 12:51:52 AM] Converged (2, 2) in 00:01:15.0585713 - Steps 8135 Episode 1419  Average: 0.5314644659999993 
[5/3/2021 12:51:52 AM] Training Environment (2, 3): 5/3/2021 12:51:52 AM
[5/3/2021 12:52:39 AM] Converged (2, 3) in 00:00:47.0126118 - Steps 11266 Episode 961  Average: 0.5455624971999997 
[5/3/2021 12:52:39 AM] Training Environment (3, 2): 5/3/2021 12:52:39 AM
[5/3/2021 12:52:56 AM] Converged (3, 2) in 00:00:17.6139995 - Steps 12447 Episode 395  Average: 0.5650996157999993 
[5/3/2021 12:52:56 AM] Training Environment (3, 3): 5/3/2021 12:52:56 AM
[5/3/2021 12:55:56 AM] Converged (3, 3) in 00:02:59.7056623 - Steps 24472 Episode 3403  Average: 0.5863068707999991 
[5/3/2021 12:55:56 AM] Training Environment (4, 4): 5/3/2021 12:55:56 AM
[5/3/2021 1:00:07 AM] Converged (4, 4) in 00:04:11.2932882 - Steps 41259 Episode 4240  Average: 0.6052226153999957 
[5/3/2021 1:00:07 AM] Training Environment (5, 5): 5/3/2021 1:00:07 AM
[5/3/2021 1:06:11 AM] Converged (5, 5) in 00:06:03.8448782 - Steps 65641 Episode 5502  Average: 0.6209708242799977 
[5/3/2021 1:06:11 AM] Training Environment (6, 6): 5/3/2021 1:06:11 AM
[5/3/2021 1:11:54 AM] Converged (6, 6) in 00:05:43.2033837 - Steps 88721 Episode 4624  Average: 0.6089312343400013

FYI: The paper states that Transitions to a terminal state are handled with γt = 0.

Update:

The 9x9 environment took 294,897 steps, in 37,025 episodes over 51 minutes and 38 seconds. It may be the case that the max_q_value=1 works better in the larger world sizes where an agent might collect more movement reward. In any case, these values are nearly quadratically better than the default values from the tutorial. I will experiment with them more.

Additionally, tuning n-steps might help. My implementation may also have an issue using the replay buffer memories from smaller world sizes as I am changing the world size dynamically an currently not clearing the buffer.

[5/3/2021 2:03:33 AM] Converged (9, 9) in 00:51:38.4201434 - Steps 294897 Episode 37025  Average: 0.6425936848799915
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ appreciate the detailed answer, will look into it and see if I can also borrow some of your ideas. $\endgroup$
    – user3656142
    May 3, 2021 at 23:23

You must log in to answer this question.

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