Optimality in Games

• What is optimal policy $\pi^i$ for ith player?
  • 만약 i 번째 플레이어를 제외한 다른 플레이어들의 policy를 고정시킨다면
  • Best response $\pi_*^i(\pi^{-i})$는 최적 해이다. 이 정책에 반해서,
  • Nash equilibrium은 $\pi_*^i(\pi^{-i})$, 모든 플레이어가 상대방에게 best response인 경우 모두가 best response이면 모든 플레이어가 전략을 바꿀 이유가 없다.

Single-Agent and Self-Play Reinforcement Learning

• Best response는 single-agent RL에 해답이다.
  • Other players는 environment의 한 부분이 된다.
  • Game이 MDP로 표현이 된다.
  • Best response는 MDP의 optimal oplicy이다.
• Nash equilibrium은 self-play RL의 부동점이다.
  • Experience는 agents 사이에 게임을 플레이함으로써 생겨난다.
  • 각 agent는 상대 플레이어에 대한 best response를 배우고
  • 한 플레이어의 policy가 다른 플레이어의 enviornment를 결정하고 모든 플레이어들은 서로 적응해가면서 Nash Equilibrium을 찾게 된다.
• Nash Equilibrium은 unique한가?
  • unique 하지 않는데, 어떤 조건을 만족하면 unique 하다
  • A two-player game ( alternating ) players
  • A zero sum game has equal and opposite rewards for black and white
    • $R^1+R^2 = 0$
  • A perfect information
    • Markov game is fully observed
  • 이 3개의 조건을 만족하면, Nash Equilibrium은 한 개 존재한다.

Minimax

• value function defines policy $\pi = [\pi^1, \pi^2 ]$가 주어졌을때의 기댓값
  • 1은 white, 2는 black 1입장에서 보는 value function
• minimax value function은
  • white는 최대값을 얻어야하고 black은 최소값을 얻으면 된다.
  • state로 부터 white, black이 각각의 최선을 다해야 한다.
  • minimax value function은 각 현재 스테이트로부터 최선을 다해서 플레이하면 누가 이길 것 인가?
  • $v_*(s) = max_{\pi^1} min_{\pi^2} v_\pi(s)$
• minimax policy는 $\pi^1, \pi^2$가 있어서 이 대로 플레이하면 minimax value를 만족하는 policy
• minimax value function은 unique 하고, minimax policy는 Nash equilibrium을 만족한다.

Value Function in Minimax Search

• Search tree grows expoentially
• 게임 끝까지 모두 search 하는 것은 impractical하다.
• value function approximator를 대신 쓴다.
• leaf nodes까지 도달 하면 value function값으로 minimax value를 쓴다.