*Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

Markov Decision Process을 지난 강의에서 배웠던 내용으로 설명하면, 강화학습을 위해 환경을 완전하게 알고 있는 것을 의미한다. 즉 full observable해야 한다. 이러한 이유로 RL의 거의 모든 문제는 MDP로 설계가 되어 있고, MDP하지 않다면 MDP하도록 조건을 더 추가시켜줘야 한다.

Markov Property

이전 강의에서 잠시 다뤘던 내용이다. "Markov하다" 라는 것은 다음 상태는 과거 상태에는 독립적이고 현재 상태에만 종속을 한다는 것이다. 즉 다음과 같다.

예시로 설명하면 다음과 같다. 현재 내가 장기(체스)를 두고 있다고 하자. 그러면 지금 현재 기물들이 어떻게 놓여져 있는지가 다음 수를 두는 것에 영향을 줄 뿐, 이전에 어떻게 움직였는지는 전혀 다음 수에 도움이 되지 않는다.

State Transition Matrix

Markov를 설명하기 위해 도움이 되는 정의 중 하나이다. state transition probability는 Markov한 state s에서 다음 상태 s'으로 이동할 확률을 뜻하고, Matrix는 이러한 확률을 행렬꼴로 모아둔 것이다.

Markov Process

앞으로 다룰 Markov 대한 성질들의 가장 기본이 되는 과정이다. memoryless random process라고 하는데, 이는 Markov의 특징을 말하는 것이다. Markov Process는 <S,P>로 정의되고, S는 state들의 집합, P는 state transition probability matrix이다. 다음은 아기가 잠에 드는 과정을 도식화한 것이다.

상태천이행렬이며, 빈 공간은 0이라 생각한다.

여기서 각 행동은 다 타원형으로 표시되어 있고, '잔다' 라는 상태만 네모로 표시되어 있는데 이는 terminate state, 종료 상태를 의미한다. 각 행동으로 이동하는 화살표에 확률이 써져 있는데, 아직은 모든 상태는 확률에 의해서만 바뀐다. 즉, '눕는다.' 라는 상태에서는 70% 확률로 논다. 라는 상태로 이동하고, 30%으로 확률로 잠에 들기 시작하는 상태로 이동하는 것이다.

상태를 이동하는 상황이 여러가지 있는데 이들을 episodes라고 부른다.

Markov Reward Process

Markov Process에 Reward function이 추가된 개념으로 <S,P,R,r>와 같으며 R은 reward function으로 Rs=E[Rt+1|St=s]이고, r 은 감쇠인자로써, 0과 1 사이의 값을 가진다. 이 단계에서 새로 정의되는 개념들이 있어 이를 정리하고 진행한다.

Reward가 추가 되었다.

Return

return Gt는 t 시간이 지난 뒤에 얻은 총 보상을 의미한다. 

  • Why discount? 감쇠인자를 사용하는 이유는 무엇일까?
    • 수학적으로 편리하다. 감쇠 인자를 0과 1 사이의 값으로 설정을 했기 때문에 return 값이 무한히 커지는 것을 막을 수 있다. 즉 bounded하게 만들 수 있다.
    • 사람이 선호하기 때문이다.
      • 만약 누군가 당신에게 지금 커피를 사줄지? 아님 10달 뒤에 커피를 사줄지 물어볼 수 있다.
        • 대부분 지금 사달라고 할 것이다.
    • 불확실성을 표현하기 위해서
      • 위의 예시로 생각하보면 지금 사달라고 선택을 하는 이유가 10달 뒤에 진짜 커피를 사줄지는 불확실했기 때문일 것이다.

Value Function

value function은 현재 상태 s로 부터 시작했을 때 return의 기댓값을 의미한다.

 

지금까지 예시에서 감쇠인자 값을 0이라 가정했을 때, 다음과 같이 value function 값이 구해진다.

지금은 state들이 단순해서 충분히 손으로도 계산을 할 수 있지만 더 많은 state들이 복잡하게 연결된다면 손으로 하는 것은 어렵게 될 것이다. 따라서 이를 위해 Bellman Equation이라는 것을 사용한다.

Bellman Equation

value function을 다음과 같이 표현할 수 있다.

Bellman Equation으로 value function을 그림으로 표현하면 다음과 같다. 현재 상태의 value function은 현재 보상을 받은 뒤(Rs)에 다음 상태들의 value function 합(sigma Pss'v(s'))에 감쇠 인자를 곱한 값을 얻는다는 것이다.

 따라서 이와 같이 value function으로만 구성된 식을 matrix form으로 변환한다면 역행렬을 통해서 한번에 구할 수 있게 된다.

하지만 이 연산은 O(n^3)에 해당하는 복잡도를 가지고 있다. 따라서 작은 MRP에서만 계산이 가능하고, 큰 경우는 DP, Monte-Carlo 방법등으로 구하게 된다.

Markov Decision Process

Markov Reward Process에서 action이 추가된 단계이다. <S,A,P,R,r>와 같이 정의 하며 A는 action들의 집합을 의미한다.

