Is reinforcement learning based on memorization of states during training?

Question

I have just started learning Reinforcement Learning. I was reading a Tic Tac Toe Agent code and what I understood is that basically 2 agents were training by playing 1000s of games and recording various states they discovered during the game and at the end of every game updating the value for the states based on the reward.

So their "learning" was the state values that they had learned throughout all games that they had played. I also ran the agent and discovered that giving the agent a completely new position would cause it to play some random move as it has not seen such a state before.

Questions:

1. So isn't this memorization by random play?
2. What happens when an unseen state is seen by the agent? Random move?
3. How does AlphaGo or similar such agents handle such a large state space? And how would it react to a new unseen state? It wouldn't be random, right?

Answer 1

So isn't this memorization by random play?

A little bit more than memorisation is going on in a simple tabular reinforcement learning (RL) agent. Most notably, the agent aggregates experience to calculate expected future rewards, and does so by backing up experience to adjust estimated values of earlier timesteps. This backup process is key to how RL works.

However, in simple tabular agents, this data is stored separately per state, so there is a strong isolation of estimated values for each state. This does behave a lot like exhaustive learning process that needs to experience each possible state multiple times.

What happens when an unseen state is seen by the agent? Random move?

In the simplest tabular agents, then yes typically a random move, or perhaps an arbitrary one based on initialisation.

How does AlphaGo or similar such agents handle such a large state space? And how would it react to a new unseen state? It wouldn't be random, right?

More sophisticated agents that work on large state spaces use function approximation provided by methods such as neural networks. This is used in place of the table of state values, and allows the agent to generalise from data it has experienced to new unseen data. The neural network is used in this way to solve a prediction problem, for value-based methods that is a regression problem (predict expected future returns from a state given a representation of the state). This is very similar to use of the same methods in supervised learning - the difference being that the target value in the training data is calculated using the backup mechanisms of RL.