Sample-based Learning Methods - 03. Week 3. Temporal Difference Learning Methods for Control

July 12, 2023

TD for Control

Sarsa: GPI with TD
- 학습목표
  - GPI (generalized policy iteration) 을 TD 와 함께 사용하여 개선된 정책을 찾는 법 설명하기.
  - Sarsa 제어 알고리즘 서술하기.
- GPI (generalized policy iteration) 에 대한 복기
  - GPI : policy iteration (policy evaluation $\to$ policy improvement)
  - GPI in Monte-carlo : 에피소드 진행 후 policy evaluation $\to$ policy improvement)
    - 몬테카를로의 경우 정책개선 이전에 완전한 정책평가를 하지 않는다. (에피소드마다 정책평가, 정책개선을 한다.)
- TD within GPI
  - GPI 에 TD 를 적용하기 위해서는 행동가치함수를 학습해야 한다.
    - 이전 섹션에서 TD 를 상태가치함수로 학습 (상태-상태)
      - 여기에서는 행동가치함수 (상태,행동-상태,행동) 의 값을 학습 : 이것을 Sarsa 예측이라고 함.
- Sarsa
  - Sarsa 의 약어는 업데이트에 쓰인 데이터 요소를 뜻함
    - $S_t$ : state
    - $A_t$ : action
    - $R_{t+1}$ : reward
    - $S_{t+1}$ : next state
    - $A_{t+1}$ : next action
  - Sarsa 의 업데이트식은 상태가치함수를 업데이트하는 TD 식과 유사
    - 단, Sarsa 는 상태-행동 쌍에 대한 행동가치함수 $Q(S_t,A_t)$ 에 대해 업데이트함.
  - 위의 그림은 정책평가에 대한 내용만 담겨 있다. (고정된 정책에 대한 행동가치함수의 학습)
    - 그러나 GPI 의 요소를 이용, 제어 알고리즘으로 변환할 수 있다. (예: $\varepsilon$-greedy)
      - Sarsa 제어 : TD 학습을 적용한 GPI 의 한 예
Sarsa in the Windy GridWorld
- 학습목표
  - Sarsa 제어 알고리즘이 예제 MDP 에서 작동하는 방식 이해하기.
  - 학습 알고리즘의 성능 분석 방법을 경험하기
- The Windy Gridworld
  - 문제의 정의
    - State : 각각 하나의 시작과 종료상태가 존재
      - 열에 따라 바람이 위쪽 방향으로 불어, 의도한 행동의 결과와 다른 상태전이가 일어남
        
        예를 들어 위 그림에서 에이전트는 왼쪽으로 움직이는게 아니라 좌측 상단 (대각선) 으로 움직임
      - 가장자리에 부딪힐 경우 아무 일도 일어나지 않음
    - Action : 에이전트는 4개의 방향으로 이동이 가능
    - Reward : 모든 상태에서 -1
      - 에이전트가 최대한 빨리 종료상태에 도달하도록 동기부여함
    - Discount factor $\gamma$ : 1 (에피소딕)
  - 문제에 Sarsa 를 적용하고 그 결과를 해석
    - Sarsa 설정값
      - 정책 : $\varepsilon$-greedy action selection
        
        $\varepsilon = 0.1$
      - $\alpha = 0.5$
      - 초기값 = 0
        
        optimistic initial values : 초기 탐색 장려
    - 결과 해석
      - 그래프 : 각 스텝 별로 몇 번의 에피소드를 끝냈는지를 의미
        
        위 결과는 각각 100번의 시행의 평균 값임
        
        첫 몇 번의 에피소드는 2000 스텝을 진행하고 종료됨
        
        그래프의 기울기는 점점 가파르게 상승하고 이는 짧은 스텝으로 에피소드를 종료함을 뜻함
        
        7000 스텝 즈음 기울기는 더이상 상승하지 않는다. (탐욕 정책의 개선 종료-최적화)
      - 몬테카를로 방법은 위 방식에 맞지 않다.
        
        많은 정책이 종료상태까지 도달하지 못함
        
        몬테카를로 방식은 에피소드가 종료되어야 학습을 시작함
        
        따라서 결정론적 정책은 함정에 빠지고, 좋은 정책을 배우지 못하게 됨
        
        예를 들어 초기 정책이 왼쪽으로 이동하는 것이라면 에피소드가 영원히 끝나지 않게 됨
      - Sarsa 는 에피소드를 진행하며 현재의 정책이 안좋은 정책이라는 것을 학습하고, 정책을 바꾸게 된다.

