Answers.Body: <p>The <span class="math-container">$Q$</span>-learning rule that you have implemented updates <span class="math-container">$Q(S_t, A_t)$</span> estimates as follows, after executing an action <span class="math-container">$A_t$</span> in a state <span class="math-container">$S_t$</span>, observing a reward <span class="math-container">$R_t$</span>, and reaching a state <span class="math-container">$S_{t+1}$</span> as a result:</p>
  
  <p><span class="math-container">$$Q(S_t, A_t) \gets (1 - \alpha) Q(S_t, A_t) + \alpha (R_t + \gamma \max_a Q(S_{t+1}, a))$$</span></p>
  
  <p>The implementation seems to be correct for the traditional setting for which <span class="math-container">$Q$</span>-learning is normally described; <strong>single-agent MDPs</strong>. The problem is that you have a multi-agent setting, in which <span class="math-container">$Q$</span>-learning is not always directly applicable.</p>
  
  <p>Now, as far as I can see from a very quick glance at your code, it seems like you actually already have taken some important steps towards allowing it to work, and I think it should be quite close to almost working (at least for a simple game like Tic-Tac-Toe) already. Important things that you appear to already be doing correctly:</p>
  
  <ul>
  <li>Self-play training against an opponent who is hopefully gradually improving, as opposed to training against a uniform-at-random agent or a fixed-strategy agent.</li>
  <li>Add randomization during training to ensure sufficient diversity in generated experience.</li>
  </ul>
  
  <hr>
  
  <p>I think the <strong>major issue that remains to be solved</strong> is in <strong>how you define the subsequent state <span class="math-container">$S_{t+1}$</span> after making a move in a state <span class="math-container">$S_t$</span></strong>.</p>
  
  <p>The update target that the <span class="math-container">$Q$</span>-learning update rule moves its <span class="math-container">$Q$</span>-value estimates towards consists of two components:</p>
  
  <ol>
  <li>The observed immediate reward <span class="math-container">$R_t$</span>.</li>
  <li>The discounted predicted future returns <span class="math-container">$\gamma \max_a Q(S_{t+1}, a)$</span> for the greedy policy.</li>
  </ol>
  
  <p>The problem is that, in your implementation, <span class="math-container">$S_{t+1}$</span> <strong>is a state in which the opponent is allowed to make the next move <span class="math-container">$a$</span>, rather than the RL agent</strong>. This means that <span class="math-container">$\max_a Q(S_{t+1}, a)$</span> is an incredibly optimistic, naive, unrealistic estimate of future returns. In fact, <span class="math-container">$\min_a Q(S_{t+1}, a)$</span> would be a much more realistic estimate (against an optimally-playing opponent), because the opponent gets to pick the next action <span class="math-container">$a$</span>.</p>
  
  <p>I think switching in <span class="math-container">$\min_a Q(S_{t+1}, a)$</span> rather than the <span class="math-container">$\max$</span> may have a good chance of working in this scenario, but I'm not 100% sure. It wouldn't be a "pretty" solution though, since you'd no longer be doing <span class="math-container">$Q$</span>-learning, but something else altogether.</p>
  
  <p>The proper <span class="math-container">$Q$</span>-learning update may work well if you only present states to agents in which they're actually allowed to make the next move in the update rule. Essentially, you'd be plugging <span class="math-container">$\max_a Q(S_{t + 2}, a)$</span> into the update rule, replacing <span class="math-container">$S_{t+1}$</span> with <span class="math-container">$S_{t+2}$</span>. Well... that's what you'd be doing in most cases. The only exception to be aware of would be terminal states. If an agent makes a move that leads to a terminal state, you should make sure to also run an additional update for that agent with the terminal game state <span class="math-container">$S_{t+1}$</span> (where <span class="math-container">$Q(S_{t+1}, a)$</span> will always be <span class="math-container">$0$</span> for any action <span class="math-container">$a$</span> if <span class="math-container">$S_{t+1}$</span> is terminal).</p>
  
  <p>For a very closely related question, where I essentially provided an answer in the same spirit, see: <a href="https://ai.stackexchange.com/q/6573/1641">How to see terminal reward in self-play reinforcement learning?</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-23T10:23:36.550Z
Answers.Text: Applying s_t+2 instead of s_t+1 is a brilliant idea. You saved my time! Thanks.
Answers.UserDisplayName: greentec
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-16T19:45:29.007Z
Answers.Text: Wow! That was an incredibly sophisticated answer! I guess that your idea is the best solution to my problem. I'd have to give it some more thought to figure out how to do that properly but thank you very much:). So would you say that Q-learning isn't that good for multi agent tasks in general and if so what would you prefer (A2C, Policy Gradient....)?
  Best Regards
