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
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$