Off-policy TD Control : Q-learning

What is Q-learning?
- 학습목표
  - Q-learning 알고리즘 서술하기.
  - Q-learning 과 벨만 최적 방정식 (Bellman Optimality equations) 간 관계 설명하기.
- The Q-learning algorithm
  - Q 러닝은 1989년에 개발되었고, 강화학습 알고리즘 중 첫번째 메인 온라인 학습 알고리즘이다.
  - 위 그림은 Q-learning 알고리즘의 psuedo code 이다.
    - 에이전트는 상태에서 행동을 선택하고, 다음 상태와 보상을 관측한다.
    - 이후 업데이트를 진행하고 사이클이 반복된다.
    - 타 알고리즘과의 차이점은 업데이트 규칙에 있다.
  - 위 그림은 벨만방정식과 Sarsa, Q-learning 간의 수식 비교이다.
    - Sarsa : 벨만방정식의 행동가치 식과 유사
      - Sarsa 는 벨만방정식의 행동가치 식을 풀기 위한 샘플기반의 알고리즘이다.
      - Sarsa 는 샘플기반의 정책 반복 (policy iteration) (벨만 방정식 행동가치함수 사용)
    - Q-learning : 벨만최적방정식의 행동가치 식과 유사
      - Q-learning 또한 환경으로부터의 샘플을 이용해 벨만 방정식을 풀지만, 벨만 방정식 대신 벨만 최적 방정식을 사용한다.
      - 즉, $q_*$ 를 바로 학습함으로서, 정책평가와 정책개선 단계를 번갈아 가며 진행할 필요가 없게 된다.
      - Q-learning 은 샘플 기반의 가치 반복 (value iteration) (벨만 최적 방정식 행동가치함수 사용)
  - Q-learning 은 Value iteration 과 마찬가지로 최적가치함수에 수렴한다. (에이전트가 모든 상태-행동 쌍에 대해 지속적으로 탐색한다는 가정)
Q-learning in the Windy Grid World
- 학습목표
  - Q-learning 이 예제 MDP 에서 작동하는 방식 이해
  - 단일 MDP 에서 여러 학습 알고리즘의 성능을 비교하는 방식 경험
  - Q-learning 과 Sarsa 의 차이점 이해하기.
- The Windy Gridworld
  - Sarsa 와 Q-learning 간 비교 ($\alpha = 0.5$)
    - Q-learning 이 Sarsa 보다 뛰어난 결과를 보여준 이유를 명확히 설명할 수 없지만, 아마 update target 이 더 stable 했기 때문으로 추정함.
      - Sarsa 의 경우 탐색에 해당하는 샘플의 업데이트가 큰 영향을 줬을 수도 있음. (탐색적인 행동을 할 때마다 update target 이 변경될 수 있음)
      - Q-learning 의 경우 max 값을 이용해 업데이트 하기 때문에, 한 행동이 이전 행동보다 더 낫다는 것을 학습할 때에 update target 이 변경됨.
  - Sarsa 와 Q-learning 간 비교 (Salsa : $\alpha = 0.1$)
    - 더 나은 Sarsa 의 결과를 위한 파라미터의 변경
      - $\alpha = 0.1$
      - 더 많은 Time Steps 의 진행
    - Sarsa 와 Q-learning 모두 동일한 정책으로 수렴함
- 강화학습은 파라미터의 값에 따라 다른 결과물을 보여줌.
  - $\alpha$, $\varepsilon$, initial values, length of the experiments
How is Q-learning off-policy?
- 학습목표
  - Q-learning 이 importance sampling 없이 off-policy 로 동작할 수 있는 이유를 이해하기.
  - On-policy 기반과 Off-policy 기반 학습이 각각 제어 성능에 어떤 영향을 주는지 서술하기.
