Deep Counterfacutal Regret Minimization

Abstract

Counterfactual Regret Minimization(CFR)은 규모가 큰 불완전 정보 게임을 풀기위한 선도적인 프레임워크이다. cfr은 반복적으로 게임트리를 돌면서 equilibrium으로 수렴한다. 굉장히 큰 게임을 풀기위해서는 CFR 이전에 추상화 기법이 사용된다. 그렇게 추상화된 게임을 cfr로 풀고, 이는 다시 full game으로 맵핑된다. 이러한 과정(추상화)은 보통 수작업이고 어떤 분야에 특정적이기 때문에, 게임의 중요한 전략적인 뉘앙스를 놓칠 수 있다. 그리고 닭이 먼저냐 알이먼저냐의 문제가 있는데, 왜냐하면 좋은 추상화 기법을 판단하려면 그 게임의 equilibrium에 대한 지식이 필요하기 때문이다. 이번 논문에서는 Deep CFR을 소개한다. Deep CFR은 추상화가 필요없는 CFR의 한 종류로, 추상화 기법 대신에 full game에서 DNN으로 CFR의 행동을 근사한다. 우리는 Deep CFR이 원칙적이며 대형 포커 게임에서 강력한 성능을 달성한다는걸 보여준다. 이것은 대형 게임에서 테이블 형태가 아닌 CFR의 첫번째 성공 사례이다.

Introduction

불완전한 정보 게임은 부분적인 정보만으로 여러 에이전트 간의 전략적 상호작용을 모델링한다. 이들은 협상, 경매, 사이버 보안 등의 real-world 분야들에 적용 가능하다. 그런 게임들에서 우리는 어떠한 플레이어도 이 균형에서 벗어남으로써 얻는 이득이 없는 균형(equilibrium)의 근사를 찾으려고 한다.

이런 균형을 찾는 방법 중 불완전 정보 게임에서 가장 성공적인 알고리즘은 CFR이다. CFR은 two-player 제로섬 게임에서 내쉬균형으로 수렴하는 반복적인 알고리즘이다. 테이블 형태의 CFR은 최근 포커분야의 모든 마일스톤에 적용 돼었고, 지난 6년간 Annual Computer Poker Competition의 경쟁력있는 모든 봇들에 사용됐다. 매우 큰 규모의 불완전 정보 게임을 다루기 위해서 추상화가 사용되는데, 이는 비슷한 states들을 하나로 묶어서 동일하게 취급하므로써 사용된다. 단순화된 게임은 테이블 형태의 CFR을 통해서 대략적으로 풀어진다. 그러나, 강력한 추상화를 설계하는것은 광범위한 도메인 지식이 필요하고, 추상화 솔루션은 진정한 균형의 거친 근사치에 그칠 수 있다.

반면, 강화학습은 테이블 형태의 정책이 아닌 DNN을 활용한 함수 근사법을 통해 거대한 state spaces에 까지 성공적으로 확장 됐다. 이러한 접근법은 최근에 큰 규모의 MDP에서 전략을 설계하거나 perfect-information 제로섬 게임 부분에서 많은 성과를 거뒀다(알파고 등.) 중요하게, deep RL은 특정 게임에서 별 다른 도메인 지식 없이도 좋은 전략을 배울 수 있었다. 하지만 유명한 RL 알고리즘들은 정보 불완전 게임에서는 내쉬균형으로 수렴하지 않는다.

추상화와 테이블 형태의 CFR을 함께 사용하기 보다는, 이번 논문에서는 DNN과 함수 근사법을 사용해서 테이블 형태의 CFR의 행동을 full, unabstracted 게임에 근사하는 Deep CFR을 소개한다. 우리는 Deep CFR이 two player 제로섬 게임에서 $\epsilon$-Nash Equilibrium 으로 수렴하는걸 증명하고, 실증적으로 HULHP를 포함한 변형 포커들에서 성능을 평가한다. 우리는 Deep CFR이 함수 근사 알고리즘의 최고였던 NFSP의 성능을 뛰어넘고, domain specific 추상화 테크닉들과도 견줄만하단걸 보여준다.

Notation and Background

용어정리

정보 불완전 광범위한 형태(게임 트리) 게임에서는,

