0
$\begingroup$

I am new to reinforcement learning and I am reading off of some tutorial materials, but I have noticed a seldom discussed assumption that we should calculate our action based on Q-value instead of the reward.

Is there a simple reason why this is the case?

Consider the bandit problem. What happens if we did not use Q-value, but simply used the reward to select our strategy? It seems if we see our action yields the highest reward, we should simply repeat our action, instead of calculating some estimate on the reward and base off our decision on the estimate.

Further, wouldn't greedy action selection (or Boltzmann action selection, etc.) make much more sense because we are selecting our action based on highest reward instead of the highest estimate, which may not even be a good estimate?

Lastly, it seems that this would model real life scenario much more closely. I haven't noticed anybody calculating a Q-value in their head when making decisions in reinforcement learning scenarios, almost all of our decisions are based on the immediate (and most frequently, deterministic) reward, especially in game scenarios.

I apologize in advance if this seems to be a really novice observation.

$\endgroup$
1
$\begingroup$

I have noticed a seldom discussed assumption that we should calculate our action based on Q-value instead of the reward.

I think you are getting confused about how estimates, Q-values and knowledge of rewards are arrived at. Ultimately, all reinforcement learning (and the related bandit problems) are concerned about is maximising long-term reward.

$Q$ usually represents either the expected value of $r$ (in bandit problems) or the total of a series of $r$ values expected in future actions. Either way, experiencing a single value of $r$ is rarely enough information for an agent to learn all that it needs to know. The $Q$ value holds accumulated knowledge gained by the agent when it experiences multiple different $r$ values over time.

Is there a simple reason why this is the case?

The key things about the optimisation problems presented in reinforcement learning is how much knowledge the agent starts with about the available rewards and dynamics of the system.

In many reinforcement learning systems, rewards are sparse. In a game for instance, the only rewards might be +1 for winning and -1 for losing. It is not possible to act directly on that knowledge at the start of the game. In order to choose between actions early on in a game, something has to assign a value to those actions. Typical approaches are:

  • Search through possibilities and combinations until reliable values are found.

  • Assign some values based on expert knowledge.

  • Have machine calculate values based on experience of the game.

It is possible to combine all three approaches, and many game-playing routines will combine the first approach (search) with one or both of the other methods. Reinforcement learning is concerned with the last method in this list only, and is not the only way to tackle deterministic environments of games.

Consider the bandit problem. What happens if we did not use Q-value, but simply used the reward to select our strategy? It seems if we see our action yields the highest reward, we should simply repeat our action, instead of calculating some estimate on the reward and base off our decision on the estimate.

Used which reward? The last reward value received when taking the given action? Yes this would work provided the reward was always the same fixed value for each action. This is the same as having a learning rate of 1 - all you need to do is sample each action once, learn the single static reward value, and then the learning agent is done.

However, a deterministic bandit problem with fixed reward values is not an interesting problem. That is literally working through a list and taking the maximum. If that is your actual problem to solve, then you don't need any statistics or machine learning.

Instead, bandit problems are formulated to deal with rewards that are drawn from a random distribution, different for each action, that are not known by the agent (in tests of different bandit solvers, they might be known to the tester). That means when the agent observes a single reward for the first time, it cannot know whether it has a value that represents the expected reward, it could have been lucky or unlucky. The agent has no good option available to it other than to maintain an estimate of the expected reward and refine it as it gains more experience with the action. The different types of bandit solvers are usually assessed in how they can make the best use of this limited knowledge so that total reward is maximised whilst having to go through this experience and estimate-building process.

Further, wouldn't greedy action selection (or Boltzmann action selection, etc.) make much more sense because we are selecting our action based on highest reward instead of the highest estimate, which may not even be a good estimate?

No, this only makes sense if you already know what the highest reward is for each action at the point it is taken. In reinforcement learning, you generally make the assumption that you do not know this. However, if you do know that all state transitions and rewards are static, with no random effects, then you can take advantage of this with a high learning rate and a low exploration rate. That is close to your idea.

There is still one remaining problem even then in the full reinforcement problem, and with completely static non-random behaviour though - that is the number of states and actions, and how they connect. You might know that transitioning from state Y to state Z gives a reward of +100 and all other transitions give a reward of -1, but that does not tell you yet how to behave when in state A. In order to explore the state connectivity, which you do not know (or may be far too large to search exhaustively), you must explore, effectively randomly, and that means whenever you make that connection and find a route [e.g. A, C, N, Y, Z] and score +97, you do not for certain that the value of state A is +97, because there could be other routes. So that would be an estimate.

Lastly, it seems that this would model real life scenario much more closely. I haven't noticed anybody calculating a Q-value in their head

You probably have not noticed anyone calculating a full search tree, or performing minimax alpha beta pruning in a mathematically rigorous way either.

Even in deterministic games, if they are complex enough, then a lot of assessment is done by feel for good and bad positions gained through experience. That "feel" of the value of controlling a bit of the board, or having a good or bad hand in a game of cards is maybe a reasonable analogy to the Q value. This can be augmented by logical search, comparing exact moves into the future in your mind - and that is analogous to how reinforcement-learning based games bots work, they use Q-values as a heuristic to guide searches through logical deterministic play.

Here's maybe a good analogy to Q value in your head: When you play tic-tac-toe (aka noughts and crosses), then you probably know to play in the centre or a corner on your first move. It is highly unlikely that you calculate out the combinations of moves and arrive at that from scratch each time. That is similar to your brain telling you the max $Q$ value, learned from experience.

A lot of games based on fixed moves can have game bots based on tree search. They typically use heuristics to guide the search (e.g. having pieces in the corner is worth more in Othello, the queen is worth 9 points in chess). You can think of the Q-value as a machine learnt version of those heuristics where instead of an expert saying queen is worth 9 pawns, and coding it into the search routine, the machine has determined something similar through experiencing the games.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.