- On-policy 와 Off-policy 관점에서 Sarsa 와 Q-learning 비교
  - On-policy 와 Off-policy 복습
    - 에이전트는 목표정책(target policy) 의 예상 리턴값을 토대로 가치함수를 추측한다.
    - 에이전트는 행동정책(behavior policy) 에 따라 실제 행동한다.
    - 목표정책과 행동정책이 같다면, 에이전트가 On-policy 학습을 한다 고 한다.
    - 목표정책과 행동정책이 다르다면, 에이전트는 Off-policy 학습을 한다 고 한다.
  - Sarsa : On-policy algorithm
    - 에이전트가 다음에 수행할 작업의 값을 부트스트래핑 한다.
      - 다음 수행할 작업의 값은 행동정책 ($\pi$) 에 의해 샘플링한 값이다.
    - 즉 Sarsa 는 On-policy 학습이다.
  - Q-learning : Off-policy algorithm
    - 에이전트의 다음상태에 해당하는 행동값 중 가장 큰 값을 부트스트래핑한다.
      - 다음상태의 행동값 중 가장 큰 값은 탐욕정책(최적정책) ($\pi_* \noteq \pi$) 에 의해 샘플링된 값이다.
    - 즉 Q-learning 은 Off-policy 학습이다.
- Q-learning 의 Behavior policy 와 Target policy
  - 강화학습에서의 자연스러운 질문 : 목표정책(target policy) 과 행동정책(behavior policy)은 무엇인가?
    - Q-learning 에서의 Target policy : 현재 값에 대한 탐욕 정책
    - Q-learning 에서의 Behavior policy : 모든 상태-행동 쌍에 접근할 수 있는 어떠한 정책도 될 수 있음 (예: $\varepsilon$-greedy)
  - 위에서 볼 수 있듯 Target policy 와 Behavior policy 가 다르므로 Off-policy 라 할 수 있다.
- Q-learning with No importance sampling
  - Q-learning 이 importance sampling 이 필요없는 이유
    - 에이전트가 정해지지 않은 정책으로부터 행동값을 추정하고 있기 때문
      - importance sampling ratio 로 행동 선택의 차이를 수정할 필요가 없다.
  - 상태가치함수 추정의 예시
    - 행동가치함수는 주어진 상태에서 각 행동의 리턴값을 나타낸다.
    - 에이전트의 target policy 는 주어진 상태에서 각각의 행동을 할 확률을 나타낸다.
    - 즉 에이전트는 주어진 상태에서 target policy 를 따를 때 예상되는 리턴을 위 2개의 항목을 결합하여 나타낼 수 있다.
  - Q-learning 의 target policy - greedy policy
    - 가장 큰 리턴값을 가지는 행동을 선택. 즉, 다른 행동은 확률 0 을 가지게 됨.
    - 해당 상태에서의 리턴 예상값은 행동값의 최대 값과 동일하다.
- Q-learning 이 성능에 영향을 주는 경우
  - Q-learning 은 정책반복 (정책평가와 정책개선) 을 하지 않고 바로 최적값을 직접 학습한다.
  - 최적가치함수와 정책을 직접 학습하는 것은 효율적으로 보이나, 가끔 미묘한 경우가 존재한다.
    - 예 : $\varepsilon$-greedy 정책의 Q-learning 의 경우 Cliff walking 문제에서 Sarsa 보다 안좋은 결과를 보여준다.

Expected Sarsa

Expected Sarsa
- 학습목표
  - Expected Sarsa 알고리즘 설명
- 벨만방정식 (action-values) 과 Sarsa 알고리즘
  - 위 벨만방정식을 살펴보면, 해당 상태-행동 쌍의 온전한 값을 구하기 위해 상태전이에 의한 다음상태의 합계와 정책에 의한 행동에 대한 합계를 구하는 것을 알 수 있다.
  - Sarsa 의 업데이트 식의 경우 Error 를 구하는 부분에서 다음 상태의 값을 샘플링하여 계산하는데, 이 샘플링 데이터는 상태전이와 정책에 의한 행동 요소가 들어가 있다.
    - 이 때, 에이전트는 이미 정책을 알고 있으므로, 이 부분을 샘플링 데이터에 의지하지 않고 계산을 하면 어떻게 될까?
