Adaboosted trees and q-learning

Question

Question:
Is there a solid mathematical connection between ADABOOST and Q-learning that can inform "higher performance" machine learning algorithms?

Background:
Q-learning references:

• http://www.autonlab.org/tutorials/rl.html
• http://mnemstudio.org/path-finding-q-learning-tutorial.htm
• http://www.autonlab.org/tutorials/rl06.pdf (pg 20) which comes from the (beautiful) autonlab tutorials.

Adaboost references:

• http://rob.schapire.net/papers/explaining-adaboost.pdf
• http://arxiv.org/pdf/1212.1108.pdf
• http://www.site.uottawa.ca/~stan/csi5387/boost-tut-ppr.pdf
• https://en.wikipedia.org/wiki/AdaBoost

The intuition:
The "xgboost" is a great first step in kaggle. Tuning it wins contests. It can be argued that xgboost is a "very high performance" machine learning algorithm.

Q-learning was a component of the deep learning topology that beat the Atari games. (reference) Q-learning has been called the dumbest of smart learning. It is kludgy and slow.

Motivation:

• Gradient Boosted machines are amazingly fast and are the "winningest" on Kaggle. (Most online tutorials make the learning parameter high, which is very risky)
• Q-learning, while the "dumbest" or "slowest" learner, because of its use in things like deep learning (AlphaGo etc) makes it one of the most important to improve
• A clear and technically effective link between the two should allow something between a substantial acceleration in Q-learning and a substantial acceleration in deep-learning.

Note to editors: I worked most of this out and am composing an answer.

Answer 1

This would be a fun exercise. The scope could grow pretty large though, and in an effort to constrain scope this will have two parts, one that has the "discuss the point answer" and the next which is more of a "demo".

(Part 1) Discuss the point:
I'm going to rephrase the question into "how to transform Q-learning" so that it is much more like gradient boosted trees. I'm doing it while thinking about this tutorial.

Q-learning, as I understand it, works as follows:

1. You have a reward function, "R". In the tutorial, it is a table.
2. We have an initialized Q function. It is the policy that is used to decide the next action. In the tutorial, it is a table initialized to zero.
3. We iterate "runs" through the system until some run-count or convergence criteria are met.

Each run is as follows:

• Initialize to some position. In the tutorial, it is uniformly random but alternate approaches can include epsilon-greedy, and weighted random initial as well.
• Select a "next state" using the Q-matrix. In the tutorial, it is uniformly randomly selected. Epsilon-greedy, Epsilon-ascetic, and weighted random are also options here.
• The value of Q is updated using a learning parameter, and whether there is a reward from the R matrix in the next state.
• The next state is set as the current state and iteration proceeds.

Criticisms from the perspective of GBM's might include:

• There is a correlation in the states because the next state depends on the last. This means particular "random" trajectories within the graph must be fully explored, sometimes with nodes traveled several times, while other non-travelled trajectories have nodes that are untouched.
• The learning rate does not change. This connects to the challenge of eigenvalues of multiple sizes. (link) In GBM the weight interacts with the error so learning is highest on highest-error regions.

Commendations from the perspective of GBM's might include:

• The Q-matrix updates every step of every run. For a GBM, this would be like updating the learning weights at the completion of each terminal branch (aka leaf).
• The random start and random path are going to act a little like sub-sampling rows/cols during training, and a little like stochastic gradient descent.

There is also the complication that the explicit input-output mapping present in a GBM does not exist for Q-learning. For Q-learning the Q-matrix does have a final static state, at least for the tutorial, but the diffusion of R along the graph is less pristine. (link)

So here is how to modify Q-learning to make it GBM-ish:

• Be willing to abandon a "run" after one (or few) steps, especially early in learning.
• touch each candidate starting state once before you touch andy candidate twice.
• touch each candidate path once before touching one twice
• account for error in the dynamic weighting of the learning parameter. I think something a little like conjugate gradient (more of a numeric search) could go good distance here.

(Part 2) Working example:
(work in progress)

• a sufficiently complex problem, the tutorial graph is too simple (random graph of sufficient size, perhaps)
• reproducible r-code
• possibly using an actual GBM as the q matrix.