김영진

게임 이론의 가정

• 모든 player는 합리적인 선택을 한다
• 모든 플레이어는 자신의 utility를 최대화 하기 위한 선택을 한다. 
• 모든 플레이어는 다른 플레이어가 합리적인 선택을 할 것 임을 알고 있다. 
• Dominant Action : 상대방이 어떤 Action을 하던지 내가 취할수있는 최고의 action

Game Theory의 수학적 표현 (N,A,u)

• N : 플레이어 수 , i 라는 index로 표현
• A : Action set 
  • $A_i$ : i player가 수행할 수 있는 action set
• u : utility function
  • $u_i(a)$ : 플레이어 i가 a 라는 액션을 선택했을때의 utility
  • 일반적으로 u는 N차원 벡터
     

Zero Sum Game 

• 모든 플레이어의 utility 합이 0인 게임 
• 나의 utility를 최대화 하기 위해서는 상대방의 utility를 최소화 해야한다. 

Nash Equlibrium

• $S_i$ : 플레이어 i가 취할 수 있는 action에 대한 확률 분포
• Strategy Profile S : N명의 플레이어들의 모든 $S_i$ 값을 모은 것 
  • S = ($S_1,S_2, \cdots , S_N$)
• support : 확률 분포가 있을때 확률이 0보다 큰부분 
• pure strategy : 모든 플레이어들이 항상 똑같은 전략을 사용, 시간에 따라 $S_i$가 달라지지 않음 
• mixed strategy : $S_i$를 따라서만 선택하는 것이 아니라 무작위성을 가짐 
• Best response : 나를 제외한 모든 player들의 전략이 주어졌을때 내가 선택할 수 있는 최선의 전략 
• Nash Equlibrium : 모든 Player들의 전략이 best response 일때
• minmax Strategy
  • 상대방이 상대방에게 가장 유리한 선택을 한다는 것을 안다고 가정 
  • 최솟값을 구함, 여기서 최솟값은 player1이 i번째 action을 취했을때 플레이어2가 최선의 액션을 취한 상황 
    • $V_i^1 = min{x_i^1 , \cdots , x_i^n}$
  • 각 행의 최솟값중 최대값이 되는 행을 선택하는 것이 maxmin strategy
    • $V^1 = max{V_i^1 , \cdots , V_n^1}$
  • utility 행렬이 player 1의 입장이기때문에 플레이어 2는 반대로 minmax strategy를 택함 
• value of the game : $V^1 = V^2 = V$ 인 V
• $V^1$ 과 $V^2$ 를 선택하는 두 플레이어의 전략 $(a_i,b_j)$ 를 Nash Equlibrium이라고 한다. 

MDP

• S : state 의 집합
• P : state transition function
  • state를 받아서 다른 state로 맵핑 해주는 함수
  • n개의 state 가 있으면 n*n matrix 가 됨
• memoryless random process
  • history를 알 필요 없이 현재 state만 알고 있으면 됨 
• markov property
  • 현재 state가 주어지면 과거의 일과 미래의 일이 독립이다. 

Markov Reward Process

• markov process에서 reward 개념을 추가한것 
• V(s)는 state S에서 시작할때 return 의 기댓값 

Value Function

• $V_{\pi}(S)$ : Policy &\pi&에서 State S가 주어졌을때 Value Function
• $Q_{\pi}(S,a)$ : Polivy $\pi$ 에서 State S 와 action a가 주어졌을 때 value Function

Bellman Equation

• Value Function을 구하기 위한 방정식
• $V_{\pi}(S) = E_{\pi} [R_{t+1} +\gamma V(S_{t+1}) | S_t = S]$

Optimal Value Function

• policy 마다 다른 value function이 주어지는 데 value function을 최대화 하는 policy를 적용했을때의 value function

Prediction & Control 