또한 action이 추가되었기 때문에 상태천이행렬 P와, reward function R에 a에 관한 식이 들어가게 되었다. 따라서 슬라이드에서 소개한 내용에 action을 추가하면 다음과 같다.

그리고 Action이 생김에 따라서 몇 가지 용어를 정의해야 한다.

Policy

정책 π 는 현재 주어진 상태에서 action a를 수행할 분포를 의미한다.

따라서 정책은 agent 행동을 정의한다고 할 수 있다. 그리고 이 정책을 이용해서 상태천이행렬 P와 reward function R을 다음과 같이 다시 정의할 수 있다.

 

Value Function

  • state-value function

state value function은 현재 상태 s가 주어졌고, 정책을 따른다고 했을 때 얻을 수 있는 return의 기댓값을 의미한다.

  • action-value function

action value function은 현재 상태가 s이고, action a를 한다. 그리고 정책을 따른다고 했을 때, 얻을 수 있는 return의 기댓값을 의미한다.

 

Bellman Expectation Equation

위에서 정의했던 state value function과 action value function을 Bellman equation을 사용하기 위해서 Immediate reward와 future reward 형태로 분해할 수 있게 된다.

하지만 위 식으로는 실제로 구현을 하는 것이 힘들기 때문에 직접 구현을 위해 조금 더 명백한 형태로 변형이 필요하게 됩니다.

 위 그림에서 흰색 원은 state를 의미하고, 검은색 원은 action을 의미합니다. 위 그림을 해석해 보면 현재 상태 s에서 가능한 action들은 2개가 있는 것입니다.(실제로는 더 많은 검은색 점이 있을 수 있습니다.) 그러면 agent가 선택한 당시의 정책에 따라 action을 할 확률이 정해질 것이고, 그 때마다 action-value function을 구할 수 있게 됩니다. 

 따라서 위 그림으로 보아 우리는 현재 state s에서의 state value function을 구하기 위해서 각 action을 할 확률(정책)과 그 action에서 발생하는 value state function을 곱한 것들의 합으로 표현을 할 수 있게 됩니다.

즉 다음과 같이 식을 얻을 수 있습니다.

하지만 아직 이 형태로는 현재 state value function과 다음 state value function과의 관계를 알 수 없습니다. 그러므로 action value function에 대해서 식을 전개해보도록 하겠습니다.

state s에서 action a를 했을 때의 그 action에 대한 value는 두 가지로 나뉘게 됩니다. state s에서 action a를 했을 때의 reward와 그 다음 state의 value function입니다. 그런데 이 중 다음 state value function은 다음 시점의 value function이므로 감쇠 인자를 적용시켜줘야 합니다. 또한 상태가 변한 것이므로 상태 전이 확률도 적용시켜줘야 합니다. 따라서 다음과 같이 식을 구성할 수 있습니다.

따라서 위 두 내용을 모두 한 번에 합치면 다음과 같이 됩니다.

지금까지 state value function을 설명하기 위해 전개를 한 것처럼 이를 action value function을 설명하기 위해 전개를 진행하면 다음과 같이 됨을 알 수 있습니다.

이제 식을 state, action value function 하나씩으로만 표현을 할 수 있기 때문에 이전에 matrix form으로 변경해서 구했떤 것처럼 구할 수 있게 된다.

Bellman Optimal Equation

강화학습은 기본적으로 최대의 보상을 얻는 정책을 찾는 것을 목표로 하고 있기 때문에 얻을 수 있는 기댓값보다는 최대 보상을 얻을 수 있는 것이 더 중요합니다. 따라서 앞서 정의했던 value function들을 다음과 같이 정의할 수 있습니다.

위의 식으로 optimal한 value function을 구할 수 있다면 주어진 state에서 value가 가장 높은 action을 선택할 수 있고, 이를 통해서 optimal한 정책을 구할 수 있게 됩니다. optimal한 값을 항상 얻도록 만들어야 하므로 다음과 같이 정책을 수식을 적을 수 있습니다.

앞서 Expectation Equation에서 진행했던 것처럼 Optimal도 진행을 할 수 있고 다음과 같이 얻을 수 있다.

하지만 Bellman Optimality Equation은 max 연산때문에 non-linear하다. 그렇기 때문에 일반화된 해법을 제공할 수는 없고, 이를 위한 여러가지 다른 방법들을 제시한다.

  • Value Iteration
  • Policy Iteration
  • Q-learning
  • Sarsa

 

*Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

 

 

