Is this a Q-learning algorithm or just brute force?

Question

I have been playing with an algorithm that learns how to play tictactoe. The basic pseudocode is:

repeat many thousand times {
  repeat until game is over {
    if(board layout is unknown or exploring) {
      move randomly
    } else {
      move in location which historically gives highest reward
    }
  }

  for each step in the game {
    determine board layout for current step
    if(board layout is unknown) {
      add board layout to memory
    }
    update reward for board layout based on game outcome
  }
}

now play a human and win :-)

Exploration: in the beginning the algorithm explores aggresively, and this reduces linearly. After say a thousand games it only explores in 10% of the moves. All other moves are based on exploitation of previous rewards.

Rewards: if the game resulted in a win, then award 10 points. If the game resulted in a draw, 0 points, otherwise -5 points. Actually, these rewards can be "tuned", so that if the game was shorter and it was won, then award more points or if it was longer award less points. This way the algorithm prefers winning quickly. That means that it learns to win as soon as possible, rather than aiming to win later on. That is important so that it doesn't miss winning immediately - if it missed such a move the opponent would likely a) move there to avoid letting the AI win next time, and b) think the algorithm was stupid because it missed an "obvious" win.

This algorithm does indeed learn, so I can class it as a maching learning algorithm.

I think, but I am not sure, that it is a reinforced learning algorithm. However, according to https://www.cse.unsw.edu.au/~cs9417ml/RL1/tdlearning.html it is not temporal difference learning, because it doesn't estimate the rewards until the end, and it should be estimating the reward as it goes along. That might mean that it is not reinforced learning.

Question 1: Can I successfully argue that I am estimating the reward based on history, and still claim the algorithm is reinforced learning or even Q-learning?

Question 2: If I replace the reward lookup which is based on the board layout, with a neural network, where the board layout is the input and the reward is the output, could the algorithm be regarded as deep reinforcement learning?

Question 3: I'd don't think that I have either a learning rate or a discount factor. Is that important?

I noticed that the algorithm is pretty useless unless I train it with at least every move which an opponent tries. So in a way it feels like it's using brute force rather than really "learning". This makes me question whether or not machine learning tictactoe is really learning. I agree that using a neural network to learn image recognition can be classed as learning because when it sees an unknown image it is able to state its classification. But that is quite useless for games like tictactoe where similar looking board layouts are totally unrelated (one may lead to a win, the other may lead to a loss). So...

Question 4: Can tictactoe algorithms be classed as real learning rather than simply brute force?

Update: regarding rewards... when the algorithm is deciding where to go, it works out the reward for each position as follows:

var total = winRewards + drawRewards + lossRewards;
move.reward = (100*(winRewards/total)) + (10*(drawRewards/total)) + (-1*(lossRewards/total));

I divide by the total number of points (for each move), because otherwise it seems to learn that one place is GREAT and doesn't give other ones a chance. This way, we work out the win ratio regardless of how often it's been played. It's normalised in comparison to the others.

The code is available here: https://github.com/maxant/tictactoe/blob/master/ai.js

UPDATE #2: I have since figured out that this algorithm cannot be classed as using brute force because it doesn't actually learn that many games before becoming an expert. Details here: http://blog.maxant.co.uk/pebble/2018/04/11/1523468336936.html

Answer 1

Questions about definitions are always fun, so let me try to offer another answer here.

Firstly, let us model mathematically what you are doing. At the highest level, you are estimating some measure of "reward" $R(s)$ for each board state $s$. You are doing it by interacting with the environment and updating your internal parameters (i.e. the table of $R$ values) towards reinforcing the favorable behaviours. Consequently, by most standard definitions, your algorithm should indeed be categorized as reinforcement learning.

To understand what kind of reinforcement learning you are doing and whether it is "good", we should go a bit deeper. One of the key notions in reinforcement learning is the value function $V$ (or its alter-ego, the $Q$ function), which reports the best possible total reward you may expect to gain if you play optimally from a given board state. If you can show that your algorithm is, at least in some sense, estimating $V$, you can claim a certain "goodness" guarantee, and proceed to classify it into any of the known "good" algorithm types (which all essentially either aim to estimate $V$ directly, or to act as if they estimated it implicitly).

Note that when we speak about two-player games, there does not necessarily exist a unique $V$ to aim for. For example, assuming the reward 1 for winning, 0 for losing, 0.5 for a draw, and no discounting, $V(\text{empty board})$ is $0.5$ if you are playing against an optimal opponent, but it is probably close to $1$ if your opponent is random. If you play against a human, your $V$ may differ depending on the human. Everyone knows that the first move into the center is the safest one, however I myself have never won with such a move - the game always ends in a draw. I did win a couple of times by making the first move to the corner, because it confuses some opponents and they make a mistake on their first turn. This aside, assuming $V$ to denote the game against an optimal opponent is a reasonable choice.

Getting back to your algorithm, the crucial step is the update of $R$, which you did not really specify. Let me assume you are simply accumulating the scores there. If it is the case, we may say that, strictly speaking, you are not doing Q-learning, simply because that's not how the $Q$ function is updated in the classical definition. It still does not mean you are not implicitly estimating the correct $V$, though, and it is rather hard to prove or disprove whether you do it or not eventually.

