Q-learning is not yet scalable
seohong.me
seohong.me
As horizon increases, the number of possible states (usually) increases exponentially. This means you require exponentially increasing data to have a hope of training a Q that can handle those states.
This is less of an issue for on policy learning, because only near policy states are important, and on policy learning explicitly only samples those states. So even though there are exponential possible states your training data is laser focused on the important ones.
Total layman here, but maybe some tasks are "uniform" despite being "deep" in such a way that poor samples still suffice? I would call those "ergodic" tasks. But surely there are other tasks where this is not the case?
There are situations where states increase at much slower rates than exponential.
Those situations are a good fit for Q learning.
An exponential number of states only matters if there is no pattern to them. If there is some structure that the network can learn then it can perform well. This is a strength of deep learning, not a weakness. The trick is getting the right training objective, which the article claims q learning isn't.
I do wonder if MuZero and other model based RL systems are the solution to the author's concerns. MuZero can reanalyze prior trajectories to improve training efficiency. The Monte Carlo Tree Search (MCTS) is a principled way to perform horizon reduction by unrolling the model multiple steps. The max operator in MCTS could cause similar issues but the search progressing deeper counteracts this.
I don’t think it’s hopeless though, I actually think RL is very close to working because what it lacked this whole time was a reliable world model/forward dynamics function (because then you don’t have to explore, you can plan). And now we’ve got that.
Most RL researchers consider these approaches not to be "real RL", as they can't assign credit outside the context window, and therefore can't learn infinite-horizon tasks. With 1m+ context windows, perhaps this is less of an issue in practice? Curious to hear thoughts.
The hardness of the credit assignment problem is a statement about data sparsity. Architecture choices do not "bypass" it.
The DT citation [10] is used on a single line, in a paragraph listing prior work, as an "and more". Another paper that uses DTs [53] is also cited in a similar way. The authors do not test or discuss DTs.
> hardness of the credit assignment ... data sparsity.
That is true, but not the point I'm making. "Bypassing credit assignment", in the context of long-horizon task modeling, is a statement about using attention to allocate long-horizon reward without horizon-reducing discount, not architecture choice.
To expand: if I have an environment with a key that unlocks a door thousands of steps later, Q-Learning may not propagate the reward signal from opening the door to the moment of picking up the key, because of the discount of future reward terms over a long horizon. A decision transformer, however, can attend to the moment of picking up the key while opening the door, which bypasses the problem of establishing this long-horizon causal connection.
(Of course, attention cannot assign reward if the moment the key was picked up is beyond the extent of the context window.)
Apologies if we're talking past one another.
Not always! That's what makes some expert demonstrations so fascinating, watching someone do something "completely wrong" (according to novice level 'best practice') and achieve superior results. Of course, sometimes this just means that you can get away with using that kind of technique (or making that kind of blunder) if you're just that good.
Yes the model may not be able to tackle long horizon tasks from scratch, but learn some shorter horizon skills first then learn a longer horizon by leveraging groupings of those smaller skills. Chunking like we all do.
Nobody learns how to fly a commercial airplane plane cross country as a sequence of micro hand and arm movements. We learn to pick up a ball that way when young, but learning to fly or play a sport consists of a hierarchy of learned skills and plans.
For example, you can use a dataset of chess games from agents that move totally randomly (with no strategy at all) and use that as an input for Q-Learning, and it will still converge on an optimal policy (albeit more slowly than if you had more high-quality inputs)
For example, if you have really sparse rewards in a long-horizon task (say, a reward appears 1000 timesteps after the action), then a discount factor of even 0.99 won't help to capture that: 0.99 ^ 1000 ≈ 4e^-5.
Essentially, if your discount factor is too small for an environment, it will be near impossible to learn certain credit assignments.
https://arxiv.org/abs/2410.14606
Note that this is from Turing award winner Richard Sutton’s lab at UofA
RL works
AlphaZero/MuZero are not model based, and aren't on policy either. They train at a significantly higher temperature, and thus intentional suboptimal play, than they use when playing to win. LeelaChessZero has further improvements to reduce the bias on training on suboptimal play.
There's a well known tradeoff in TD learning based on how many steps ahead you look- 1-step TD converges off policy, but can give you total nonsense/high bias when your Q function isn't trained. Many-step can't give you nonsense because it scores based on the real result, but that real result came from suboptimal play so your own off-policyness biases the results, plus it's higher variance. It's not hard to adjust between these two in AlphaZero training as you progress to minimize overall bias/variance. (As in, AlphaZero can easily do this- I'm not saying the tuning of the schedule of how to do it is easy!)
The idea of sub-optimal play to increase learning is interesting. We can notice the human social phenomenon of being annoyed at players who play games “too mechanically” or boringly, and admiration of players (even in an overly studied game like chess) with an “intuitive” style.
I wonder how AI training strategies would change if the number of games they were allowed to play was fairly limited, to the handful of thousands of matches of a game that a person might play over the course of their lives. And perhaps if their “rank” was evaluated over the course of their training, like it is for humans.
MuZero doesn't actually learn a state transition function- it only models reward. It's a model that predicts reward given an action sequence. I suppose we could consider this a hybrid that's slightly model based because it does have an incentive to learn what's going on. But there's no feedback where we predict future world states and feed that back in.
If I understand correctly, they show random play, and expect perfect play to emerge from the naive Q-learning training objective.
In layman's term, they expect the algorithm to observe random smashing of keys on a piano, and produce a full-fledge symphony.
The main reason it doesn't work is because it's fundamentally some Out Of Distribution training.
Neural networks works best in interpolation mode. When you get into Out Of Distribution mode, aka extrapolation mode, you rely on some additional regularization.
One such regularization you can add, is to trying to predict the next observations, and build an internal model whose features help make the decision for the next action. Other regularization may be to unroll in your head multiple actions in a row and use the prediction as a training signal. But all these strategies are no longer the domain of the "model-free" RL they are trying to do.
Other regularization, can be making the decision function more smooth, often by reducing the number of parameters (which goes against the idea of scaling).
The adage is "no plan survive first contact with the enemy". There needs to be some form of exploration. You must somehow learn about the areas of the environment where you need to operate. Without interaction from the environment, one way to do this is to "grok" a simple model of the environment (fitting perfectly all observation (by searching for it) so as to build a perfect simulator), and learn on-policy from this simulation.
Alternatively if you have already some not so bad demonstrations in your training dataset, you can get it to work a little better than the policy of the dataset, and that's why it seems promising but it's really not because it's just relying of all the various facets of the complexity already present in the dataset.
If you allow some iterative gathering phase of information from the environment, interlaced with some off-policy training, it's the well known domain of Bayesian methods to allow efficient exploration of the space like "kriging", "gaussian process regression", multi-arm bandits and "energy-based modeling", which allow you to trade more compute for sample efficiency.
The principle being you try model what you know and don't know about the environment. There is a trade-off between the uncertainty that you have because you have not explored the area of space yet and the uncertainty because the model don't fit the observation perfectly yet. You force yourself to explore unknown area so as not to have regrets (Thomson Sampling) ) but still sample promising regions of the space.
In contrast to on-policy learning, the "bayesian exploration learning" learn in an off-policy fashion all possible policies. Your robot doesn't only learn to go from A to B in the fastest way. Instead it explicitly tries to learn various locomotion policies, like trotting or galloping, and other gaits and use them to go from A to B, but spend more time perfecting galloping as it seems that galloping is faster than trotting.
Possibly you can also learn adaptive strategy like they do in sim-to-real experiments where your learned policy is based on unknown parameters like how much weight your robot carry, and your learned policy will estimate on-the-fly these unknown parameters to become more robust (aka filling in the missing parameters to let the optimal "Model Predictive Control" work).
They control for the data being in-distribution
Their dataset also has examples of the problem being solved.
PS: Not sure where to put algorithms like TD-MPC or DreamerV3, since they are kind of in between, right?