• 유한의 플레이어 set $\mathcal{P}$ 가 있다.
• 노드(히스토리) $h$는 한 플레이어만 아는 private 지식을 포함한 현재 상황에서의 모든 정보로 정의된다.
• $A(h)$는 노드 $h$에서 가능한 액션들이다.
• $P(h)$는 찬스 이거나, 현재의 노드에서 행동하는 특정한 플레이어이다.
• 액션 $a\in A(h)$가 $h$를 $h^\prime$로 만들면, 우리는 $h\cdot a=h^\prime$ 라고 적는다.
• $h\sqsubset h^\prime$: 액션의 시퀀스가 $h$를 $h^\prime$으로 만들때
• $H$는 모든 노드의 집합
• $Z\subseteq H$ 는 어떤 액션도 불가능한 터미널 노드
• 각각의 플레이어 $p\in \mathcal{P}$는 $Z$에서 payoff function $u_p$를 갖는다.

이 논문에서 우리는 다음과 같이 가정한다

• $\mathcal{P} = \{1,2\}$
• $u_1 = -u_2$
• payoff의 범위: $\triangle$

불완전 정보는 각각의 플레이어 $p\in \mathcal{P}$의 information sets(a.k.a infoset)으로 표현된다.플레이어 $p$의 어떠한 infoset $I$에 대해서, $I$에 포함된 모든 노드들 $h, h^\prime\in I$는 $p$에게 구별 불가능 하다. 더 나아가서, 모든 non-terminal node $h \in H$ 는 각각의 $p$에 대하여 오직 하나의 infoset에 종속된다. 우리는 $p$가 행동하는 모든 infoset의 세트를 $\mathcal{I}_{p}$로 표현한다. 우리는 $I$에 속한 노드를 prefix 로 가지는 모든 터미널 노드를 $Z_I$라고 부르고, 특정한 prefix를 $z[I]$라고 부른다. 우리는 게임이 perfect recall 이라고 가정하는데, 이는 만약 $h$ 와 $h^\prime$ 이 플레이어 $p$의 infoset을 공유하지 않으면, $h$로 부터 파생된 어떠한 노드도 $h^\prime$에서 파생된 노드들과 플레이어 $p$의 infoset을 공유하지 않는다는 말이다.

말이 좀 어려운데, 만약 $h$가 JB이고, $h^\prime$가 QB이면, 당연히 향후 노드들의 infoset도 다를 수 밖에 없다는 말인것 같음.

Strategy(혹은 Policy) $\sigma(I)$는 infoset $I$에서 플레이어 $p$의 액션에 대한 확률벡터이다. $p$에게 infoset $I$의 모든 states는 구별 불가능 하므로, 각각에 대한 전략들은 모두 동일해야한다. $I$에서 액션의 집합은 $A(I)$, 특정 액션 $a$의 확률은 $\sigma(I,a)$ 라고 쓴다. 플레이어 $p$가 행동하는 모든 infoset에서의 전략을 $\sigma_p$ 라고 정의한다. strategy profile $\sigma$는 각각의 플레이어의 전략의 튜플이다. 플레이어 $p$가 아닌 모든 플레이어의 전략은 $\sigma_{-p}$ 라고 표현된다. $u_p(\sigma_p, \sigma_{-p})$는 $p$가 $\sigma_p$로 플레이 하고 다른 플레이어들이 $\sigma_{-p}$로 플레이 했을때의 payoff 기댓값이다.

$\pi^\sigma(h)$ 는 reach 라고 부르는데, 이는 모든 플레이어가 $\sigma$로 플레이 했을때 h 에 도달할 확률이다. $\pi^\sigma_p(h)$는 이 확률에 대한 플레이어 p의 contribution이고, $\pi^{\sigma}_{-p}(h)$는 p가 아닌 모든 플레이어(chance 포함)의 contribution이다. 플레이어 p의 infoset $I$에 대하여, p는 I에 도달하기위해 액션을 고르지만, chance와 다른 모든 플레이어들은 $\sigma_{-p}$로 플레이 할때의 도달 확률은 $\pi^{\sigma}_{-p}(I)$ 라고 표기하고, 이는 I에 속한 모든 $h$에 대한 $\pi^{\sigma}_{-p}(h)$의 합과 같다.

$\sigma_{-p}$에 대한 Best Response 는 플레이어 p의 strategy $BR(\sigma_{-p})$ 인데, 이는 $u_p(BR(\sigma_{-p}), \sigma_{-p}) = \max_{\sigma^\prime}u_p(\sigma^\prime_p, \sigma_{-p})$ 를 만족한다. 내쉬균형 $\sigma^*$ 는 모두가 best response를 플레이하는 strategy profile이다

