Answers.Body: <p>Yes, it is possible to add states to a Q table after the game has started, for example by storing the &quot;table&quot; in a binary tree.</p>
  <p>Nonetheless, with a simple interpretation of state (like all the pawn positions), Q learning won't work because there are just too many states. Most states will be new so the agent will choose most actions randomly.</p>
  <p>Instead, you'll need to reduce the state space with hand-crafted features, or approximate Q values with a classic Q function approximation or a neural network.</p>
  <p>I'd choose the latter alternative, which is called a Deep Q Network, but neural networks might be challenging if you aren't familiar with them.</p>
  <p>Alternatively, you could use Monte Carlo Tree Search.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-10T19:20:24.317Z
Answers.Text: It's my problem: every state would be seen as new. I only have experience with neural networks for image recognition. Would you be so kind as to give me the name of a book that would point me in the right direction? I hope it isn't strictly forbidden.
Answers.UserDisplayName: Dunno
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-10T19:32:53.843Z
Answers.Text: Reinforcement Learning: An Introduction
  by Richard S. Sutton and Andrew G. Barto is the book I learned from. And it's available online at: http://incompleteideas.net/book/the-book-2nd.html
Answers.UserDisplayName: Lee Reeves
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-10T19:35:43.590Z
Answers.Text: But it's a full textbook covering a lot of RL, and the section on Q learning may be hard to understand on its own. You might find a good tutorial by searching for Approximate Q-Learning or Q function approximation.
Answers.UserDisplayName: Lee Reeves
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-10T19:38:45.990Z
Answers.Text: Is it a legal version?
Answers.UserDisplayName: Dunno
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-10T19:43:07.277Z
Answers.Text: Yes, it's from the authors. The book is Creative Commons licensed, and also sold on Amazon.
Answers.UserDisplayName: Lee Reeves
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-10T18:00:01.863Z
Answers.LastActivityDate: 2022-06-10T19:51:26.230Z
Answers.LastEditDate: 2022-06-10T19:51:26.230Z
Answers.UserDisplayName: Lee Reeves
Body: <p>I would like to implement Q-learning in a game.</p>
  <p>Here is the board:</p>
  <p><a href="https://i.sstatic.net/mnutG.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mnutG.jpg" alt="enter image description here" /></a></p>
  <p>It's a 2 player game. At each turn, each player can put a pawn on a line of their choice. They can't choose the column. The right player will put their pawn on the right column and the left player will put their pawn on the other side. At each turn, each pawn will advance in the direction of the opponent. Each pawn has a cost and each player has an amount of money and health points.</p>
  <p>I was wondering how I could enumerate the number of states, and it seems impossible.</p>
  <p>Given the number of possible states, is Q-learning a solution? If it is, is it possible to add states to the Q-table after the game has started? If Q-learning isn't a solution, what could I use?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-10T17:29:47.127Z
Comments.Text: Put your **SPECIFIC** question in the title. "Add states Q-learning" is not a question. Furthermore, Q-learning is an algorithm and saying "add states Q-learning" doesn't seem to make much sense. So, please, try to ask a clear specific question and put in the title.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-10T17:34:07.433Z
Comments.Text: No need to be so agressive. You understood the question. Anyway, I edited it.
Comments.UserDisplayName: Dunno
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-10T17:41:32.320Z
Comments.Text: Well, "Add states Q-table after initialization" still doesn't make sense and it's not a question, so now it should be clearer why I used capitals and bold. My intention was not to be aggressive but to be super clear. Apparently, it was highly ineffective, but sometimes it is. Here's a clear a question: "What is 2+2? Is it 4 or 5?"
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-10T18:02:02.313Z
Comments.Text: @Dunno Hello and welcome to AI Stack Exchange! Sometimes we are very direct on this website because we want you to receive the best possible answer to your question. We appreciate that you are here, and we look forward to seeing your questions and answers in the near future! :)
Comments.UserDisplayName: DeepQZero
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-11T15:38:02.377Z
Comments.Text: As usual, I do the dirty work of making posts (even those that are not mine) great here. Thank you... This is the last time I do this for you. You should have followed my recommendation to improve your post. Next time, I will just leave the downvote.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><q-learning><implementation>
Title: Is it possible to add states to the Q-table after the game has started?
UserDisplayName: Dunno
ThreadText: # Is it possible to add states to the Q-table after the game has started?
  
  (Asked by: username_0 on 2022-06-10)
  
  I would like to implement Q-learning in a game.
  
  Here is the board:
  
  [![enter image description here](https://i.sstatic.net/mnutG.jpg)](https://i.sstatic.net/mnutG.jpg)
  
  It's a 2 player game. At each turn, each player can put a pawn on a line of their choice. They can't choose the column. The right player will put their pawn on the right column and the left player will put their pawn on the other side. At each turn, each pawn will advance in the direction of the opponent. Each pawn has a cost and each player has an amount of money and health points.
  
  I was wondering how I could enumerate the number of states, and it seems impossible.
  
  Given the number of possible states, is Q-learning a solution? If it is, is it possible to add states to the Q-table after the game has started? If Q-learning isn't a solution, what could I use?
  
  **Tags:** reinforcement-learning, q-learning, implementation
  
  > **Comments:**
  > **username_1**: Put your **SPECIFIC** question in the title. "Add states Q-learning" is not a question. Furthermore, Q-learning is an algorithm and saying "add states Q-learning" doesn't seem to make much sense. So, please, try to ask a clear specific question and put in the title.  
  > **username_0**: No need to be so agressive. You understood the question. Anyway, I edited it.  
  > **username_1**: Well, "Add states Q-table after initialization" still doesn't make sense and it's not a question, so now it should be clearer why I used capitals and bold. My intention was not to be aggressive but to be super clear. Apparently, it was highly ineffective, but sometimes it is. Here's a clear a question: "What is 2+2? Is it 4 or 5?"  
  > **username_2**: @username_0 Hello and welcome to AI Stack Exchange! Sometimes we are very direct on this website because we want you to receive the best possible answer to your question. We appreciate that you are here, and we look forward to seeing your questions and answers in the near future! :)  
  > **username_1**: As usual, I do the dirty work of making posts (even those that are not mine) great here. Thank you... This is the last time I do this for you. You should have followed my recommendation to improve your post. Next time, I will just leave the downvote.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2022-06-10. Score: 0 | Accepted answer
  
  Yes, it is possible to add states to a Q table after the game has started, for example by storing the "table" in a binary tree.
  
  Nonetheless, with a simple interpretation of state (like all the pawn positions), Q learning won't work because there are just too many states. Most states will be new so the agent will choose most actions randomly.
  
  Instead, you'll need to reduce the state space with hand-crafted features, or approximate Q values with a classic Q function approximation or a neural network.
  
  I'd choose the latter alternative, which is called a Deep Q Network, but neural networks might be challenging if you aren't familiar with them.
  
  Alternatively, you could use Monte Carlo Tree Search.
  
  > **Comments:**
  > **username_0**: It's my problem: every state would be seen as new. I only have experience with neural networks for image recognition. Would you be so kind as to give me the name of a book that would point me in the right direction? I hope it isn't strictly forbidden.  
  > **username_3**: Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto is the book I learned from. And it's available online at: http://incompleteideas.net/book/the-book-2nd.html  
  > **username_3**: But it's a full textbook covering a lot of RL, and the section on Q learning may be hard to understand on its own. You might find a good tutorial by searching for Approximate Q-Learning or Q function approximation.  
  > **username_0**: Is it a legal version?  
  > **username_3**: Yes, it's from the authors. The book is Creative Commons licensed, and also sold on Amazon.  
  
  ---
  
  