4 ms·

I'm trying to refresh mind on what Q learning is, if I may think out loud here? Q is an evaluation of how good a state is assuming the agent acts optimally goi

I'm trying to refresh mind on what Q learning is, if I may think out loud here? Q is an evaluation of how good a state is assuming the agent acts optimally going forward. In Chess for example, sacrificing a rook to capture a queen would have a high Q value. Sacing a rook is bad, but gaining the queen later is better. Q values are supposed to see past immediate consequences and reflect the long term consequences. How do we find a Q value though? We can look several steps ahead, or we can look to the end of the game, etc. These aren't real Q values though, because optimal actions probably weren't taken. We can use Bellman equations, which roughly update one Q value by a small amount to the maximum of the next possible states, which results in the highest Q values gradually flowing backward into states that can lead to good outcomes. I'm trying to think how this would apply to LLMs though. Where do the basic values come from? In Chess the basic values are the number of pieces, or whether or not a side ultimately wins. What are the basic values in a LLM? What is the Q agent aiming to do?

jacquesm 3y ago
In computer chess, traditionally 'minimax' was the strategy that allowed you to efficiently probe ahead. The only requirement for this is that your evaluation function returns a single (scalar) value.
seanhunter 3y ago
I don't think your intuition about computer chess is going to help you here with transformer architecture. Usually in transformer models[1], for each attention head there are 3 vectors of weights, known as q(uery), k(ey) and v(alue). I was assuming that the q in q* applied to the q vector, so q-learning is training this vector. In a transformer model you don't have an objective function for any sort of state evaluation so it can't be the Q you're thinking of. If they've done something funky with the q vector that could indeed be a breakthrough since a lot of people feel that we are sort of running out of juice with scaling transformers as-is and need a new architecture to really have a step change in capability. That's pure speculation on my part though. [1] Here's Vaswani et al, the paper that first set out the transformer architecture https://arxiv.org/abs/1706.03762 https://arxiv.org/abs/1706.03762
- Buttons840 3y ago
  Good point. I'm thinking of the Q from reinforcement learning, but as you say, this Q is probably different.
- a_wild_dandan 3y ago
  Current architectures have a lot of juice left across several axes, using extraordinarily accurate scaling laws. We're nowhere close to a wall. The industry has been focusing hard on 'System Two' approaches to augment our largely 'System One'-style models, where optimal decision policies make Q-learning a natural approach. The recent unlock here might be related to using the neural nets' general intelligence/flexibility to better broadly estimate their own states/rewards/actions (like humans). [EDIT: To be clear, the Q-learning stuff is my own speculation, whereas the 'System Two' stuff is well known.] Serendipitously, Karpathy broadly discussed these two issues yesterday! Toward the lecture's end: https://www.youtube.com/watch?v=zjkBMFhNj_g https://www.youtube.com/watch?v=zjkBMFhNj_g
  - visarga 3y ago
    How do you apply Q-learning to LLMs? They would need to estimate the action-value of each action in a given state. How can you pick the best action when you only have a scoring function that would rate how good each action is, but the action space is infinite. You can't pick the best action. It is probably something else, like Decision Transformer.
    - silveraxe93 3y ago
      That got solved using Deep-Q learning. I think David Silver did loads of work on it? Basically, instead of computing every state value like in normal Q learning. You use a Neural Network to estimate the best value.
      - visarga 3y ago
        If I remember correctly DQLearning is using discrete action space, limited number of possible actions which makes it possible to simply take the argmax_i(qvalue(state, action_i))
nuc1e0n 3y ago
It's probably something to do with path finding with constraints in high dimensional search spaces I'd guess. Like quake bots used to do in the late 90s
deleted 3y ago
[deleted]
pyinstallwoes 3y ago
https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/A*_search_algorithm there's interesting complexity on the definition, especially in consideration of the "different implmenetations" - very interesting. I think Theta* is the ticket: https://en.wikipedia.org/wiki/Theta https://en.wikipedia.org/wiki/Theta*
- skissane 3y ago
  You meant to link to https://en.m.wikipedia.org/wiki/Theta%2A https://en.m.wikipedia.org/wiki/Theta%2A HN’s software doesn’t recognise an asterisk in a URL as part of the URL