Let me tune your algorithm a bit for clarity. Instead of adding up the final reward to $R(s)$ for each state $s$, which occurred in the game, let us track the average reward ever reached from each state. Obviously, the position where you always win, although rarely reach, should be more valued than a position where you rarely win, even if you often reach it, so we probably won't break the algorithm by this change, and the overall spirit of learning stays the same anyway. After this change, $R(s)$ becomes easy to interpret - it is the average expected reward reachable from position $s$.

This average expected reward is not really the value function $V$ we are interested in estimating. Our target $V$ should tell us the best expected reward for each position, after all. Interestingly, though, when your policy is already optimal then your average reward is equal to your optimal reward (because you always do optimal moves anyway), hence it may be the case that even though you are kind-of learning the wrong metric in your algorithm, if the learning process pushes your algorithm ever so slightly towards optimal play, as you gradually improve your policy, the "average expected reward" metric itself slowly becomes "more correct" and eventually you start converging to the correct value function. This is pure handwaving, but it should illustrate the claim about it being hard to prove or disprove whether your algorithm formally learns what it should learn. Maybe it does.

In any case, let us, instead of tracking the average reward for each state, change your algorithm to track the best possible reward so far. This means, you'll check all the alternative moves from each position and only update $R(s)$ if your current move resulted in an improved score down the road (in comparison to alternative options you could have taken from this state). Congratulations, now your algorithm is equivalent to the usual Q-learning method (it is the "value iteration" method, to be more precise).

Finally, "is it learning or brute force" is a valid question. The word "learning" can be interpreted in at least two different ways. Firstly, learning may denote simplistic memorization. For example, if I discover that the first move to the center is good, I may write this fact down in a table and use this fact later directly. People call such memorization "learning", but this learning is really quite dumb.

A second, different meaning often ascribed to "learning" is generalization. It would be the case when, besides simply writing down which moves are good, your algorithm could generalize this information to previously unseen moves. This is the "intelligent" kind of learning.

Q-learning, as well as many other RL algorithms are typically formulated in terms of updates to the tables $V$ or $Q$. As such, they are inherently "dumb learning" algorithms, which do not even aim to generalize the state information. True generalization (aka "smart learning") emerges only when you start modeling the state or the policy using something with a built-in generalization ability, such as a neural network.

So, to summarize. Yes, your algorithm is reinforcement learning. No, it is not Q-learning, but it becomes that with a minor change. Yes, it is more "brute force" rather than "intelligent learning", but so is the default Q-learning as well. Yes, adding generalization by modeling states with a neural network makes the algorithm "more intelligent".

Answer 2

Kudos for figuring out a working tic-tac-toe playing algorithm from scratch!

Question 1: Can I successfully argue that I am estimating the reward based on history, and still claim the algorithm is reinforced learning or even Q-learning?

First things first, this is definitely not Q-learning.

However, I do think it classifies as Reinforcement Learning. You have implemented these key components of RL:

• A state (the current board), used as input on each step.

• An action (desired next board arrangement), used as output. When the action is effectively to choose the next state directly, this is sometimes called the afterstate representation. It is commonly used in RL for deterministic games.

• Rewards generated by the environment, where the agent's goal is to maximise expected reward.

• An algorithm that can take data about states, actions and rewards, and learn to optimise expected reward through gaining experience within the environment.

Your algorithm is closest IMO to Monte Carlo Control, which is a standard RL approach.

One of the big advantages of Q Learning is that it will learn an optimal policy even whilst exploring - this is known as off-policy learning, whilst your algorithm is on-policy, i.e. it learns about the values of how it is currently behaving. This is why you have to reduce the exploration rate over time - and that can be a problem because the exploration rate schedule is a hyper-parameter of your learning algorithm that may need careful tuning.

Question 2: If I replace the reward lookup which is based on the board layout, with a neural network, where the board layout is the input and the reward is the output, could the algorithm be regarded as deep reinforcement learning?

Yes, I suppose it would be technically. However, it is unlikely to scale well to more complex problems just from adding a neural network to estimate action values, unless you add in some of the more sophisticated elements, such as using temporal-difference learning or policy gradients.

Question 3: I'd don't think that I have either a learning rate or a discount factor. Is that important?

A discount factor is not important for episodic problems. It is only necessary for continuous problems, where you need to have some kind of time horizon otherwise the predicted reward would be infinite (although you could also replace the discount mechanism with an average reward approach in practice).

The learning rate is an important omission. You don't explain what you have in its stead. You have put update reward for board layout based on game outcome - that update step typically has the learning rate in it. However, for tic-tac-toe and Q-Learning, you can actually set the learning rate to 1.0, which I guess is the same as your approach, and it works. I have written example code that does exactly that - see this line which sets learning rate to 1.0. However, more complex scenarios, especially in non-deterministic environments, would learn badly with such a high learning rate.

Question 4: Can tictactoe algorithms be classed as real learning rather than simply brute force?

Your algorithm is definitely learning something from experience, albeit inefficiently compared to a human. A lot of the more basic RL algorithms have similar issues though, and often need to see each possible state of a system multiple times before they will converge on an answer.

I would say that an exhaustive tree search from the current position during play was "brute force". In a simple game like tictactoe, this is probably more efficient than RL. However, as games get more and more sophisticated, the machine learning approach gets competitive with search. Often both RL and some form of search are used together.