Answers.Body: <blockquote>
  <p>So can we perfectly learn a solved game as well?</p>
  </blockquote>
  <p>The short answer is yes. If your model has enough complexity it can theoretically learn any behavior you want.</p>
  <blockquote>
  <p>So in theory our model could learn tic-tac-toe</p>
  </blockquote>
  <p>Tic Tac Toe has already been solved. Another popular game that has been solved is Checkers, by the algorithm Chinook.</p>
  <p>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.</p>
  <p>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.</p>
  <p>If you want to learn more about this topic I would highly recommend this series <a href="https://www.youtube.com/watch?v=2pWv7GOvuf0&amp;list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ&amp;ab_channel=DeepMind" rel="nofollow noreferrer">RL Course by David Silver</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-10T15:57:30.690Z
Answers.Text: 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).
Answers.UserDisplayName: Nuclear Hoagie
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T11:34:45.387Z
Answers.Text: "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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T01:13:56.253Z
Answers.Text: @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
Answers.UserDisplayName: BOSSrobot
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-10T02:42:46.690Z
Answers.LastActivityDate: 2020-11-13T07:41:33.947Z
Answers.LastEditDate: 2020-11-13T07:41:33.947Z
Answers.UserDisplayName: BOSSrobot
Body: <p>I had a question today that I feel it must have an answer already, so I'm shopping around.</p>
  <p>If we ask a model to learn the binary OR function, we get perfect accuracy with every model (as far as I know).</p>
  <p>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).</p>
  <p>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.</p>
  <p>So can we perfectly learn a solved game as well?</p>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-09T22:01:31.933Z
Comments.Text: 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.
Comments.UserDisplayName: OmG
Tags: <machine-learning><function-approximation>
Title: Can models get 100% accuracy on solved games?
UserDisplayName: Qfwfq
ThreadText: # Can models get 100% accuracy on solved games?
  
  (Asked by: username_0 on 2020-11-09)
  
  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?
  
  **Tags:** machine-learning, function-approximation
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-11-10. Score: 1
  
  > 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](https://www.youtube.com/watch?v=2pWv7GOvuf0&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ&ab_channel=DeepMind)
  
  > **Comments:**
  > **username_3**: 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).  
  > **username_4**: "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.  
  > **username_2**: @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  
  
  ---
  
  