- Expected Sarsa 알고리즘
  - 명시적으로 다음 행동의 예측값을 계산하는 것이 Expected Sarsa 의 핵심 아이디어이다.
  - Expected Sarsa 또한 벨만 방정식 (action-values) 에 기반을 두고 있기에 업데이트식의 형식은 타 알고리즘과 유사하다.
    - 차이점은 TD error 값을 샘플링을 통한 부트스트래핑 값이 아닌 다음 행동의 예측값으로서 정책과 부트스트래핑 값을 이용해 계산을 해낸다는 점이다.
      - 이것의 의미는 매 타임스텝 마다 정책 하의 예측 값(부트스트래핑)을 계산해야 한다는 의미이다.
  - Expected Sarsa 는 Sarsa 에 비해 더 안정적인 update target 을 가지게 된다.
    - Sarsa 의 경우 샘플에 따라 잘못된 방향 (target) 으로 업데이트가 될 수 있다.
      - 물론 많은 업데이트를 통해 참 값으로 수렴하게 된다.
    - Expected Sarsa 의 경우 곧바로 참 값 (target) 으로 업데이트가 이루어진다.
      - 이는 분산이 작아지는 효과를 가져온다.
  - Expected Sarsa 의 단점은 컴퓨팅 리소스 부분이다.
    - 행동의 가지수가 늘어날 수록 계산 가격이 비싸진다. (특히 매 타임스텝마다 계산되는 부분이므로 더 부담스럽다.)
Expected Sarsa in the Cliff World
- 학습목표
  - Expected Sarsa 의 행동을 예시 MDP에서 설명
  - Expected Sarsa 와 Sarsa 의 경험적 비교
- Cliff Walking 환경에서의 Sarsa 와 Expected Sarsa 비교 ($\varepsilon = 0.1$, 100회 학습, 50000회 독립시행 평균결과)
  - Expected Sarsa 는 Sarsa 에 비해 더 큰 $\alpha$ 값을 사용할 수 있다.
    - 정책의 무작위성을 명시적 평균을 통해 해결
    - 이 문제에서의 상태이동은 결정론적이기에 다른 무작위성이 없다.
    - 즉 위 두 조건으로 Expected Sarsa 의 업데이트는 결정론적인 값이 된다.
  - Sarsa 의 업데이트의 경우 다음 행동에 크게 영향을 받게 된다.
- Cliff Walking 환경에서의 Sarsa 와 Expected Sarsa 비교 ($\varepsilon = 0.1$, 100000회 학습, 50000회 독립시행 평균결과)
  - Expected Sarsa 는 $\alpha$ 값에 영향 없이 같은 결과를 보여줌
    - 업데이트가 결정론적이기 때문
    - 위 경우 step size 는 얼마나 목표 값에 빠르게 수렴하는지에만 영향을 줌
  - Sarsa 의 경우 $\alpha$ 값에 큰 영향을 받음
    - $\alpha$ 값이 크면 수렴에 실패하며, $\alpha$ 값이 작으면 오랜 시간 학습 끝에 Expected Sarsa 와 거의 동일한 결과를 보여줌
Generality of Expected Sarsa
- Sarsa, Q-learning, Expected Sarsa 간 비교 (도입부)
  - Sarsa 와 Expected Sarsa 는 동일한 벨만 방정식으로부터 유도되었다는 점에서 유사성이 있음.
  - Q-learning 과 Expected Sarsa 간에는 어떠한 관계가 있을까?
- 학습목표
  - Expected Sarsa 가 importance sampling 없이 off-policy 학습을 할 수 있는 이유 설명
  - Expected Sarsa 가 Q-learning 의 일반화 버전인 이유
- Off-policy Expected Sarsa
  - (On-policy 의 경우를 가정) On-policy 의 경우에도 Expected Sarsa 는 실제 다음 선택된 행동 관련 업데이트를 하는 것이 아닌 정책 $\pi$ 에 관한 업데이트를 진행함
    - 즉, $\pi$ 가 behavior policy 와 같을 필요가 없다고 볼 수 있음.
    - 위의 관점은 Expected Sarsa 가 Q-learning 과 같이 importance sampling 없이 Off-policy 학습이 가능함을 보여줌.
- Greedy Expected Sarsa
  - 만약 학습할 target policy 가 탐욕정책이라면 어떻게 될까?
    - 이는 다음 상태에서 최대값을 이끌어내는 행동을 수행하는 것이고, Q-learning 과 동일한 방식이다.
    - 즉, Q-learning 은 Expected Sarsa 의 특별한 케이스이다.