강화학습은 여러 분야에서 사용가능하다. 컴퓨터 과학, 공학, 수학, 경제학 등 여러 분야에서 사용 가능하다.

  • 머신러닝은 지도 학습, 비지도 학습, 강화 학습 세 분야로 나눌 수 있는데, 강화 학습에 대해 자세히 알아보도록 한다.

  • 강화학습이 다른 머신러닝 분야들과 다른점은 무엇일까?

    • supervisor가 존재 하지 않는다.(y 값이 존재하지 않는다.) 대신 reward라는 값이 존재한다.
    • Feedback을 바로 받는 것이 아니라 일련의 행동들이 모두 마친 뒤에 나타난다.
    • 내가 이전에 한 행동에 따라 결과가 바뀌게 된다. 즉 시점에 따라 행동이 다르다.
    • agent의 행동에 따라 얻는 데이터가 달라지게 된다. (agent는 뒤에 다시 소개한다.)
  • 강의에서 다음과 같은 예시들을 소개하고 있다.

    • Fly stunt manoeuvres in a helicopter(자율주행)
    • Defeat the world champion at Backgammon(유럽의 보드게임)
    • Manage an investment portfolio(주식)
    • Control a power station(발전소 관리)
    • Make a humanoid robot walk(로봇이 걷도록 하는것)
    • Play many different Atari games better than humans(알파고(Atari 게임))
  • Reward (Rt)

    • scalar 피드백 값, 얼마나 agent가 t 단계에서 잘 수행했는지를 나타낸다.
    • agent의 임무는 누적 보상을 최대화 하는 것.
    • 강화 학습은 reward hypothesis에 기반을 두고 있다.
      • reward hypothesis?
        • 기대 누적 보상을 최대화하는 것이 agent의 목표이다.
  • Sequential Decision Making

    • Goal : 총 reward를 최대화 하는 행동을 고르는 것.
    • 행동은 긴 기간 동안 연속적으로 발생하며 보상은 이 행동들이 마친 뒤에 얻게 된다.
    • 이로써 나중에 더 큰 보상을 얻을 수 있다면 지금 당장은 적은 보상을 선택하거나 손해를 볼 수도 있음을 의미한다.

Agent and Environment

  • agent
    • environment의 observation, reward를 받아서 agent가 action을 수행한다.
  • Environment
    • agent의 action을 받아서 바뀐 observation, reward를 agent에 전달해준다.

즉 agent는 사람, envionment는 지구로써 사람이 어떤 행위를 취하면 지구에 영향을 주게 되고 지구의 환경에 변하며 이는 다시 사람에게 영향을 주게 된다.(지구 온난화?)

History and State

  • history는 observation, actions, rewards를 일련적으로 표현한 것.

  • state는 다음에 어떤 것을 해야 하는지 결정에 도움을 주는 정보, 이 것은 history에 특정한 함수를 취함으로써 얻는다.

Environment state and Agent State

agent, environment가 각각 가지고 있는 상태, 정의상으로는 agent state는 알고 있지만 envionment state는 모른다.( ex) 사람은 자신의 정보를 바탕으로 행동을 하지만, 그렇다고 지구의 환경이 어떻게 변할지는 예측할 수 없다.(또는 매우 힘들다)

Markov state(information state)

'Markov하다' 라는 정의로 미래는 과거에 어떤 상태였는지는 관계 없이 현재 상태만이 영향을 준다는 것이다. 다음 강의에서 Markov에 대해서 자세히 설명하기 때문에 이번엔 정의만 보고 넘어간다.

  • Full observability : agent가 agent state, environment state를 모두 아는 것, 이러한 경우에 Markov decision Process라고 부르며 다음 강의에서 자세히 다룬다.

RL's major components

  • Policy
    • agent의 행동을 의미한다. 어떤 현재 상태에 있을 때 어떠한 행동을 할지를 나타낸다.
    • 결정론적 정책
      • 상태 s에 도달하면 항상 a라는 행동을 한다.
    • 통계학적 정책
      • 상태 s에 있을 때 일정한 확률에 따라 특정한 행동 a를 한다.
  • Value Function
    • 미래 reward의 예측을 하는데 사용한다.
    • 이 값으로 상태가 좋은지/나쁜지 판단할 수 있다.
  • Model
    • 환경에 다음에 어떠한 것을 할 지 예측하는 것
    • 즉 다음에 어떤 상태가 발생되고, reward가 발생하는지 알려준다.

Categorizing RL agent

  • Value Based
    • Value Function
  • Policy Based
    • Policy
  • Actor Critic
    • Policy
    • Value Function
  • Model Free
    • Policy and Value Function
  • Model Based
    • Policy and Value Function
    • Model

나중에 더 자세히 설명하도록 한다.

Learning and Planning

  • Reinforcement Learning
    • 환경은 초기에 알려져 있지 않다.
    • agent는 환경과 상호작용한다.
    • agent는 정책을 발전시킨다.
  • Planning
    • 환경의 모델을 알고 있다.
    • agent는 그 모델에서 계산을 수행한다.
    • agent는 정책을 발전 시킨다.

Exploration and Exploitation

  • Exploration(탐험)
    • 탐험은 전체 공간을 골고루 찾아보는 전략이며 항상 같은 방향으로 진행하지 않는다.
  • Exploitation(탐사)
    • 탐사는 특정한 곳 주위를 집중적으로 찾아보는 전략으로 보상이 최대화 되는 방향으로만 진행한다.
  • 이들은 trade-off 관계에 있으며, 탐험은 시간이 너무 오래 걸리고, 탐사는 지역 최적해에 머무는 문제가 발생한다.

https://www.youtube.com/watch?v=2pWv7GOvuf0&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ

 

+ Recent posts