Answers.Body: <blockquote>
  <p>How can I approach projects with a big state space without loosing a huge chunk of predictability (which I might fear with DQN, DDPQ or TD3)?</p>
  </blockquote>
  <p>You can impact this by choosing a combination of function approximator and engineered features which are a good match to predicting either the value functions or policy function that an agent will need to produce.</p>
  <p>It is hard to tell a priori how much work you would need in this regard. Given that you play as many training games as you have time for, use a deep neural network with hardware acceleration, then one approach is to simply normalise/scale your feature vector as it is, and train heavily. This approach in RL has repeatedly shown new state-of-the-art results for e.g. AlphaZero, Open AI's DoTA agent and others. This appears to work provided the compute resource that you can throw at the problem is large enough. As you mention, card-counted blackjack is a solved problem, so doing this may be within your reach on consumer hardware.</p>
  <p>Some smart feature engineering may help though, by making the core problem easier for the agent. As this is a hobby project, what you do will depend on what you want the agent to learn. Is the purpose of your project to teach the agent how to card-count from scratch? Given that you have told the agent the count of remaining cards in the state, it does not appear so.</p>
  <p>Next question: Do you need the agent to learn to sum up all remaining cards in order to calculate the raw probability of revealing a card of each type amongst cards so far unseen? That's currently what your main state feature is doing. If you don't need the agent to learn that, you could help by using the <em>probability</em> of each card being seen as a feature instead of the remaining count. This feature is likely to reduce the complexity of value and policy functions, thus it will reduce compute time, and may also improve accuracy.</p>
  <p>With a game that can be solved analytically, you could take this up to the point of deriving the optimal policy directly and not using RL at all (i.e the input to your NN would be the correct action or the action values!). The question for your project is then this: What precisely are you hoping to demonstrate that your agent can learn? Or maybe: What do you want to gain by applying RL to this problem?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-12T09:34:20.087Z