Week 3 Summary
- TD control and Bellman equations
  - TD 제어는 벨만 방정식에 기반을 둔다.
    - Sarsa
      - 벨만 방정식의 샘플 기반 버전
      - $q_\pi$ 를 학습
      - On-policy 알고리즘 (현재 정책의 action value 를 학습)
    - Q-learning
      - 벨만 최적 방정식을 이용
      - $q_*$ 를 학습
      - Off-policy 알고리즘 (현재 정책과 무관하게 optimal action value 를 학습)
    - Expected Sarsa
      - Sarsa 와 동일한 벨만 방정식을 이용
      - 그래나 Sarsa 와 샘플링을 하는 방식이 다름
        
        다음 행동가치의 예측값 (Sum) 을 활용함.
      - On-policy, Off-policy 둘다 가능
        
        behavior policy 가 deterministic 하다면 On-policy 가 된다.
        
        behavior policy 가 탐욕정책이라면 Q-learning 과 동일한 알고리즘이 되어버린다. (Q-learning 은 Expected Sarsa 의 특이 케이스)
- Subtleties with off-policy control (Off-policy control 의 미묘함)
  - Online 학습에서 Q-learning 은 Sarsa 보다 값이 안좋게 나오는데, 이는 탐색정책의 랜덤성 때문이다.
  - Expected Sarsa 의 경우 Online 학습에서 Sarsa 와 동일한 결과를 보여주면서, 동시에 더 좋은 학습률을 보여준다.
    - 학습한 정책이 동일하다.
    - 다음 행동가치의 예측값으로 학습하기 때문에, behavior policy 에 학습의 영향을 받는 Sarsa 보다 더 안정적인 학습을 한다.
Chapter summary
- TD learning
  - 예측 : TD 방식은 예측 문제 해결을 위한 Monte Carlo 방법의 대안임.
  - 제어 : 두 경우 모두 제어 문제에 대한 확장은 동적 프로그래밍에서 추상화한 일반화된 정책 반복(GPI)의 아이디어를 통해 이루어짐
    - 근사 정책과 가치 함수가 둘 다 최적을 향해 움직이는 방향으로 상호 작용해야 한다는 아이디어임
    - 가치 함수를 구동하여 현재 정책의 수익을 정확하게 예측 (예측의 문제)
    - 현재 가치 함수와 관련하여 정책을 국지적으로 개선(예: e-greedy)하도록 유도 (정책개선)
- TD 제어 방법의 분류
  - 경험을 기반으로 하는 경우에서의 탐색 문제가 발생한다.
  - On-policy : Sarsa
  - Off-policy : Q-learning, Expected Sarsa
  - 이 외에 행위자 비평 방법 (Actor-Critic) 이 있는데 이러한 방법은 13장에서 다룸.
- TD learning 의 장점
  - 가장 널리 사용되는 강화학습 방법
    - 매우 단순
      - 최소한의 계산으로 환경과의 상호 작용에서 생성된 경험에 온라인으로 적용할 수 있음
      - 작은 컴퓨터 프로그램으로 구현할 수 있는 단일 방정식으로 거의 완벽하게 표현
    - 단순한 알고리즘을 확장하여 약간 더 복잡하고 훨씬 강력하게 만들 수 있음
      - 본질은 TD 의 것 그대로임.
        
        적은 계산으로 온라인경험 처리 가능
        
        TD 오류에 의해 구동됨
- 이 장에서 다룬 TD 학습법의 특징
  - 1 Step
  - Tabular
  - 모델이 없는 TD 방법
- 앞으로 배울 내용
  - n단계 형식(Monte Carlo 방법 관련)과 환경 모델을 포함하는 형식(계획 및 동적 프로그래밍 관련)으로 확장
  - 테이블(딥 러닝 및 인공 신경망 관련)이 아닌 다양한 형태의 함수 근사치로 확장
- 일반적인 방법으로서의 TD
  - 강화 학습의 문제 맥락에서 TD 방법에 대해 살펴보았지만 실제로 TD 방법은 이보다 더 일반적임
    - 동적 시스템에 대한 장기 예측을 학습하기 위한 일반적인 방법
    - 강화학습이 아닌 순수한 예측의 방법으로 분석
      - 재무 데이터, 수명, 선거 결과, 날씨 패턴, 동물 행동, 발전소에 대한 수요, 고객 구매 예측 등의 문제에도 쓰일 수 있음
  - 아직 TD 학습 방법의 잠재적 응용은 광범위하게 탐색되지 않음.