Answers.UserDisplayName: SHA256man
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-16T19:58:33.290Z
Answers.Text: @Robin_at_Cantelli Those are all standard RL agents originally formulated for the standard single-agent MDP setting, they'd all have similar problems. All of these things (including $Q$-learning) *may* work if you treat the opponent as part of "the environment" (which is essentially also what I suggested in my answer, skipping some states means you treat those parts of the trajectory as being part of the environment's inherent dynamics), but you often need extra tricks to avoid "overfitting" to an imperfect player. See also: https://ai.stackexchange.com/q/7963/1641
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-16T20:00:42.017Z
Answers.Text: In addition to that, there's also a whole field of Multi-Agent Reinforcement Learning research with lots of different algorithms dedicated to multi-agent settings (also often variants of traditional RL algorithms, with some extra tricks)
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-16T20:21:46.290Z
Answers.Text: Ok I see. So it seems to be the best approach to use the kind of algorithm (DQN,QL,A2C and so on) which seems to be the best fit for your current problem an if you have the multi agent task on top you try to modify the the state similar to what you suggested.
  Good that I thought about trying to build an agent for the German game of scat in the future. There you have 3 agents...oh dear;)
  Thanks for the outstanding educational experience you provided!
Answers.UserDisplayName: SHA256man
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-16T20:37:16.960Z
Answers.Text: @Robin_at_Cantelli That's right! If the answer helped, you can [mark it as accepted](https://ai.stackexchange.com/help/someone-answers) such that it no longer shows up in the list of unanswered questions. Of course you can also wait until you got a chance to implement my suggestions and verify whether that really completely solves it, or if there is something else that I may have missed.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-16T18:10:04.403Z
Answers.LastActivityDate: 2019-01-16T18:18:57.233Z
Answers.LastEditDate: 2019-01-16T18:18:57.233Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I tried to build a Q-learning agent which you can play tic tac toe against after training.</p>
  <p>Unfortunately, the agent performs pretty poorly. He tries to win but does not try to make me 'not winning' which ends up in me beating up the agent no matter how many loops I gave him for training. I added a reward of 1 for winning the episode and it gets a reward of -0.1 when he tries to put his label on an non-empty square (after the attempt we have s = s'). I also start with an epsilon=1 which decreases in every loop to add some more randomness at the beginning because I witnessed that some (important in my opinion) states did not get updated. Since I spend some hours of debugging without noticeable progress I'd like to know what you think.</p>
  <p>PS: Don't care about some print statements and count variables. Those where for debugging.</p>
  <p>Code here or on <a href="https://github.com/DataHamster/q-learning-tic-tac-toe" rel="nofollow noreferrer">Github</a></p>
  <pre><code>import numpy as np
  import collections
  import time
  
  Gamma = 0.9
  Alpha = 0.2
  
  
  class Environment:
      def __init__(self):
          self.board = np.zeros((3, 3))
          self.x = -1  # player with an x
          self.o = 1  # player with an o
          self.winner = None
          self.ended = False
          self.actions = {0: (0, 0), 1: (0, 1), 2: (0, 2), 3: (1, 0), 4: (1, 1),
                          5: (1, 2), 6: (2, 0), 7: (2, 1), 8: (2, 2)}
  
      def reset_env(self):
          self.board = np.zeros((3, 3))
          self.winner = None
          self.ended = False
  
      def reward(self, sym):
          if not self.game_over():
              return 0
          if self.winner == sym:
              return 10
          else:
              return 0
  
      def get_state(self,):
          k = 0
          h = 0
          for i in range(3):
              for j in range(3):
                  if self.board[i, j] == 0:
                      v = 0
                  elif self.board[i, j] == self.x:
                      v = 1
                  elif self.board[i, j] == self.o:
                      v = 2
                  h += (3**k) * v
                  k += 1
          return h
  
          def random_action(self):
              return np.random.choice(self.actions.keys())
  
      def make_move(self, player, action):
          i, j = self.actions[action]
          if self.board[i, j] == 0:
              self.board[i, j] = player
  
      def game_over(self, force_recalculate=False):
          # returns true if game over (a player has won or it's a draw)
          # otherwise returns false
          # also sets 'winner' instance variable and 'ended' instance variable
          if not force_recalculate and self.ended:
              return self.ended
  
          # check rows
          for i in range(3):
              for player in (self.x, self.o):
                  if self.board[i].sum() == player*3:
                      self.winner = player
                      self.ended = True
                      return True
  
          # check columns
          for j in range(3):
              for player in (self.x, self.o):
                  if self.board[:, j].sum() == player*3:
                      self.winner = player
                      self.ended = True
                      return True
  
          # check diagonals
          for player in (self.x, self.o):
              # top-left -&gt; bottom-right diagonal
              if self.board.trace() == player*3:
                  self.winner = player
                  self.ended = True
                  return True
              # top-right -&gt; bottom-left diagonal
              if np.fliplr(self.board).trace() == player*3:
                  self.winner = player
                  self.ended = True
                  return True
  
          # check if draw
          if np.all((self.board == 0) == False):
              # winner stays None
              self.winner = None
              self.ended = True
              return True
  
          # game is not over
          self.winner = None
          return False
  
      def draw_board(self):
          for i in range(3):
              print(&quot;-------------&quot;)
              for j in range(3):
                  print(&quot;  &quot;, end=&quot;&quot;)
                  if self.board[i, j] == self.x:
                      print(&quot;x &quot;, end=&quot;&quot;)
                  elif self.board[i, j] == self.o:
                      print(&quot;o &quot;, end=&quot;&quot;)
                  else:
                      print(&quot;  &quot;, end=&quot;&quot;)
              print(&quot;&quot;)
          print(&quot;-------------&quot;)
  
  
  
  
  class Agent:
      def __init__(self, Environment, sym):
          self.q_table = collections.defaultdict(float)
          self.env = Environment
          self.epsylon = 1.0
          self.sym = sym
          self.ai = True
  
      def best_value_and_action(self, state):
          best_val, best_act = None, None
          for action in self.env.actions.keys():
              action_value = self.q_table[(state, action)]
              if best_val is None or best_val &lt; action_value:
                  best_val = action_value
                  best_act = action
          return best_val, best_act
  
      def value_update(self, s, a, r, next_s):
          best_v, _ = self.best_value_and_action(next_s)
          new_val = r + Gamma * best_v
          old_val = self.q_table[(s, a)]
          self.q_table[(s, a)] = old_val * (1-Alpha) + new_val * Alpha
  
      def play_step(self, state, random=True):
          if random == False:
              epsylon = 0
          cap = np.random.rand()
          if cap &gt; self.epsylon:
              _, action = self.best_value_and_action(state)
          else:
              action = np.random.choice(list(self.env.actions.keys()))
              self.epsylon *= 0.99998
          self.env.make_move(self.sym, action)
          new_state = self.env.get_state()
          if new_state == state and not self.env.ended:
              reward = -5
          else:
              reward = self.env.reward(self.sym)
          self.value_update(state, action, reward, new_state)
  
  
  class Human:
      def __init__(self, env, sym):
          self.sym = sym
          self.env = env
          self.ai = False
  
      def play_step(self):
          while True:
              move = int(input('enter position like: \n0|1|2\n------\n3|4|5\n------\n6|7|8'))
              if move in list(self.env.actions.keys()):
                  break
          self.env.make_move(self.sym, move)
  
  
  
  def main():
      env = Environment()
      p1 = Agent(env, env.x)
      p2 = Agent(env, env.o)
      draw = 1
      for t in range(1000005):
  
          current_player = None
          episode_length = 0
          while not env.game_over():
              # alternate between players
              # p1 always starts first
              if current_player == p1:
                  current_player = p2
              else:
                  current_player = p1
  
              # current player makes a move
              current_player.play_step(env.get_state())
  
          env.reset_env()
  
          if t % 1000 == 0:
              print(t)
              print(p1.q_table[(0, 0)])
              print(p1.q_table[(0, 1)])
              print(p1.q_table[(0, 2)])
              print(p1.q_table[(0, 3)])
              print(p1.q_table[(0, 4)])
              print(p1.q_table[(0, 5)])
              print(p1.q_table[(0, 6)])
              print(p1.q_table[(0, 7)])
              print(p1.q_table[(0, 8)])
              print(p1.epsylon)
  
      env.reset_env()
      # p1.sym = env.x
  
      while True:
          while True:
              first_move = input(&quot;Do you want to make the first move? y/n :&quot;)
              if first_move.lower() == 'y':
                  first_player = Human(env, env.x)
                  second_player = p2
                  break
              else:
                  first_player = p1
                  second_player = Human(env, env.o)
                  break
          current_player = None
  
          while not env.game_over():
              # alternate between players
              # p1 always starts first
              if current_player == first_player:
                  current_player = second_player
              else:
                  current_player = first_player
              # draw the board before the user who wants to see it makes a move
  
              if current_player.ai == True:
                  current_player.play_step(env.get_state(), random=False)
              if current_player.ai == False:
                  current_player.play_step()
              env.draw_board()
          env.draw_board()
          play_again = input('Play again? y/n: ')
          env.reset_env()
          # if play_again.lower != 'y':
          #     break
  
  
  if __name__ == &quot;__main__&quot;:
      main()
  </code></pre>
  
Tags: <reinforcement-learning><q-learning><game-ai><combinatorial-games><tic-tac-toe>
Title: Why isn't my Q-Learning agent able to play tic-tac-toe?
UserDisplayName: SHA256man
ThreadText: # Why isn't my Q-Learning agent able to play tic-tac-toe?
  
  (Asked by: username_0 on 2019-01-16)
  
  I tried to build a Q-learning agent which you can play tic tac toe against after training.
  
  Unfortunately, the agent performs pretty poorly. He tries to win but does not try to make me 'not winning' which ends up in me beating up the agent no matter how many loops I gave him for training. I added a reward of 1 for winning the episode and it gets a reward of -0.1 when he tries to put his label on an non-empty square (after the attempt we have s = s'). I also start with an epsilon=1 which decreases in every loop to add some more randomness at the beginning because I witnessed that some (important in my opinion) states did not get updated. Since I spend some hours of debugging without noticeable progress I'd like to know what you think.
  
  PS: Don't care about some print statements and count variables. Those where for debugging.
  
  Code here or on [Github](https://github.com/DataHamster/q-learning-tic-tac-toe)
  
  ```
  import numpy as np
  import collections
  import time
  
  Gamma = 0.9
  Alpha = 0.2
  
  class Environment:
      def __init__(self):
          self.board = np.zeros((3, 3))
          self.x = -1  # player with an x
          self.o = 1  # player with an o
          self.winner = None
          self.ended = False
          self.actions = {0: (0, 0), 1: (0, 1), 2: (0, 2), 3: (1, 0), 4: (1, 1),
                          5: (1, 2), 6: (2, 0), 7: (2, 1), 8: (2, 2)}
  
      def reset_env(self):
          self.board = np.zeros((3, 3))
          self.winner = None
          self.ended = False
  
      def reward(self, sym):
          if not self.game_over():
              return 0
          if self.winner == sym:
              return 10
          else:
              return 0
  
      def get_state(self,):
          k = 0
          h = 0
          for i in range(3):
              for j in range(3):
                  if self.board[i, j] == 0:
                      v = 0
                  elif self.board[i, j] == self.x:
                      v = 1
                  elif self.board[i, j] == self.o:
                      v = 2
                  h += (3**k) * v
                  k += 1
          return h
  
          def random_action(self):
              return np.random.choice(self.actions.keys())
  
      def make_move(self, player, action):
          i, j = self.actions[action]
          if self.board[i, j] == 0:
              self.board[i, j] = player
  
      def game_over(self, force_recalculate=False):
          # returns true if game over (a player has won or it's a draw)
          # otherwise returns false
          # also sets 'winner' instance variable and 'ended' instance variable
          if not force_recalculate and self.ended:
              return self.ended
  
          # check rows
          for i in range(3):
              for player in (self.x, self.o):
                  if self.board[i].sum() == player*3:
                      self.winner = player
                      self.ended = True
                      return True
  
          # check columns
          for j in range(3):
              for player in (self.x, self.o):
                  if self.board[:, j].sum() == player*3:
                      self.winner = player
                      self.ended = True
                      return True
  
          # check diagonals
          for player in (self.x, self.o):
              # top-left -> bottom-right diagonal
              if self.board.trace() == player*3:
                  self.winner = player
                  self.ended = True
                  return True
              # top-right -> bottom-left diagonal
              if np.fliplr(self.board).trace() == player*3:
                  self.winner = player
                  self.ended = True
                  return True
  
          # check if draw
          if np.all((self.board == 0) == False):
              # winner stays None
              self.winner = None
              self.ended = True
              return True
  
          # game is not over
          self.winner = None
          return False
  
      def draw_board(self):
          for i in range(3):
              print("-------------")
              for j in range(3):
                  print("  ", end="")
                  if self.board[i, j] == self.x:
                      print("x ", end="")
                  elif self.board[i, j] == self.o:
                      print("o ", end="")
                  else:
                      print("  ", end="")
              print("")
          print("-------------")
  
  class Agent:
      def __init__(self, Environment, sym):
          self.q_table = collections.defaultdict(float)
          self.env = Environment
          self.epsylon = 1.0
          self.sym = sym
          self.ai = True
  
      def best_value_and_action(self, state):
          best_val, best_act = None, None
          for action in self.env.actions.keys():
              action_value = self.q_table[(state, action)]
              if best_val is None or best_val < action_value:
                  best_val = action_value
                  best_act = action
          return best_val, best_act
  
      def value_update(self, s, a, r, next_s):
          best_v, _ = self.best_value_and_action(next_s)
          new_val = r + Gamma * best_v
          old_val = self.q_table[(s, a)]
          self.q_table[(s, a)] = old_val * (1-Alpha) + new_val * Alpha
  
      def play_step(self, state, random=True):
          if random == False:
              epsylon = 0
          cap = np.random.rand()
          if cap > self.epsylon:
              _, action = self.best_value_and_action(state)
          else:
              action = np.random.choice(list(self.env.actions.keys()))
              self.epsylon *= 0.99998
          self.env.make_move(self.sym, action)
          new_state = self.env.get_state()
          if new_state == state and not self.env.ended:
              reward = -5
          else:
              reward = self.env.reward(self.sym)
          self.value_update(state, action, reward, new_state)
  
  class Human:
      def __init__(self, env, sym):
          self.sym = sym
          self.env = env
          self.ai = False
  
      def play_step(self):
          while True:
              move = int(input('enter position like: \n0|1|2\n------\n3|4|5\n------\n6|7|8'))
              if move in list(self.env.actions.keys()):
                  break
          self.env.make_move(self.sym, move)
  
  def main():
      env = Environment()
      p1 = Agent(env, env.x)
      p2 = Agent(env, env.o)
      draw = 1
      for t in range(1000005):
  
          current_player = None
          episode_length = 0
          while not env.game_over():
              # alternate between players
              # p1 always starts first
              if current_player == p1:
                  current_player = p2
              else:
                  current_player = p1
  
              # current player makes a move
              current_player.play_step(env.get_state())
  
          env.reset_env()
  
          if t % 1000 == 0:
              print(t)
              print(p1.q_table[(0, 0)])
              print(p1.q_table[(0, 1)])
              print(p1.q_table[(0, 2)])
              print(p1.q_table[(0, 3)])
              print(p1.q_table[(0, 4)])
              print(p1.q_table[(0, 5)])
              print(p1.q_table[(0, 6)])
              print(p1.q_table[(0, 7)])
              print(p1.q_table[(0, 8)])
              print(p1.epsylon)
  
      env.reset_env()
      # p1.sym = env.x
  
      while True:
          while True:
              first_move = input("Do you want to make the first move? y/n :")
              if first_move.lower() == 'y':
                  first_player = Human(env, env.x)
                  second_player = p2
                  break
              else:
                  first_player = p1
                  second_player = Human(env, env.o)
                  break
          current_player = None
  
          while not env.game_over():
              # alternate between players
              # p1 always starts first
              if current_player == first_player:
                  current_player = second_player
              else:
                  current_player = first_player
              # draw the board before the user who wants to see it makes a move
  
              if current_player.ai == True:
                  current_player.play_step(env.get_state(), random=False)
              if current_player.ai == False:
                  current_player.play_step()
              env.draw_board()
          env.draw_board()
          play_again = input('Play again? y/n: ')
          env.reset_env()
          # if play_again.lower != 'y':
          #     break
  
  if __name__ == "__main__":
      main()
  
  ```
  
  **Tags:** reinforcement-learning, q-learning, game-ai, combinatorial-games, tic-tac-toe
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-01-16. Score: 3 | Accepted answer
  
  The $Q$-learning rule that you have implemented updates $Q(S\_t, A\_t)$ estimates as follows, after executing an action $A\_t$ in a state $S\_t$, observing a reward $R\_t$, and reaching a state $S\_{t+1}$ as a result:
  
  $$Q(S\_t, A\_t) \gets (1 - \alpha) Q(S\_t, A\_t) + \alpha (R\_t + \gamma \max\_a Q(S\_{t+1}, a))$$
  
  The implementation seems to be correct for the traditional setting for which $Q$-learning is normally described; **single-agent MDPs**. The problem is that you have a multi-agent setting, in which $Q$-learning is not always directly applicable.
  
  Now, as far as I can see from a very quick glance at your code, it seems like you actually already have taken some important steps towards allowing it to work, and I think it should be quite close to almost working (at least for a simple game like Tic-Tac-Toe) already. Important things that you appear to already be doing correctly:
  
  * Self-play training against an opponent who is hopefully gradually improving, as opposed to training against a uniform-at-random agent or a fixed-strategy agent.
  * Add randomization during training to ensure sufficient diversity in generated experience.
  
  ---
  
  I think the **major issue that remains to be solved** is in **how you define the subsequent state $S\_{t+1}$ after making a move in a state $S\_t$**.
  
  The update target that the $Q$-learning update rule moves its $Q$-value estimates towards consists of two components:
  
  1. The observed immediate reward $R\_t$.
  2. The discounted predicted future returns $\gamma \max\_a Q(S\_{t+1}, a)$ for the greedy policy.
  
  The problem is that, in your implementation, $S\_{t+1}$ **is a state in which the opponent is allowed to make the next move $a$, rather than the RL agent**. This means that $\max\_a Q(S\_{t+1}, a)$ is an incredibly optimistic, naive, unrealistic estimate of future returns. In fact, $\min\_a Q(S\_{t+1}, a)$ would be a much more realistic estimate (against an optimally-playing opponent), because the opponent gets to pick the next action $a$.
  
  I think switching in $\min\_a Q(S\_{t+1}, a)$ rather than the $\max$ may have a good chance of working in this scenario, but I'm not 100% sure. It wouldn't be a "pretty" solution though, since you'd no longer be doing $Q$-learning, but something else altogether.
  
  The proper $Q$-learning update may work well if you only present states to agents in which they're actually allowed to make the next move in the update rule. Essentially, you'd be plugging $\max\_a Q(S\_{t + 2}, a)$ into the update rule, replacing $S\_{t+1}$ with $S\_{t+2}$. Well... that's what you'd be doing in most cases. The only exception to be aware of would be terminal states. If an agent makes a move that leads to a terminal state, you should make sure to also run an additional update for that agent with the terminal game state $S\_{t+1}$ (where $Q(S\_{t+1}, a)$ will always be $0$ for any action $a$ if $S\_{t+1}$ is terminal).
  
  For a very closely related question, where I essentially provided an answer in the same spirit, see: [How to see terminal reward in self-play reinforcement learning?](https://ai.stackexchange.com/q/6573/1641)
  
  > **Comments:**
  > **username_0**: Wow! That was an incredibly sophisticated answer! I guess that your idea is the best solution to my problem. I'd have to give it some more thought to figure out how to do that properly but thank you very much:). So would you say that Q-learning isn't that good for multi agent tasks in general and if so what would you prefer (A2C, Policy Gradient....)? Best Regards  
  > **username_1**: @Robin_at_Cantelli Those are all standard RL agents originally formulated for the standard single-agent MDP setting, they'd all have similar problems. All of these things (including $Q$-learning) *may* work if you treat the opponent as part of "the environment" (which is essentially also what I suggested in my answer, skipping some states means you treat those parts of the trajectory as being part of the environment's inherent dynamics), but you often need extra tricks to avoid "overfitting" to an imperfect player. See also: https://ai.stackexchange.com/q/7963/1641  
  > **username_1**: In addition to that, there's also a whole field of Multi-Agent Reinforcement Learning research with lots of different algorithms dedicated to multi-agent settings (also often variants of traditional RL algorithms, with some extra tricks)  
  > **username_0**: Ok I see. So it seems to be the best approach to use the kind of algorithm (DQN,QL,A2C and so on) which seems to be the best fit for your current problem an if you have the multi agent task on top you try to modify the the state similar to what you suggested. Good that I thought about trying to build an agent for the German game of scat in the future. There you have 3 agents...oh dear;) Thanks for the outstanding educational experience you provided!  
  > **username_1**: @Robin_at_Cantelli That's right! If the answer helped, you can [mark it as accepted](https://ai.stackexchange.com/help/someone-answers) such that it no longer shows up in the list of unanswered questions. Of course you can also wait until you got a chance to implement my suggestions and verify whether that really completely solves it, or if there is something else that I may have missed.  
  > **username_2**: Applying s_t+2 instead of s_t+1 is a brilliant idea. You saved my time! Thanks.  
  
  ---
  
  