I had a question today that I feel it must have an answer already, so I'm shopping around.

If we ask a model to learn the binary OR function, we get perfect accuracy with every model (as far as I know).

If we ask a model to learn the XOR function we get perfect accuracy with some models and an approximation with others (e.g. perceptrons).

This is due to the way perceptrons are designed -- it's a surface the algorithm can't learn. But again, with a multi-layered neural network, we can get 100% accuracy.

So can we perfectly learn a solved game as well?

Tic-tac-toe is a solved game; an optimal move exists for both players in every state of the game. So in theory our model could learn tic-tac-toe as well as it could a logic function, right?

  • 1
    $\begingroup$ It depends on the VC dimension of the model. If the solution space of the game can be shattered by the learning model, theoretically it is possible. You're right. $\endgroup$ – OmG Nov 9 '20 at 22:01

So can we perfectly learn a solved game as well?

The short answer is yes. If your model has enough complexity it can theoretically learn any behavior you want.

So in theory our model could learn tic-tac-toe

Tic Tac Toe has already been solved. Another popular game that has been solved is Checkers, by the algorithm Chinook.

To be more specific, in Reinforcement Learning we make the assumption that any decision making process can be modeled as an MDP (Markov Decision Process). Once there, there are a host of different methods like Q-Learning and TD that theoretically converge towards the optimal policy - the one the plays perfectly.

Now, just because it is theoretically possible doesn't mean it will always empirically work. In games that are very complex and have a large state space it is extremely difficult to perfectly solve. This is because the only feasible way to go about them is to approximate and getting perfect play even in small edge cases becomes much more difficult as a result.

If you want to learn more about this topic I would highly recommend this series RL Course by David Silver

  • 1
    $\begingroup$ Indeed, a solved game can be expressed simply as a table that enumerates every possible game state and associates it with the optimal move for that state. A sufficiently complex model can simply memorize the table, as it never needs to generalize to unseen states (which would, by definition, not be valid game states). $\endgroup$ – Nuclear Hoagie Nov 10 '20 at 15:57
  • $\begingroup$ "If your model has enough complexity it can theoretically learn anything.", this is not true. Universal approximation theorems say that you can approximate arbitrarily well, they don't say that you can compute exactly. Moreover, they hold for continuous functions. In general, machine learning techniques are naturally approximative methods, so usually find approximative solutions to problems. $\endgroup$ – nbro Nov 11 '20 at 11:34
  • $\begingroup$ @nbro I see your point. Anything is a bit vague. What I was trying to get at was that in RL you can learn any policy you want. In terms of not being able to compute the exact values or being discrete, its not a problem, because approximating values is good enough for your policy to learn optimal behavior. I will edit my answer to make that more clear $\endgroup$ – BOSSrobot Nov 12 '20 at 1:13

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.