Answers.Text: Yes, you’re right, I could parse the probability of each card appearing as an input - though that wouldn’t condense my state space, would it? I’d still input an integer value for each card type into my action space, except this time it represents a probability (which could be calculated by simple dividing the amount of said card left and the total amount of cards left). I don’t see any advantage of deriving this value beforehand? For my specific problem, it’s important to consider the probability of each card appearing in the next turn.
Answers.UserDisplayName: J. M. Arnold
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-12T09:40:20.860Z
Answers.Text: My goal is to programmatically determine the best choice for each stage in the game. My first approach was to backcalculate any decision tree within the MDP, though this ended up to be ineffective due to sheer amount of calculation required (even with alpha beta pruning and other shorting techniques). After that I went ahead and tried to implement an agent playing the game, but as mentioned ended up with monstrous state spaces, therefore making it ineffective.
Answers.UserDisplayName: J. M. Arnold
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-12T11:19:12.413Z
Answers.Text: "I don’t see any advantage of deriving this value beforehand?" Although the calculation is trivial, it is specific, very likely to be useful when calulating expected return, and a learning algorithm could take some time to stumble across an approximation to it statistically from the data.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-12T11:27:59.457Z
Answers.Text: tho the size of a single digit in comparison to multiple might be valuable in a huge q-table - as you’re apparently proposing.
Answers.UserDisplayName: J. M. Arnold
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-12T11:49:36.810Z
Answers.Text: I am not proposing any Q table at all. You will need to use an approximator such as a neural network. Your question is about making that neural network more accurate. My first paragraph explains in general wht you might need to do tyo make it more accurate. The second para explains why you might not need that. Third para onwards suggest some specific things you may want to consider.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-11T08:30:10.490Z
Answers.LastActivityDate: 2021-09-11T11:00:41.337Z
Answers.LastEditDate: 2021-09-11T11:00:41.337Z
Answers.UserDisplayName: Neil Slater
Body: <p>Consider a single-player card game which shares many characteristics to &quot;unprofessional&quot; (not being played in casino, <em>refer point 2</em>) Blackjack, i.e.:</p>
  <ul>
  <li>You're playing against a dealer with fixed rules.</li>
  <li>You have one card deck which is played completely through.</li>
  <li><em>etc. An exact description of the game isn't needed for my question, thus I remain with these simple bullet points.</em></li>
  </ul>
  <p>Especially the second point bears an important implication. The more cards that have been seen, the higher your odds of predicting the subsequent card - up to a 100% probability for the last card. Obviously, this rule allows for precise exploitation of said game.</p>
  <p>As far as the <strong>action</strong> and <strong>state space</strong> is concerned: The action space is discrete, the player only has a fixed amount of actions (in this case five - <em>due to the missing explanation of the rules, I won't go in-depth about this</em>). Way more important is the state space. In my case, I decided to structure it as follows:</p>
  <div class="s-table-container">
  <table class="s-table">
  <thead>
  <tr>
  <th>A</th>
  <th>2</th>
  <th>3</th>
  <th>4</th>
  <th>5</th>
  <th>6</th>
  <th>7</th>
  <th>8</th>
  <th>9</th>
  <th>10</th>
  <th>J</th>
  </tr>
  </thead>
  <tbody>
  <tr>
  <td>4</td>
  <td>4</td>
  <td>4</td>
  <td>4</td>
  <td>4</td>
  <td>4</td>
  <td>4</td>
  <td>4</td>
  <td>4</td>
  <td>14</td>
  <td>2</td>
  </tr>
  </tbody>
  </table>
  </div>
  <p>First part of my state space describes each card value being left in the stack, thus on the first move all 52 cards are still in the deck. This part alone allows for about 7 million possible variations.</p>
  <p>Second part of the state space describes various decks in the game (<em>once again without the rules it's hard to explain in detail</em>). Basically  five integers ranging from 0-21, depending on previous actions. Another 200k distinct situations.</p>
  <p>Third part are two details - some known cards and information, though they only account for a small factor, but still bring in a considerable amount of variation into my state space.</p>
  <p>Thus a complete state space might look something like this: Example one would be the start setup: <code>444444444142;00000;00</code>. Another example in midst of the game: <code>42431443081;1704520;013</code>. <em>Semicolons have been added for readability purposes.</em></p>
  <p>So now arises the question: From my understanding my state space is definitely finite and discrete, but too big to be solved by SARSA, Q-learning, Monte Carlo or alike. How can I approach projects with a big state space without loosing a huge chunk of predictability (which I might fear with DQN, DDPQ or TD3)? Peculiarly due to the fact that only one deck is being used - and it's played through in this game - it seems like a more precise solution would be possible.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-09T07:20:23.960Z
Comments.Text: If there are any questions left, feel free to post them below.
Comments.UserDisplayName: J. M. Arnold
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-11T07:15:08.747Z
Comments.Text: 1. The explanation of the state/action space is unclear. You mention "rules" with no explanation as to what these are or how they affect the game. It seems to me like the state space should be 12 dimensional (number of each of the 11 cards in deck, + value of your current hand). I don't understand this second part "various decks in the game" or the third part "details". Are the 5 actions corresponding to https://en.wikipedia.org/wiki/Blackjack#Player_decisions?
Comments.UserDisplayName: Taw
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-11T07:18:37.810Z
Comments.Text: 2. What do you mean by "losing a huge chunk of predictability" when using something like DQN/DDPG? Also I should point out that you don't have to use neural network function approximators - one popular option is using linear combinations of hand picked features as your function approximator.
Comments.UserDisplayName: Taw
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-11T07:19:52.057Z
Comments.Text: Also, as far as I'm aware, blackjack is a solved game, so that offers a precise solution to the optimal blackjack policy.
Comments.UserDisplayName: Taw
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-12T09:29:37.850Z
Comments.Text: @Taw Thanks for your replies. To clear things up a bit: The game resembles Blackjack in some rudimentary characteristics, i.e. cards can be counted - but it’s not Blackjack. Should have mentioned that more clearly. My simple problem is the sheer size of the underlying state space (it can’t be shortened further or else considerable losses in performance would arise). As far as your second question is concerned, I was referring to the approximating of my state space - which, if Implemented poorly, could end up with a horrible performance. Nonetheless, I’d be curious to how you’d approach that.
Comments.UserDisplayName: J. M. Arnold
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-15T11:43:30.733Z
Comments.Text: How many active turns do you need to look ahead in this game? If it's played in short, separate rounds with the only thing preserved between them being state, then you might be able to do a tree search in limited memory.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-15T16:46:42.517Z
Comments.Text: i would believe that blackjack in the settings you describe can be solved analytically as well........ the expected value of each next draw can be computed very cleanly, and so i don't see any problem with an analytic solution.
Comments.UserDisplayName: k.c. sayz 'k.c sayz'
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-07T21:38:54.867Z
Comments.Text: @k.c.sayz'k.csayz' Problem is computational capacity.
Comments.UserDisplayName: J. M. Arnold
Tags: <reinforcement-learning><deep-learning><q-learning><state-spaces>
Title: How to approach a blackjack-like card game with the possibility of cards being counted?
UserDisplayName: J. M. Arnold
ThreadText: # How to approach a blackjack-like card game with the possibility of cards being counted?
  
  (Asked by: username_0 on 2021-09-08)
  
  Consider a single-player card game which shares many characteristics to "unprofessional" (not being played in casino, *refer point 2*) Blackjack, i.e.:
  
  * You're playing against a dealer with fixed rules.
  * You have one card deck which is played completely through.
  * *etc. An exact description of the game isn't needed for my question, thus I remain with these simple bullet points.*
  
  Especially the second point bears an important implication. The more cards that have been seen, the higher your odds of predicting the subsequent card - up to a 100% probability for the last card. Obviously, this rule allows for precise exploitation of said game.
  
  As far as the **action** and **state space** is concerned: The action space is discrete, the player only has a fixed amount of actions (in this case five - *due to the missing explanation of the rules, I won't go in-depth about this*). Way more important is the state space. In my case, I decided to structure it as follows:
  
  | A | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | J |
  | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
  | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 14 | 2 |
  
  First part of my state space describes each card value being left in the stack, thus on the first move all 52 cards are still in the deck. This part alone allows for about 7 million possible variations.
  
  Second part of the state space describes various decks in the game (*once again without the rules it's hard to explain in detail*). Basically five integers ranging from 0-21, depending on previous actions. Another 200k distinct situations.
  
  Third part are two details - some known cards and information, though they only account for a small factor, but still bring in a considerable amount of variation into my state space.
  
  Thus a complete state space might look something like this: Example one would be the start setup: `444444444142;00000;00`. Another example in midst of the game: `42431443081;1704520;013`. *Semicolons have been added for readability purposes.*
  
  So now arises the question: From my understanding my state space is definitely finite and discrete, but too big to be solved by SARSA, Q-learning, Monte Carlo or alike. How can I approach projects with a big state space without loosing a huge chunk of predictability (which I might fear with DQN, DDPQ or TD3)? Peculiarly due to the fact that only one deck is being used - and it's played through in this game - it seems like a more precise solution would be possible.
  
  **Tags:** reinforcement-learning, deep-learning, q-learning, state-spaces
  
  > **Comments:**
  > **username_0**: If there are any questions left, feel free to post them below.  
  > **username_1**: 1. The explanation of the state/action space is unclear. You mention "rules" with no explanation as to what these are or how they affect the game. It seems to me like the state space should be 12 dimensional (number of each of the 11 cards in deck, + value of your current hand). I don't understand this second part "various decks in the game" or the third part "details". Are the 5 actions corresponding to https://en.wikipedia.org/wiki/Blackjack#Player_decisions?  
  > **username_1**: 2. What do you mean by "losing a huge chunk of predictability" when using something like DQN/DDPG? Also I should point out that you don't have to use neural network function approximators - one popular option is using linear combinations of hand picked features as your function approximator.  
  > **username_1**: Also, as far as I'm aware, blackjack is a solved game, so that offers a precise solution to the optimal blackjack policy.  
  > **username_0**: @username_1 Thanks for your replies. To clear things up a bit: The game resembles Blackjack in some rudimentary characteristics, i.e. cards can be counted - but it’s not Blackjack. Should have mentioned that more clearly. My simple problem is the sheer size of the underlying state space (it can’t be shortened further or else considerable losses in performance would arise). As far as your second question is concerned, I was referring to the approximating of my state space - which, if Implemented poorly, could end up with a horrible performance. Nonetheless, I’d be curious to how you’d approach that.  
  > **username_2**: How many active turns do you need to look ahead in this game? If it's played in short, separate rounds with the only thing preserved between them being state, then you might be able to do a tree search in limited memory.  
  > **username_3**: i would believe that blackjack in the settings you describe can be solved analytically as well........ the expected value of each next draw can be computed very cleanly, and so i don't see any problem with an analytic solution.  
  > **username_0**: @username_3sayz'k.csayz' Problem is computational capacity.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-09-11. Score: 2
  
  > How can I approach projects with a big state space without loosing a huge chunk of predictability (which I might fear with DQN, DDPQ or TD3)?
  
  You can impact this by choosing a combination of function approximator and engineered features which are a good match to predicting either the value functions or policy function that an agent will need to produce.
  
  It is hard to tell a priori how much work you would need in this regard. Given that you play as many training games as you have time for, use a deep neural network with hardware acceleration, then one approach is to simply normalise/scale your feature vector as it is, and train heavily. This approach in RL has repeatedly shown new state-of-the-art results for e.g. AlphaZero, Open AI's DoTA agent and others. This appears to work provided the compute resource that you can throw at the problem is large enough. As you mention, card-counted blackjack is a solved problem, so doing this may be within your reach on consumer hardware.
  
  Some smart feature engineering may help though, by making the core problem easier for the agent. As this is a hobby project, what you do will depend on what you want the agent to learn. Is the purpose of your project to teach the agent how to card-count from scratch? Given that you have told the agent the count of remaining cards in the state, it does not appear so.
  
  Next question: Do you need the agent to learn to sum up all remaining cards in order to calculate the raw probability of revealing a card of each type amongst cards so far unseen? That's currently what your main state feature is doing. If you don't need the agent to learn that, you could help by using the *probability* of each card being seen as a feature instead of the remaining count. This feature is likely to reduce the complexity of value and policy functions, thus it will reduce compute time, and may also improve accuracy.
  
  With a game that can be solved analytically, you could take this up to the point of deriving the optimal policy directly and not using RL at all (i.e the input to your NN would be the correct action or the action values!). The question for your project is then this: What precisely are you hoping to demonstrate that your agent can learn? Or maybe: What do you want to gain by applying RL to this problem?
  
  > **Comments:**
  > **username_0**: Yes, you’re right, I could parse the probability of each card appearing as an input - though that wouldn’t condense my state space, would it? I’d still input an integer value for each card type into my action space, except this time it represents a probability (which could be calculated by simple dividing the amount of said card left and the total amount of cards left). I don’t see any advantage of deriving this value beforehand? For my specific problem, it’s important to consider the probability of each card appearing in the next turn.  
  > **username_0**: My goal is to programmatically determine the best choice for each stage in the game. My first approach was to backcalculate any decision tree within the MDP, though this ended up to be ineffective due to sheer amount of calculation required (even with alpha beta pruning and other shorting techniques). After that I went ahead and tried to implement an agent playing the game, but as mentioned ended up with monstrous state spaces, therefore making it ineffective.  
  > **username_2**: "I don’t see any advantage of deriving this value beforehand?" Although the calculation is trivial, it is specific, very likely to be useful when calulating expected return, and a learning algorithm could take some time to stumble across an approximation to it statistically from the data.  
  > **username_0**: tho the size of a single digit in comparison to multiple might be valuable in a huge q-table - as you’re apparently proposing.  
  > **username_2**: I am not proposing any Q table at all. You will need to use an approximator such as a neural network. Your question is about making that neural network more accurate. My first paragraph explains in general wht you might need to do tyo make it more accurate. The second para explains why you might not need that. Third para onwards suggest some specific things you may want to consider.  
  
  ---
  
  