Feedback 27-04-2012

Experiment Results

I also ran experiments in the Six Hump Camel Back environment. Again, all experiments are done over 1000 samples and are averaged over 1000 runs. For every experiment the 95% confidence intervals are displayed by a colored region surrounding the lines.

Incremental Regression Tree Induction (IRTI)

• MCTS_C = (parentRangeSize / globalRewardVolume) * Config.MCTS_K
• MCTS_K=1.0
• IRTI_SPLIT_NR_TESTS=100
• IRTI_SPLIT_MIN_NR_SAMPLES=75
• IRTI_SIGNIFICANCE_LEVEL=0.001
• IRTI_MEMORIZATION = true

Hierarchical Optimistic Optimization (HOO)

• MCTS_C = (parentActionSpaceVolume / globalActionSpaceVolume) * globalRewardVolume * MCTS_K)
• MCTS_K=0.5
• HOO_V_1 = (sqrt(nrActionDimensions) / 2) ^ HOO_ALPHA
• HOO_RHO = 2 ^ (- HOO_ALPHA /  nrActionDimensions)
• HOO_ALPHA=0.99
• HOO_MEMORIZATION = true

IRTI + HOO +  MC + Random + UCT (pre-discretization with 2 splits per depth)

Planning

1. Run experiments regarding the multi-step agents and possibly debug / optimize code.

Feedback 22-04-2012

Experiment Results

Finally some nice results to show after some debugging and parameter tuning; manual and    automatic. All experiments are done over 1,000 samples and are averaged over 10,000 runs. For every experiment the 95% confidence intervals are displayed by a colored region surrounding the lines.

Incremental Regression Tree Induction (IRTI)

• MCTS_C = (childRewardRangeSize / globalRewardRangeSize) * MCTS_K)
• MCTS_K = 2.0
• IRTI_SPLIT_NR_TESTS = 100
• IRTI_SPLIT_MIN_NR_SAMPLES = 50
• IRTI_SIGNIFICANCE_LEVEL = 0.001
• IRTI_MEMORIZATION = true

Hierarchical Optimistic Optimization (HOO)

• MCTS_C  = (parentActionSpaceVolume / globalActionSpaceVolume) * globalRewardVolume * MCTS_K
• MCTS_K=5.0
• HOO_MEMORIZATION = true
• HOO_V_1 = (sqrt(nrActionDimensions) / 2) ^ HOO_ALPHA 
• HOO_RHO = 2 ^ (- HOO_ALPHA /  nrActionDimensions)
• HOO_ALPHA = 0.99

IRTI + HOO +  MC + Random  + UCT (pre-discretization with 25 splits per depth)

Work

Implemented all four multi-step agents and seem to be able to balance the pole in the Cartpole environment pretty well.

1. Regression-based Meta Tree Learning agent (RMTL)
2. Hierarchical Optimistic Meta Tree Learning agent (HOMTL)
3. Regression-based Sequence Tree Learning agent (RSTL)
4. Hierarchical Optimistic Sequence Tree Learning agent (HOSTL)

Planning

1. Find a better parameter set for HOO for the Six Hump Camel Back function as it is now barely better than UCT with pre-discretization in that environment. I can then generate the same pictures as the ones above.
2. Do experiments regarding the multi-step agents and possibly debug / optimize code.

Meeting 12-04-2012

Work

1. Fixing, debugging and improving IRTI and HOO. 
2. Furthermore, a lot of parameter tuning for above two algorithms.

Action Points

1. Michael and I had a discussion about the exploration factor
1. C should be related to the reward range
1. constant C =  globalRangeSize * K
2. adaptive C =  parentRangeSize * K
3. Lukas proposed: adaptive C = (childRangeSize / globalRangeSize) * K
2. For HOO, you should also multiply the last term (diam) with C or divide the first term (mean reward) with C.
1. R + C * exploration + C * diam 
2. R / C + exploration + diam

Planning

• Change the HOO formula (see action points)
• Generate reward distributions (learning curve, greedy curve, error) of several algorithms
• IRTI
• HOO
• UCT (pre-discretization)
• Vanilla MC (random sampling, greedy returns best sample seen)
• Random
• I should ask Lukas about the working of his IRTI algorithm to find out why mine does not converge samling at the global maximum.

Feedback 06-04-2012

Work

1. Looked into sample Scala code for parameters used for the experiments of the TLS paper. Unfortunately I wasn't able to generate the same results yet. From the code, it seems following settings are used:
1. Non-Adaptive C of 0.5
2. T-test
3. minNbSamples = 25
4. minNbSamplesPerPopulation = 5
5. significanceThreshold = 0.001
2. Following 4 points are some experiments performed of Regression Trees / HOO in combination with constant / adaptive C in the Sinus experiment (averaged over 1000 tests).
3. Regression Trees with constant C (= 0.5 *  totalRewardRangeSize)











4. Regression Trees with adaptive C (= 0.5 *  parentRewardRangeSize) 











5. HOO with constant C (= 0.5 * totalRewardRangeSize) 











6. HOO with adaptive C (= 0.5 * parentRewardRangeSize) 











7. Regression trees is not able to sample at the global maximum (as of now). It does not explore and split properly to find the best region.
8. HOO does a much better job than regression trees in the sinus environment and finds the global maximum most of the time.
9. Although an adaptive c constant causes to focus more on the promising regions, it also causes the algorithm to get stuck in local maxima sometimes. Therefore, over multiple tests, the error is lower for HOO with adaptive c.

Feedback 05-04-2012

Work

1. Lukas pointed out that my discounting was incorrect in TLS. The power of the gamma should always match the depth, even when updating nodes lower in the tree. I fixed this.
2. Instantiating nodes beforehand for HOO did not make a difference in the performance.
3. Removing the storage of the action ranges within the nodes (to avoid array copying each split) makes only a small difference in simulations per second. For compatibility and readability I decided to stick to the initial implementation of having the action ranges within the nodes.
4. Updating U and B values before the selection step increased the number of simulations. This means a full tree traversal in done to update the U and B values of all nodes, updating the children before the parent (since the calculation of B takes the B-values of the children). To avoid a stack overflow when using a recursive post-order traversal, I decided to (also) store the (reference to) nodes in a list in which the nodes added in order of creation. By simply using a descendingIterator makes sure the children are always updated before its parent.
5. I tried scaling the exploration term in the calculation of U in HOO, but did not (yet) succeed to let the HOO algorithm perform well in environments with rewards not in the range of 0 to 1. The sinus environment however is in the range of about 0 to 0.6 and HOO performs well as long as the splitting occurs in or near the middle (see next point).
6. I implemented a choice in splitting behaviour for HOO (the decision of where to split given an action range of one of the action dimensions) 
1. Normally distributed around the middle of the range (with an option to change the shape of the "bell")
2. Uniformly distributed
3. Exactly in the middle
7. Splitting sooner for the regression tree agent in the sinus environment did not change the reward;  it keeps sampling in the left most peek most of the time.
8. I found a problem regarding the adaptive C value. This value can be 0, "removing" the exploration term whenever a node has count 1 in the selection step (because then min equals max and therefore the size of the range equals 0). For regression trees this never occurs since a node has gathered more than 1 sample before splitting but for HOO this can be a problem.

Planning

1. Try to split sooner for the Sinus environment and observe results
2. Scaling the exploration term in the calculation of U in HOO
3. Investigate saving of images in RL Viz
4. Generate some pictures / results

Next meeting

• Individual meeting: Thursday, April 12, 2012, 11:00 - 12:00
• Joint meeting: Wednesday, May 2, 13:00 - 15:00