deleted 3y ago
[deleted]
visarga 3y ago
> Q is an evaluation of how good a state is assuming the agent acts optimally going forward. The Q-value represents the expected utility or the total reward of taking a certain action in a given state, followed by following an optimal policy thereafter. So, yes, it does evaluate how "good" or beneficial a state is, but specifically in conjunction with a chosen action and under the assumption that the agent will act optimally in the future. So it is conditioned on state and action, not just on state.

jacquesm 3y ago

In computer chess, traditionally 'minimax' was the strategy that allowed you to efficiently probe ahead. The only requirement for this is that your evaluation function returns a single (scalar) value.

seanhunter 3y ago

I don't think your intuition about computer chess is going to help you here with transformer architecture. Usually in transformer models[1], for each attention head there are 3 vectors of weights, known as q(uery), k(ey) and v(alue). I was assuming that the q in q* applied to the q vector, so q-learning is training this vector. In a transformer model you don't have an objective function for any sort of state evaluation so it can't be the Q you're thinking of. If they've done something funky with the q vector that could indeed be a breakthrough since a lot of people feel that we are sort of running out of juice with scaling transformers as-is and need a new architecture to really have a step change in capability. That's pure speculation on my part though. [1] Here's Vaswani et al, the paper that first set out the transformer architecture https://arxiv.org/abs/1706.03762 https://arxiv.org/abs/1706.03762

Buttons840 3y ago
Good point. I'm thinking of the Q from reinforcement learning, but as you say, this Q is probably different.
a_wild_dandan 3y ago
Current architectures have a lot of juice left across several axes, using extraordinarily accurate scaling laws. We're nowhere close to a wall. The industry has been focusing hard on 'System Two' approaches to augment our largely 'System One'-style models, where optimal decision policies make Q-learning a natural approach. The recent unlock here might be related to using the neural nets' general intelligence/flexibility to better broadly estimate their own states/rewards/actions (like humans). [EDIT: To be clear, the Q-learning stuff is my own speculation, whereas the 'System Two' stuff is well known.] Serendipitously, Karpathy broadly discussed these two issues yesterday! Toward the lecture's end: https://www.youtube.com/watch?v=zjkBMFhNj_g https://www.youtube.com/watch?v=zjkBMFhNj_g
- visarga 3y ago
  How do you apply Q-learning to LLMs? They would need to estimate the action-value of each action in a given state. How can you pick the best action when you only have a scoring function that would rate how good each action is, but the action space is infinite. You can't pick the best action. It is probably something else, like Decision Transformer.
  - silveraxe93 3y ago
    That got solved using Deep-Q learning. I think David Silver did loads of work on it? Basically, instead of computing every state value like in normal Q learning. You use a Neural Network to estimate the best value.
    - visarga 3y ago
      If I remember correctly DQLearning is using discrete action space, limited number of possible actions which makes it possible to simply take the argmax_i(qvalue(state, action_i))

nuc1e0n 3y ago

It's probably something to do with path finding with constraints in high dimensional search spaces I'd guess. Like quake bots used to do in the late 90s

deleted 3y ago

[deleted]

pyinstallwoes 3y ago

https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/A*_search_algorithm there's interesting complexity on the definition, especially in consideration of the "different implmenetations" - very interesting. I think Theta* is the ticket: https://en.wikipedia.org/wiki/Theta https://en.wikipedia.org/wiki/Theta*

skissane 3y ago
You meant to link to https://en.m.wikipedia.org/wiki/Theta%2A https://en.m.wikipedia.org/wiki/Theta%2A HN’s software doesn’t recognise an asterisk in a URL as part of the URL

deleted 3y ago

[deleted]

visarga 3y ago

> Q is an evaluation of how good a state is assuming the agent acts optimally going forward. The Q-value represents the expected utility or the total reward of taking a certain action in a given state, followed by following an optimal policy thereafter. So, yes, it does evaluate how "good" or beneficial a state is, but specifically in conjunction with a chosen action and under the assumption that the agent will act optimally in the future. So it is conditioned on state and action, not just on state.