$\forall p, u_p(\sigma^*_p,\sigma^*_{-p}) = \max_{\sigma^\prime_p}u_p(\sigma^\prime_p,\sigma^*_{-p})$

two player 제로섬 게임에서 전략 $\sigma_p$의 Exploitability $e(\sigma_p)$ 는 내쉬균형 전략 $\sigma^*_p$의 $BR(\sigma^*_p)$에 대한 utility에 비해 자신의 BR을 상대로 얼마나 utility가 떨어졌는지이다. 수식으로 풀어 쓰자면 다음과 같다.

$e(\sigma_p) = u_p(\sigma^*_p, BR(\sigma^*_p)) - u_p(\sigma_p,BR(\sigma_p))$

우리는 total exploitability $\sum_{p\in P}e(\sigma_p)^3$을 측정한다.

Counterfactual Regret Minimization(CFR)

CFR은 어떤 유한 two-player 제로섬 게임에서든지 이론적인 수렴 범위가 $O(\frac{1}{\sqrt{T}})$인 내쉬 균형으로 수렴하는 반복적인 알고리즘이다. 실전에서 CFR은 훨씬 빠르게 수렴한다.

$\sigma^t$를 t 반복에서의 strategy profile 이라고 하자. 플레이어 $p=P(I)$의 Counterfactual Value $v^\sigma(I)$는 $p$가 $I$에 도달했을때, $I$의 counterfactual reach probability로 가중된 payoff 기댓값이다. 수식은 다음과 같다.

$v^\sigma(I) = \displaystyle\sum_{z\in Z_I}\pi^\sigma_{-p}(z[I])\pi^\sigma(z[I]\rightarrow z)u_p(z)$

그리고 $v^\sigma(I,a)$는 플레이어 p 가 infoset I 에서 100% 확률로 액션 a를 취할때의 Counterfacutal Value이다.

the instantaneous regret $r^t(I,a)$ 는 iteration t, $I$에서 a를 플레이 할때와 $\sigma$를 플레이 할때 $P(I)$의 counterfactual value의 차이이다.

$r^t(I,a) = v^{\sigma^t}(I,a) - v^{\sigma^t}(I)$

T번 반복 동안 Infoset $I$에서 액션 a 에 대한 Counterfactual regret은 다음과 같다.

$R^T(I,a) = \displaystyle\sum_{t=1}^Tr^t(I,a)$

추가적으로, $R^T_+(I,a) = \max\{R^T(I,a), 0\}$ 이고, $R^T(I) = \max_a\{R^T(I,a)\}$ 이다. 전체 게임에 대한 p 의 Total Regret은 $R^T_p = \max_{\sigma^\prime_p}\sum_{t=1}^T(u_p(\sigma^\prime_p,\sigma^t_{-p})-u_p(\sigma^t_p,\sigma^t_{-p}))$ 이다.

수식이 좀 복잡하고 내가 지금 머리가 잘 안돌아가는데, 정리하자면 $R^T(I)$는 T번의 반복동안 가장 regret이 큰 액션 a에 대한 regret의 합이고, $R^T_p$는 각각의 infoset I 마다 regret이 가장 큰 액션들만 모아놓은 strategy와 현재의 strategy사이의 difference의 합이다.

CFR은 각각의 infoset에 대하여 각 반복마다 regret minimization 알고리즘 중 하나를 사용해서 전략을 정한다. 일반적으로는 파라미터가 없고, 간단한 regret matching이 사용된다.

RM에서, 플레이어는 action들의 positive regret의 비중에 따라 행동을 고른다. 공식적으로는, 각 iteration t+1에서, 액션 $a\in A(I)$ 을 다음과 같은 확률로 고른다

$\sigma^{t+1}(I,a) = \frac{R^t_+(I,a)}{\sum_{a^\prime\in A(I)}R^t_+(I,a^\prime)}$

만약 $\sum_{a^\prime\in A(I)}R^t_+(I,a^\prime)=0$ 이면, 무작위 strategy가 선택된다. 일반적으로 각각의 액션에 같은 확률이 할당 되지만, 이 논문에서 우리는 1의 확률로 Counterfactual regret이 가장 높은 액션을 선택했는데, 이는 실험적으로 approximation error에 대처하는데 도움이 됐다.