• Prediction : MDP가 주어지고 Policy가 주어졌을때 Value Function을 구하는 과정
• Control : MDP가 주어질때 optimal policy를 구하는 것 
• MDP가 주어진다는 것은 S,A,P,R,$\gamma$ 가 주어진것 
  • S : State
  • A : Action
  • P : State transition Probablity
  • R: Reward
  • $\gamma$ : 시간에 따른 감소상수

Policy Improvement

• Policy를 가지고 Value Function을 구하고 구한 Value Function을 바탕으로 Optimal Policy를 구하는 것 
• 시작할때 Random Policy를 이용해서 Value function을 도출하고, 도출된 Value function으로 Greedy Optimal policy를 구하고 다시 새로운 Policy로 Value function을 도출하는 과정을 반복하는 것 
• 반드시 optimal policy로 수렴한다. 

강화학습

• 장점 : 룰을 일일히 알려주기 힘든 상황에서 사용가능
• 단점 : 학습시간이 오래걸림
• 특징
  • 보상함수를 통해서 학습
  • 에이전트가 스스로 배워야한다.
  • 피드백이 늦게 올 수도 있다 (바둑은 결과를 끝내야 리워드가 온다)

강화학습 용어

• Policy : 에이전트가 어떤 행동을 할지 정해주는 함수
• Value function : state가 얼마나 좋은지 평가해주는 함수
• Model : 에이전트가 환경을 표현하는 모든 것 
• RL agent는 policy, value function, model로 구성
• RL model은 state, action, reward 로 구성 

policy

• Deterministic Policy : 어떤 상태에서 어떤 액션을 할지 정의한 것 
• Stocastic Policy : 어떤 상태에서 어떤 액션을 할지 확률적으로 정의한 것 

Value Function

• 미래의 보상에 대한 예측값
• $ V  _{\pi} (S) =  E_{\pi}[R_{t+1} +  \gamma R_{t+2}+ \gamma^2R_{t+3} + \cdots  | S_t = S ]$
• $V_{\pi}$ 는 $\pi$ 라는 policy일때 Value Function
• $E_{\pi}$ 는 기댓값
• $R_{t+1}$ 은 t+1 step에서 reward
• $S_t$ 는 t step에서 state

Model

• $P_{SS' }^a$ : t step에 S에 있고 a라는 action을 취했을때 S'으로 갈 확률 
• $R_S^a$ : S state에 있고 a라는 action을 취했을 때 얻는 reward

Exploration & Explotation

• Exploration : 탐험, 경험해보지 않은 state에 대해서 random action을 취하는 것 
• Explotation : 이미 알고 있는 정보를 이용해서 reward를 maximize 하는 것
• Exploraion을 통해서 새로운 것을 학습하고 Explotaion을 통해 reward를 maximize

Prediction & Control

• Prediction : Policy $\pi$ 가 주어졌을 때 가치함수 $V_{\pi}(S)$ 를 구하는 것 
• Control : reward를 최대로 하는 Policy를 구하는 것 

Local Search 

• path가 중요한게 아닌 goal에 도착하는게 중요한 문제를 해결할 때 많이 사용
  • 매 state에서 지금보다 더 나은 state로 가보자
• Hill Climbing Search 
  • 바로 주변만 볼 수 있는 짙은 안개속에서 산을 올라가는 것 비유
  • 가장 가파른 근처 노드로 가겠다
• 장점
  • 현재 state만 기억하기 때문에 메모리를 적게씀
  • 엄청나게 많은 state가 있을 때 효율적임
• 단점
  • Local Maxima에 빠질 수 있음
    • global maxima가 아닌 지역적 최대값으로 빠질수 있음 
• 단점을 보완하기 위해 등장한것이 annealing(담금질) search
  • 현재 상태보다 좋지는 않지만, 안좋은 move를 허락해줌
  • 시간이 지날수록 허락의 빈도수가 줄어들도록 설정 
  • 기본적으로 hill climbing을 따르지만 next node가 지금보다 가파르지 않더라도 가끔은 허락을 해주겠다는 것