Sample-based Learning Methods - 04. Week 4. Planning, Learning & Acting

관련 자료 (RLbook Pages 159-166)

• Planning and Learning with Tabular Methods : 개요
  • 이 장에서는 동적 프로그래밍과 휴리스틱 탐색과 같이 환경모델이 필요한 강화학습 방법과, 몬테카를로와 시간차 학습과 같이 환경모델 없이 사용할 수 있는 강화학습 방법에 대한 통합된 관점을 개발한다.
  • 이러한 방법들은 각각 모델기반(model-based) 과 모델프리(model-free) 강화학습 방법으로 불린다.
  • 모델기반(model-based) 방법은 주로 계획(planning)에 의존하며, 모델프리(model-free) 방법은 주로 학습(learning)에 의존한다.
  • 이 두가지 방법 사이에는 실제로 차이가 있지만, 큰 유사점도 있다.
    • 특히, 두 가지 방법 모두 가치함수를 계산하는 것이 핵심임.
    • 또한 모든 방법들은 미래 이벤트를 예측하고 backed-up value 를 계산하며 이를 근사 가치함수의 업데이트 대상으로 사용한다.
  • 이전 장에서 몬테카를로 학습과 시간차 학습을 서로 다른 대안으로 소개한 후, n-step 방법으로 통합하는 방법을 보여줌.
  • 이 장에서는 모델기반 방법과 모델프리 방법의 통합이며, 우선 이들을 구분하여 설명한 후 서로 어떻게 조합될 수 있는지를 탐구한다.
• Models and Planning
  • 모델 (models) 에 대해서
    • 환경의 모델 : 에이전트가 에이전트의 행동에 환경이 어떻게 응답할 것인지 예측하는 데 사용할 수 있는 것
      • 특정 상태와 행동이 주어지면, 모델은 결과적인 다음 상태와 다음 보상에 대한 예측을 생성한다.
      • 즉, 에이전트가 환경과 상호작용하여 얻은 경험을 바탕으로 환경의 동작을 예측하는 수단
    • 분포 모델 (distribution models)
      • 모델이 확률적인 경우, 가능한 여러 다음 상태와 다음 보상들이 각각 발생할 확률과 함께 존재함
      • 몇몇 모델들은 모등 가능성과 그 확률에 대한 설명을 생성하며, 이러한 모델들을 분포 모델이라고 한다.
      • 예를 들어, 주사위 12개의 합을 모델링할 때 분포모델은 모든 가능한 합과 그들이 발생할 확률을 생성한다.
      • 동적 프로그래밍에서 가정하는 모델의 종류인 MDP 의 역학 $p(s’,r | s,a)$ 는 분포모델이다.
    • 샘플 모델 (sample models)
      • 어떤 모델들은 확률에 따라 샘플링된 하나의 가능성만 생성하며, 이러한 모델을 샘플 모델이라고 한다.
      • 예를 들어, 주사위 12개의 합을 모델링할 때 샘플 모델은 이 확률 분포에 따라 샘플링된 개별 합을 생성한다.
      • Chapter 5 의 블랙잭 예시에서 사용되는 모델은 샘플 모델이다.
    • 분포 모델과 샘플 모델간의 비교
      • 분포 모델은 항상 샘플을 생성할 수 있어, 샘플 모델보다 강력하다.
      • 그러나 많은 경우 샘플 모델을 얻는 것이 분포 모델을 얻는 것 보다 훨씬 쉽다.
        • 주사위 12개의 경우가 간단한 예시가 될 수 있는데, 주사위를 굴린 결과를 시뮬레이션하고 합을 반환하는 컴퓨터 프로그램은 쉽게 작성할 수 있지만, 모든 가능한 합과 그들의 확률을 찾는 것은 어렵고 오류가 발생할 수 있다.
  • 모델의 활용
    • 모델은 경험을 모방하거나 시뮬레이션 하는 데 사용될 수 있다.
    • 시작 상태와 행동이 주어지면, 샘플 모델은 가능한 전이를 생성하고, 분포 모델은 그들의 확률에 따라 가중치가 주어진 모든 가능한 전이를 생성한다.
    • 시작 상태와 정책이 주어지면, 샘플 모델은 전체 에피소드를 생성하고, 분포 모델은 모든 가능한 에피소드와 그들의 확률을 생성한다.
    • 두 경우 모두, 모델은 환경을 시뮬레이션하고 모의 경험을 생성하는데 사용된다고 말한다.
  • 계획 (planning) 에 대해서
    • Planning 이라는 용어는 다른 분야에서 여러 가지 방식으로 사용됨.
      • 강화학습에서는 모델을 입력으로 받아 환경과 상호작용하기 위한 정책을 생성하거나 개선하는 계산 과정을 가리키는 데 사용한다.
        • 즉, 모델을 사용하여 최적의 정책을 찾는 과정

      

    • 상태-공간 계획 (State-space planning)
      • 최적 정책 또는 목표로의 최적 경로를 찾기 위해 상태 공간을 탐색하는 것
      • 행동은 상태에서 상태로의 전이를 야기하며, 가치 함수는 상태 위에서 계산됨
      • 강화학습에서 일반적으로 많이 사용되는 계획 방식으로, 주어진 상태에 가능한 모든 행동을 시뮬레이션하고 그에 따른 예상 보상을 계산하여 좋은 행동을 선택하는 것을 반복
        • 상태 공간이 작을 때 효과적, 모델 기반 강화학습 알고리즘 중 일반적으로 사용되는 것
    • 계획-공간 계획 (Plan-space planning)
      • 최적 정책 또는 목표로의 최적 경로를 찾기 위해 계획 공간을 탐색하는 것
      • 연산자들은 한 계획을 다른 계획으로 변환하며, 가치함수 (있는 경우) 는 계획 공간 위에 정의됨
      • 계획-공간 계획에는 진화적 방법과 부분순서계획 (partial-order planning) 이 포함됨.
        • 이는 계획의 단계별 순서가 완전히 결정되지 않은 인공지능에서의 일반적인 계획 방법임
        • 계획 공간 방법은 강화학습의 초점인 확률적 순차 결정 문제에 효율적으로 적용하기 어렵기 때문에, 이에 대해 더 이상 고려하지 않음.
      • 에이전트가 가능한 다양한 계획들을 생성하고 평가함
        • 위 방식으로 계획을 다른 계획으로 변환하거나 합성하여 최적의 전략을 도출
        • 계획들 사이의 관계를 탐색하고 변환하는 과정을 거쳐 최적의 계획을 찾는데 사용
          • 계획들의 집합과 관계를 모델링하고 분석하는 것이 필요하기 때문에 복잡한 문제에 유용하게 적용
    • 모든 상태-공간 계획 방법에 대한 통합된 관점
      • 상태-공간 계획 방법은 공통된 구조를 가지고 있음
        • 모든 상태-공간 계획 방법은 정책 개선을 위한 핵심 중간단계로 가치함수를 계산하는 것을 포함한다.
        • 이들은 가치 함수를 시뮬레이션된 경험에 적용하는 업데이트 또는 백업 연산으로 계산한다.

      

      • 동적 계획법의 예
        • 상태 공간을 훑으며 각 상태에서 가능한 전이의 분포를 생성
        • 각 분포는 업데이트 값 (업데이트 대상) 을 계산하는 데 사용되며, 상태의 추정값이 업데이트됨
      • 다양한 다른 상태-공간 계획 방법들 또한 이러한 구조에 맞으며, 개별적인 방법들은 업데이트 종류, 수행 순서, 얼마나 오래 업데이트 대상을 유지하는지 정도의 차이만 존재
    • 학습(learning) 과 계획 (planning) 방법
      • 두 방법의 핵심은 백업 업데이트 연산에 의한 가치 함수의 추정임
      • 차이점은 계획은 모델에서 생성된 시뮬레이션 경험을 사용하는 반면, 학습 방법은 환경에서 생성된 실제 경험을 사용한다는 것임
        • 이 차이는 성능 평가 방법과 경험 생성 유연성 등 다른 여러 가지 차이를 유발
      • 그러나 위의 공통된 구조는 계획과 학습 사이에서 많은 아이디어와 알고리즘을 상호 전달할 수 있음을 의미함
        • 특히 많은 경우 학습 알고리즘은 계획 방식의 핵심 업데이트 단계를 대체하는 데 사용될 수 있음
          • 학습 방법은 경험만을 입력으로 필요로 하며, 많은 경우 실제 경험과 똑같이 시뮬레이션 경험에도 적용할 수 있음.
          • One-step tabular Q-learning 과 샘플 모델(Sample model) 로부터의 무작위 샘플을 기반으로 한 계획 방법의 psuedo code

          

          • 위 방법은 ramdom-sample one-step tabular Q-planning 이라 한다.
          • One-step tabular Q-learning 이 실 환경에서 최적 정책으로 수렴하는 것과 동일 조건으로 최적 정책에 수렴을 보장한다.
            • Step 1 에서 각 상태-행동 쌍이 무한히 선택
            • 시간이 지남에 따라 $\alpha$ 가 적절하게 감소
    • 작고 점진적인 단계로 계획을 수행
      • 계획과 학습 방법의 통합적 관점 이외에도, 작고 점진적인 단계로 계획을 수행하는 것은 장점이다.
      • 계획은 언제든 중단되거나 방향을 바꿀 수 있으며, 거의 낭비되지 않은 계산으로 이루어질 수 있음.
        • 이는 계획과 행동, 그리고 모델의 학습을 효율적으로 혼합하기 위한 핵심 요건임
      • 매우 작은 단계로 계획을 수행하는 것은 순수한 계획 문제에서도 가장 효율적인 접근방법일 수 있으며, 만약 문제가 정확하게 해결될 수 없을 정도로 크다면 특히 그러함.

• Dyna: Integrated Planning, Acting, and Learning

  • 개요
    • 온라인으로 계획을 수행할 때 환경과 상호작용하면서 흥미로운 문제들이 발생함
      • 상호작용으로 얻은 새로운 정보는 모델을 변경하고, 이로 인해 계획과 상호작용할 수 있다.
      • 현재 고려 중이거나 가까운 장래에 예상되는 상태 또는 결정에 대해 어떤 식으로든 계획 프로세스를 사용자 지정하는 것이 바람직할 수 있다.
      • 만약 의사결정과 모델학습이 모두 계산량이 많은 과정이라면, 사용 가능한 계산 자원을 이들 간에 분배해야 할 수도 있음.

  • Dyna-Q 의 구조

    

    • Dyna-Q 개요
      • 온라인 계획 에이전트에 필요한 주요 기능들을 통합한 간단한 구조
      • 간결하게 기능 구성
      • 각 기능을 달성하는 다른 대안적인 방법과, 이들 간의 균형점은 다음 섹션에서 다룸
    • 직접적 방법과 간접적 방법
      • 계획 에이전트 내에서 실제 경험은 적어도 두 가지 역할을 할 수 있음
        • 모델 학습 : 모델을 개선하기 위해 사용 (실제 환경과 더 정확하게 일치하도록 만드는 역할)
        • 직접적 강화학습 (direct RL) : 강화학습 방법을 사용하여 가치함수와 정책을 직접적으로 개선하기 위해 사용 (이전 장에서 논의한 방법)
      • 계획에 관여하는 것은 간접적 강화학습이라고도 불림.
    • 직접적 방법과 간접적 방법의 장단점
      • 간접적 방법
        • 종종 제한된 경험을 보다 효과적으로 활용하여 더 적은 환경 상호작용으로부터 더 나은 정책을 달성함
      • 직접적 방법
        • 간접적 방법보다 훨씬 간단하며, 모델 설계에 영향을 주지 않음
        • 대부분의 인간과 동물의 학습에 기여하는 방법
      • 심리학, 인공지능 분야에서는 의사결정과 반복적 학습 간의 상대적 중요성, 계획적 의사 결정과 반응적 의사 결정 간의 상대적 중요성에 대한 논의가 이루어지고 있음.
        • 첵의 관점은 이러한 논쟁들에서 대안 간의 대비는 과장된 것으로 보고, 실제 이 두가지 접근 방식 간의 유사성을 인정함으로써 더 많은 통찰력을 얻을 수 있다고 보고있음.
    • Dyna-Q 에 대하여
      • 위 다이어그램에 표시된 모든 과정 - 계획, 행동, 모델학습 및 직접적 강화학습 - 이 지속적으로 발생하는 것을 포함한다.
      • 계획 : random-sample one-step tabular Q-planning (위에 설명함)
      • 직접 강화학습 (direct RL) : one-step tabular Q-learning
      • 모델학습 : 테이블 기반, 결정론적 환경이라고 가정
        • 각 전이 $S_t, A_t \to R_{t+1}, S_{t+1}$ 이후 모델은 $S_t, A_t$ 에 대한 예측으로 $R_{t+1}, S_{t+1}$ 이 결정론적으로 발생한다는 정보를 기록
        • 따라서 모델이 이전에 경험한 상태-행동 쌍으로 쿼리되면, 마지막으로 관찰된 다음 상태와 보상을 예측으로 반환함
        • 계획 중 Q-planning 알고리즘은 이전에 경험한 상태-행동 쌍에서만 무작위 샘플링을 수행하기 때문에 모델은 정보가 없는 쌍으로 쿼리되지 않음.

      

      • Dyna-Q 알고리즘을 포함한 Dyna 에이전트의 전체적인 구조
        • 중앙 열은 에이전트와 환경 간의 상호작용을 나타내며, 실제 경험의 궤적을 만들어 냄
        • 왼쪽 화살표는 실제 경험에 적용하여 가치함수와 정책을 개선하는 직접적 강화학습을 나타냄
        • 오른쪽 부분은 모델 기반 프로세스를 나타냄
          • 모델은 실제 경험으로부터 학습되어 모의 경험을 생성함
          • 모델이 생성한 모의 경험의 시작 상태와 행동을 선택하는 프로세스를 탐색 제어(search control) 라고 함
        • 계획은 모의 경험 (simulated experience) 에 대해 실제로 일어난 것처럼 강화학습 방법을 적용함으로써 달성됨
          • 일반적으로 (Dyna-Q 도 해당) 실제 경험으로부터 학습하는 데 사용된 강화학습 방법과 모의 경험으로부터 계획하는데 사용되는 강화학습 방법은 동일함
          • 따라서 강화학습 방법은 학습, 계획 모두에 대한 공통경로가 됨
          • 학습과 계획은 거의 모든 부분을 공유하므로 깊게 통합되어 있고, 경험의 소스만 다르다. (환경, 모델)

      

      • Tabular Dyna-Q
        • 개념적으로 계획, 행동, 모델학습, 직접적인 강화학습은 Dyna 에이전트에서 동시에 병렬적으로 발생한다.
        • 그러나 직렬 컴퓨터에서 구현하기 위해 시간 단위 내에 발생하는 순서를 지정한다.
          • Dyna-Q 에서 행동, 모델 학습 및 직접적 강화학습 프로세스는 거의 계산이 필요하지 않으며, 시간의 일부분만 소비한다고 가정한다.
          • 각 단계에서 남은 시간은 계산이 많이 필요한 계획 프로세스에 할당된다.
          • 행동, 모델 학습 및 직접적 강화학습 후 각 단계에서 Q-planning 알고리즘의 n 번째 반복 (step 1-3) 을 완료하기 위한 시간이 있다고 가정한다.
          • 위 psuedo code 알고리즘에서 $Model(s,a)$ 는 상태-행동 쌍 $(s,a)$ 에 대한 (다음 상태와 보상) 의 내용을 나타낸다.
          • 직접 강화학습, 모델 학습 및 계획은 각각 단계 (d), (e), (f) 로 구현된다.
          • (e) 와 (f) 를 생략하면 남은 알고리즘은 one-step tabular Q-learning 이 된다.

  • 예제 8.1 : Dyna Maze

    

    • 문제의 정의
      • 그림 8.2의 소형 미로를 고려한다.
      • 상태 : 47개의 상태
      • 동작
        • 위, 아래, 오른쪽 및 왼쪽으로 이동.
        • 각 동작은 대응하는 인접 상태로 결정론적으로 이동시킨다.
        • 다만 장애물 또는 미로의 가장자리로 이동하는 경우에는 에이전트가 현재 위치에 머물게 됨.
      • 보상
        • 모든 전이에서 0
        • 목표 상태로의 전이에서 +1
      • 목표 상태(G)에 도달한 후, 에이전트는 새로운 에피소드를 시작하기 위해 시작 상태(S) 로 돌아감.
      • 감가율 적용 ($\gamma = 0.95$)
      • 에피소드 형태의 문제
    • 결과의 해석
      • 그림 8.2 에서 미로 과제에 Dyna-Q 에이전트가 적용된 실험에서의 평균 학습 곡선을 보여줌
        • 초기 행동가치는 0이며, step-size 파라미터는 $\alpha = 0.1$, 탐색 파라미터는 $\varepsilon = 0.1$ 이다.
        • 탐욕 방식으로 동작하였을 때, 동점일 경우 무작위로 결정한다.
      • 에이전트는 실제 단계마다 수행하는 계획 단계의 수인 n 에 의해 다양하게 변한다.
        • 각 n에 대해 실험을 30회 반복하여 에피소드에서 목표에 도달하기까지 취한 스텝 수를 평균화한 결과를 보여준다.
          • 각 반복에서 난수생성기의 초기 시드는 동일하게 유지함
          • 따라서 첫 버째 에피소드는 모둔 n의 값에 대해 정확히 동일했으며 (약 1700 스텝), 그 데이터는 그림에서 표시되지 않았음.
        • 첫 번째 에피소드 이후, 모든 n 값에 대해 성능이 향상되었지만, 특히 n 값이 큰 경우 더 빠르게 종료됨.
        • $n=0$ 인 에이전트는 계획 없는 에이전트로서 직접 강화학습 (one-step tabular Q-learning) 만 사용
        • 계획 없는 에이전트는 최적 성능 ($\varepsilon$-optimal) 에 도달하는 데 약 25번의 에피소드가 걸렸으며, $n=5$ 인 에이전트는 5번의 에피소드, $n=50$ 인 에이전트는 3번의 에피소드가 걸렸음.

      

      • 그림 8.3은 계획 에이전트가 계획 없는 에이전트보다 훨씬 빠르게 해결책을 찾은 이유를 보여준다.
        • 그림은 두 번째 에피소드의 중간 지점에서 $n=0$ 및 $n=50$ 에이전트가 찾은 정책이 표시된 것이다.
        • $n=0$ 인 경우 (계획이 없는 경우), 각 에피소드는 정책에 마지막 한 스텝만 추가하므로, 하나의 스텝만을 학습하였다.
        • 계획을 사용하면, 첫 번째 에피소드에서는 하나의 단계만 배웠지만, 두 번째 에피소드에서는 광범위한 정책이 개발된다.
          • 첫 번째 에피소드는 환경과 상호작용을 하면서 실제 경험을 얻는 과정이며, 이 경험은 진행된 경로에 한정하여 활용된다.
          • 두 번째 에피소드부터 모델 기반 학습을 통해 미래 상태에 대한 예측을 수행한다.
            • 모델은 환경에서 얻은 실제 경험으로부터 구축되며, 각 상태에서 가능한 모든 행동과 보상에 대한 확률 분포를 기록한다.
              • 실제 환경과의 상호작용을 통해 얻을 경험을 통해 일정한 정책이 개발
              • 모델 기반 학습을 통해 얻은 미래 상태에 대한 예측을 사용하여 더 다양한 정책을 탐색하고 개발
        • 세 번째 에피소드가 끝날 때 완전한 최적 정책이 발견되고, 완전한 성능이 달성된다.
    • Dyna-Q 의 진행 방식
      • Dyna-Q에서 학습과 계획은 정확히 동일한 알고리즘을 사용하여 실제 경험에 대해 학습하고 계획에서 가상 경험을 활용하여 수행
        • 계획은 점진적으로 진행되므로 계획과 행동을 혼합하는 것이 매우 간단하다.
      • 에이전트는 최신 감각 정보에 즉각적으로 응답하지만 항상 백그라운드에서 계획을 진행한다.
      • 또한 백그라운드에서 모델 학습 프로세스도 진행한다.
        • 새로운 정보가 얻어지면 모델은 현실과 더 잘 일치하도록 업데이트된다.
      • 모델이 변경되면 지속적으로 계획되는 프로세스가 새로운 모델과 일치하도록 서서히 다른 방식으로 동작을 계산할 것임.

What is a model?

• What is a Model?

  • 개요
    • 실 생활에서의 결정의 예
      • 결정할 때 많은 생각을 하지 않는 경우 - 직장에 어떻게 운전해서 가는지?
      • 결정을 할 때 많은 가능한 시나리오를 생각하는 경우 - 한손으로 취약한 물건을 운반할 때 벌어질 수 있는 시나리오들을 상상하는 것
    • 이전에 배운 학습법의 경우
      • TD : 샘플링된 경험으로부터만 학습함
      • DP : 완성된 정보를 이용하여 계획함 (결정이 불필요)
    • 위 두 방법의 중간에 해당하는 방법을 통해 양 방법의 이점을 모두 활용할 방법 찾기
      • 이번 장에서 다룰 Dyna 구조도 그러한 형태 중 하나임
  • 학습목표
    • 모델이 무엇인지와 어떻게 쓰이는지 설명
    • 모델을 분포모델 (distribution models) 또는 샘플모델 (sample models) 로 분류
    • 언제 분포모델을 쓸지 샘플모델을 쓸지 식별하기

  • 모델에 대하여

    

    • 모델은 역학에 대한 지식을 저장한다.
    • 이 장에서 모델은 상태전이와 보상에 대한 역학을 저장한다.
      • 이것은 실제 행동을 하지 않고도 행동에 대한 결과를 살펴볼 수 있게 해줌

    

    • 모델은 계획(Planning) 을 가능하게 한다.
      • 계획 (Planning) 이란 모델을 이용하여 정책을 개선하는 프로세스를 말한다.
      • 모델을 이용하여 계획하는 하나의 방법은 모델을 활용해 가상의 경험을 생성하여 가치함수와 정책을 개선하는 것이다.
        • 가상의 경험을 이용한다는 것은 최적 정책에 도달하기 위해 실제 환경과 상호작용이 덜 필요하다는 것을 의미함

    • 모델의 종류

      sample_models

      • Sample model (샘플모델)
        • 기본 확률에서 도출된 실제 결과를 생성한 것
        • 예를 들어 하나의 코인을 던져 앞면인지 뒷면인지에 대한 무작위 시퀀스를 생성하는 것
        • 샘플 모델은 일련의 규칙에 따라 무작위 결과를 생성할 수 있기 때문에 저렴하다.
          • 예를 들어 5개의 동전을 던지기 위해 임의로 하나의 동전을 독립적으로 5번 던져서 하나의 결과를 생성
          • CloudFlare 사의 라바램프(불규칙한 자연적 무작위성)를 활용(샘플)한 암호화

      

      • Distribution model (분포모델)
        • 모든 결과의 가능성 또는 확률을 완전히 지정한 것
        • 예를 들어 하나의 코인을 던졌을 때 앞면일 확률은 50% 이고 뒷면인 확률은 50% 인 것, 이 정보를 이용해 특정 시퀀스가 발생할 확률을 생성할 수 있음
        • 분포모델은 더 많은 정보가 포함되어 있지만, 특정하기 어렵고 비용도 비싸다.
          • 예를 들어 5개의 동전을 던질 때 가능한 앞면과 뒷면의 시퀀스 32개의 결과를 완전히 설명
            • 결과의 명시 확률에 따라 결과를 샘플 모델로 사용할 수 있다. (분포모델이 더 많은 정보를 포함하고 있다.)

• Comparing Sample and Distribution Models

  • 학습목표
    • 샘플모델과 분포모델의 장단점 설명
    • 왜 샘플모델이 분포모델보다 간결하게 표현될 수 있는지 이유 설명
  • 12개의 주사위 문제
    • 의도
      • 12개의 주사위를 던지는 행위에 대한 샘플모델과 분포모델의 접근방식에 대해 알아보고자 함
    • 샘플모델
      • 하나의 주사위를 12번 던져보는 것
      • 프로그램으로 생각하면 1-6 사이의 무작위 수를 12번 생성하는 것
      • 간결하고, 공동의 확률을 생각하지 않는다.
      • 적은 메모리를 차지한다.
      • 많은 샘플을 평균화 함으로써 예측되는 결과를 근사할 수 있다.
    • 분포모델
      • 12개의 주사위가 가질 수 있는 모든 경우의 수와 그것에 대한 확률을 고려해야 한다.
      • 12개의 주사위는 $6^{12}$ 의 경우의 수 (2176782336 가지) 를 가진다.
      • 결과에 대한 정확한 확률을 생산한다는 장점이 있다.
        • 예상하는 결과를 직접 계산하거나 결과의 변동성을 정량화할 수 있음
      • 확률로 가중치를 부여한 모든 결과를 합산하여 정확한 예상결과를 계산할 수 있다.
      • 위험을 평가할 수 있는 유연성이 있다.
        • 예를 들어 의사가 약을 처방할 때 가능한 많은 부작용과 발생할 가능성을 고려할 경우

Planning

• Random Tabular Q-planning

  • 학습목표
    • 정책 개선을 위해 계획이 어떻게 쓰이는지 설명
    • random-sample one-step tabular Q-planning 설명
  • 계획 (Planning)
    • 모델을 강화학습에 적용 : 환경과의 상호작용 없이 모델을 활용하여 더 나은 의사결정을 할 수 있도록 하는 것
      • 이 과정을 모델 경험을 통한 계획이라 한다.

    • 계획 (Planning) 의 정의

      

      • 모델을 입력값으로 개선된 정책을 생성하는 과정

      

      • 계획에 대한 한 가지 접근 방식은 먼저 모델에서 경험을 샘플링하는 것임
        • 세상이 어떻게 돌아가는지에 대한 이해를 바탕으로 세상에서 가능한 시나리오를 상상하는 것과 같음.
      • 이 생성된 경험은 마치 실제 상호작용이 발생한 것처럼 가치함수에 대한 업데이트를 수행하는 데 사용할 수 있음.
      • 이러한 개선된 가치에 탐욕 행동을 선택하면 정책이 개선됨.

  • Random-sample one-step tabular Q-planning

    • Q-learning 과 Q-planning 에 대해
      • Q-learning 은 환경에서 경험한 것을 사용하여 정책을 개선하기 위해 업데이트를 수행함.
      • Q-planning 은 모델의 경험을 사용하고, 유사한 업데이트를 수행하여 정책을 개선함.

    

    • Random-sample one-step tabular Q-planning
      • 가정
        • 전이 역학에 대한 샘플 모델을 가지고 있다고 가정한다.
        • 샘플에 상응하는 상태, 행동 쌍을 가지고 있다고 가정한다.
      • 하나의 선택지는 상태와 행동을 균일하게 샘플링하는 것이다.
        • 전체 상태, 행동 집합에서 랜덤하게 상태, 행동 쌍을 선택한다.
        • 그 뒤로 샘플 모델을 이용해 상태, 행동값에 대한 다음 상태와 보상을 질의한다.
      • 위의 입력값과 결과값을 이용해 Q-learning update 를 진행한다.
      • 탐욕화를 이용해 정책을 개선한다.

    • Planning 의 특징

      

      • Planning 은 환경과 에이전트의 상호작용 결과가 아닌, 가상의 (상상의) 경험을 사용한다.

      

      • 환경과 에이전트의 상호작용 없이 진행하거나, 상호작용을 하는 중에 동시에 진행되기도 한다.
        • 행동이 특정 시간대에 일어나면서, 학습 업데이트가 상대적으로 더 빠를 경우 시간적 공백이 생긴다.
        • 예를 들면, 이 공백 시간에 계획을 업데이트 할 수 있다.
        • 예를 들어 로봇이 절벽 쪽에 다가갔을때의 결과가 모델에 있고, 가치함수나 정책에 아직 반영이 되지 않은 경우 가상의 경험을 생성하여 계획을 진행해 볼 수 있다.

Dyna as formalism for planning

• The Dyna Architecture

  • 개요

    

    • Direct RL : World (환경) 와 직접적인 상호작용을 하고, Q-learning 을 통해 학습하는 것
    • Planning : 모델로부터 생성된 가상 경험을 통해 학습하는 것
    • Dyna 구조 : Direct RL + Planning
  • 학습목표
    • 모델로부터의 가상경험과 환경으로부터의 상호작용 간의 차이점을 이해
    • Dyna 구조를 통해 직접 RL(direct RL) 과 계획 (planning) 업데이트를 결합하는 방법 이해
  • Q-learning 과 Q-planning 의 결합
    • Q-learning update: 환경으로부터의 경험을 통해 정책과 가치함수 업데이트
    • Q-planning update: 모델에서 생성한 경험을 통해 정책과 가치함수 업데이트
    • Dyna 구조를 통한 Q-learning 과 Q-planning 의 결합

  • Dyna 구조

    

    • (중간부분) 환경과의 상호작용을 통해 경험의 흐름을 생성한다.
    • (왼쪽부분) 위 경험을 직접적으로 이용해 정책/가치함수를 업데이트 하는 것을 direct RL update 라 한다.
    • (오른쪽 부분) Planning 을 위해서는 모델이 필요하다. 환경과의 상호작용을 통해 얻은 경험으로 모델을 학습시킬 수 있다.
      • 모델은 model experience 를 생성한다.
      • 위 경험을 생성할 때, 어떠한 가상 경험을 생성하여 계획을 구성할지 제어하는 것을 search control 이라 한다.
      • planning update 는 모델로부터 생성된 경험으로 정책/가치함수를 업데이트 하는 것을 말한다.
  • Dyna 의 예시 : simple maze

    • 문제의 설명

      

      • 로봇이 미로를 탈출하는 문제
      • 로봇은 Goal 에서 +1 의 보상을 얻고, 그렇지 않은 부분에서는 0의 보상을 얻는다.

      

      • 로봇은 첫 시도에 헤메게 되며, 결국 골에 도착하고 보상 1 을 획득, 에피소드를 종료하게 된다.
        • 노랗게 표시된 부분은 로봇에 실제 한번 이상 방문한 상태이다.
        • 로봇은 행동가치함수를 업데이트 하는데, 실제 영향을 받는 부분은 보라색 상태 뿐이다.
          • $Q(s,a) \gets Q(s,a) + \alpha (r + \gamma \max_{a’} Q(s’,a’) - Q(s,a))$
          • 보상값이 존재하는 상태가 종료 상태 뿐이기 때문
          • 위의 업데이트가 direct RL 을 통해 이루어진 업데이트이다.
      • Dyna 는 첫 번째 에피소드 동안 생성된 모든 경험을 이용하여 모델을 학습한다.
        • 노랗게 표시된 부분이 첫 에피소드 동안 방문한 상태이다. 로봇은 전체 상태를 방문하지 않았지만, 대부분의 상태를 이미 방문하였다.
        • Dyna 는 모든 타임스텝에 대해 planning 을 진행한다.
          • 하지만, planning 은 첫 에피소드 동안에는 정책에 영향을 주지 않는다. (비록 모델이 각 타입스텝마다 점점 정확해지더라도…)
          • 첫 에피소드가 끝나면, planning 이 작동하기 시작한다.
            • 모델을 통해 노랗게 표시된 부분에서 어떠한 반환값이 나올 지 이미 알고 있다.
            • Dyna 는 이미 방문한 상태-행동 쌍에 대한 전이를 시뮬레이션 할 수 있다. (World 의 모방)
            • Planning 의 각 타임스텝 동안 가상의 경험을 통해 Q-learning 업데이트를 진행할 수 있다.

      

      • 충분한 Planning 단계를 거쳐, 에이전트는 모든 방문한 상태에 대한 정책을 업데이트 할 수 있다.
        • Dyna 는 더 많은 계산을 하지만, 제한된 경험을 보다 효율적으로 활용한다.
        • 이것은 Cartoon 의 예시일 뿐, 실제로 에이전트는 위 정책보다 더 탐색적으로 행동하게 되고, Planning 단계에서 정책은 계속 수정되게 된다.

• The Dyna Algorithm

  • 학습목표
    • Tabular Dyna-Q 알고리즘 설명
    • Tabular Dyna-Q 내에서 직접RL과 계획 업데이트 식별
    • Tabular Dyna-Q 내에서 모델학습과 탐색제어 요소를 식별
  • Tabular Dyna-Q 에서의 모델 학습

    • 우선 Tabular Dyna-Q 는 결정론적 전이를 가정한다.

      

      • 위 그림에서 토끼가 A 상태에서 오른쪽으로 움직이기로 결정하였다면, 오직 한 종류의 결과만이 발생한다. (B, 0)
      • 에이전트가 위 세 가지 상태-행동을 경험하였다면, 모델은 위 세 가지 상태-행동에 따르는 결과를 알게 된다.

  • Tabular Dyna-Q psuedo code

    

    • 에이전트가 환경과 상호작용 하며, $\varepsilon$-greedy 정책을 따르고 있다.
    • 위 정책에 따른 행동을 하면, 결과 보상과 다음 상태를 관측할 수 있다.
    • 위 값들도 Q-learning update 를 진행한다. (여기까지가 direct-RL)
    • (여기에서 멈춘다면, Q-learning 알고리즘이 된다.)

    

    • Dyna-Q는 이 전이를 이용해 model learning step 을 진행한다. (Model-free method 와 차이)
      • 모델은 위의 전이를 기억, 저장한다. (환경이 결정론적이라는 가정)

    

    • Dyna-Q는 planning 을 n-step 진행한다.
      • 각각의 planning step 은 3가지 단계를 포함한다.
        • search control : 이전 방문한 상태, 행동 쌍을 랜덤하게 결정한다.
        • model query : 위 선택된 상태, 행동 쌍을 이용, 모델에 다음 상태와 보상을 질의한다.
        • value update : Q-learning update 를 진행한다.

    

    • Dyna-Q는 각 전이에 대해 많은 planning update 를 수행한다.
      • 첫 에피소드 184 step 이후 (이 때의 결과를 Model learning 에 활용)
      • 두 번째 에피소드 1 step 당 100 회의 planning 을 진행함으로서 많은 정책이 개발되었음을 확인할 수 있음.

• Dyna & Q-learning in a Simple Maze

  • 학습목표
    • 작은 GridWorld 내에서 Model-free Q-learning 학습과 Dyna-Q 학습을 비교
    • 환경의 경험과 모델의 가상경험으로부터의 학습이 성능에 어떤 영향을 주는지 확인
    • 정확한 모델이 에이전트가 환경과의 상호작용의 요구도를 낮추는 방법을 설명
  • 미로 환경에서의 실험

    • 문제의 설정

      

      • 행동 : 4가지 방향으로 이동
      • 보상 : 목표 상태로 전이시 +1, 그 외의 경우 0
      • 에피소딕 문제
      • 할인율 0.95
      • $\alpha = 0.1$, $\varepsilon = 0.1$
      • 행동 가치의 초기값은 모두 0으로 세팅
    • 의도
      • 3 개의 에이전트를 비교 (n=0, n=5, n=50)
      • 각각의 실험을 50 에피소드, 30번 실행하고 결과의 평균을 구함

    • 결과해석

      

      • 각 에이전트가 에피소드를 완료하는 데 걸린 평균 단계 수 (30번 수행의 평균) 를 표현. 즉, 에이전트가 잘 수행한다면 단계의 수가 감소 (y 값이 낮을 수록 좋음)
      • Dyna-Q 를 0 계획 단계로 수행하면 Q-러닝 알고리즘과 정확히 동일한 결과이다.
        • 14 에피소드 정도에서 수렴을 함
      • Dyna-Q 를 5 계획 단계로 수행하면 더 빠르게 수렴함.
      • Dyna-Q 를 50 계획 단계로 수행하면 3번째 에피소드에서 수렴함.
        • 즉, 샘플을 더 효율적으로 사용함 (모델이 정확한 경우 환경 경험을 더 잘 활용함)
    • 다른 미로에서의 진행상황 해석
      • 하나의 에피소드 후 Q-러닝은 목표 옆 상태에서 위 동작에 해당하는 하나의 동작 값만 업데이트 됨 (0이 아닌 보상이 발생한 유일한 전환)
      • 이 상태의 값을 다른 인접 상태로 부트스트랩 하는 데는 몇 에피소드가 더 필요함

      

      • search control 이 계획에 미치는 영향을 살펴본다. (Dyna-Q와 조금 다른 방식으로 작동하나, 포인트를 더 강조할 수 있음)
        • 계획 단계를 10개로 설정하고, 계획 루프를 10번 연속 호출 (총 100개의 계획 단계)
        • 보다시피, 많은 계획 업데이트가 가치함수를 변경하지 못하고, 단 2개의 상태 행동 쌍만 업데이트하였음.
        • 계속 진행 (각 호출마다 100개의 계획 단계를 시도)
        • 몇 번의 호출은 소수의 동작 값만 업데이트 한다.
          • 검색 제어 (Search Control) 가 상태-행동 쌍을 무작위로 샘플링하기 때문. 즉, 샘플 상대-행동 쌍이 T 오류를 0 으로 생성한다면 업데이트는 아무런 효과가 없음.
          • 모든 보상도 0이고, 초기값도 0이기 때문에 이 환경에서 자주 발생한다.
          • 검색 제어의 주제에 대해서는 교재의 8.4 섹션을 확인.

Dealing with inaccurate models

• What if the model is inaccurate?

  • 학습목표
    • 어떠한 모델이 부정확한건지 식별하는 방법
    • 부정확한 모델에서 계획이 어떤 효과를 주는지 설명
    • 부분적으로 부정확한 모델에서 Dyna 가 성공적으로 계획하는 방법 서술

  • 부정확한 모델이란?

    

    • 모델이 저장한 전이가 환경에서 일어난 전이와 다를 때 발생
    • 불완전한 모델 : 학습 초기에 에이전트가 일부의 상태에서 일부의 행동만 시도했을 경우, 모델에 누락된 전이 정보가 생기게 됨.
    • 부정확한 모델 : 모든 상태에서 모든 행동을 수행했더라도, 환경이 변화하여 실제 환경과 모델간 전이 정보가 다를 경우.
  • 부정확한 모델로 계획을 세울 떄 발생할 수 있는 일
    • 불완전한 모델로 계획을 세울 때 전이 정보가 없는 상태에서 계획을 세울 수 없음. 그러나 에이전트가 환경과 상호작용하면서 더 많은 전이를 경험하면 학습이 가능해진다.

    

    • 부정확한 모델일 경우 계획 업데이트 시 가치 함수나 정책이 잘못된 방향으로 변경될 수 있음.

  • 불완전한 모델로 성공적인 계획을 하는 방법

    

    • Dyna-Q 의 경우에서 처럼, 계획 단계에서 모델이 어떤 상태-행동 쌍을 쿼리할지 결정
      • Dyna-Q 는 이미 방문한 상태-행동 쌍에 대해서만 계획 업데이트를 수행한다. (이미 모델에 전이 정보가 존재)
      • 초기에는 이미 방문한 상태-행동에 대해서만 반복적으로 업데이트를 수행할 수 있으나, 에이전트가 점점 더 많은 상태-행동 쌍을 방문하면 계획 업데이트가 상태-행동 공간 전체에 더 고르게 진행됨.
    • 부정확한 모델로 계획을 세울 때 계획은 모델을 기준으로 정책이나 가치함수를 개선함 (환경을 기준으로 개선되지 않음)

• In-depth with changing environments

  • 학습목표
    • 모델의 부정확성이 또다른 탐색-이용 trade-off 를 생성하는지 설명
    • 위의 trade-off 를 Dyna-Q+ 가 해결하는 방법 설명
  • 모델이 부정확한 경우
    • 모델이 부정확하면 계획은 환경을 기준으로 정책이나 가치함수를 악화시킬 수 있음.
      • 이는 에이전트가 모델이 정확한지 확인하기 위해 노력해야 한다는 것을 의미한다.
      • 즉, 에이전트가 환경에서 전이를 경험한 후 모델을 수정해야 함
    • 일반적으로 에이전트는 자신의 모든 모델 전이가 올바른지 다시 확인하려고 할 것임.
      • 그러나 낮은 가치의 행동 전이를 다시 확인하면, 낮은 보상을 얻게 됨.
      • 변화하는 환경에서는 언제든지 에이전트의 모델이 부정확해질 수 있음.

      • 에이전트는 선택을 해야 한다.

        

        • 모델이 정확한 것으로 가정하여, 최적의 정책 계산을 위해 환경 탐사
        • 모델이 정확한지 확인
      • 환경이 변화하면, 모델은 부정확해진다.
        • 환경이 변경된 부분을 재방문하고 모델을 업데이트 하기 전까지 모델은 부정확한 상태로 유지된다.
        • 즉, 오랜 기간 동안 방문하지 않은 장소를 탐사해야 한다는 것
  • Dyna-Q+ 에서의 해결 방법
    • 모델은 에이전트가 오랫동안 방문하지 않은 상태에서 더욱 잘못될 가능성이 높음.
    • 에이전트가 주기적으로 상태를 다시 방문하도록 유도하기 위해 계획에 사용되는 보상에 보너스를 추가할 수 있다.

    • 이것을 탐사 보너스라고 한다.

      

      • 이 보너스는 단순히 $\kappa$ (Kappa) 에 $\tau$ (Tau) 의 제곱근을 곱한 것이다.
      • $r$ : 모델에서의 보상
      • $\tau$ : 환경에서 해당 상태 행동 쌍을 마지막으로 방문한 시간.
        • 계획 루프에서 업데이트되지 않음. (실제 방문이 아님.)
      • $\kappa$ : 보너스가 계획 업데이트에 미치는 영향을 조절하는 작은 상수.
        • 0이면 보너스를 완전히 무시함.

    • 탐사 보너스를 계획 업데이트에 추가하면 Dyna-Q+ 알고리즘이 생성됨.

      

      • 계획에 사용되는 보상을 인위적으로 증가시킴으로써, 최근에 방문하지 않은 상태 행동 쌍의 가치를 증가시킨다.
        • 오랫동안 방문하지 않은 상태 행동 쌍에 대한 $\tau$ 가 큰 상태 : $\tau$ 가 커질수록 보너스가 점점 커진다는 것을 의미
        • 결국 계획은 큰 보너스 때문에 해당 상태 $S$ 로 직접 가도록 정책을 변경하게 된다.
          • 에이전트가 상태 $S$ 에 방문하면 큰 보상을 볼 수도 있고, 실망을 할 수도 있다. 어떤 경우든 모델은 환경의 역학을 반영하도록 업데이트된다.
  • Dyna-Q 와 Dyna-Q+ 간 비교
    • 문제의 설정
      • 기본적인 미로 문제이며, 시작 상태에서 목표 상태까지 빠르게 도달하는 것이 목표임.
        • 보상은 목표 지점을 제외하고 0이며, 목표 지점에서 +1의 보상을 제공
        • 할인율은 1보다 작음
      • $\varepsilon$-greedy 정책을 사용

    • 결과의 해석

      

      • 실험의 절반에서는 Dyna-Q 와 Dyna-Q+ 가 매우 유사하게 작동
        • 이 경우 Dyna-Q+ 의 증가된 탐사는 더 빨리 좋은 정책을 찾는데 도움이 됨. (실제로 라인이 위에 있음)

      

      • 실험이 절반 쯤 진행되었을 때 벽의 오른쪽에 지름길을 제공
        • 환경이 변화된 후 Dyna-Q+ 는 지름길을 찾아냈음.
        • Dyna-Q는 시간 내에 지름길을 찾지 못하였음.
          • 결국 Dyna-Q도 $\varepsilon$-greedy 정책에 의해 전체 상태-행동 공간을 탐사함으로써 지름길을 찾을 것이다.
          • 그러나 위의 경우 많은 탐사가 필요하게 된다.
      • 에이전트는 모델이 정확한지 확인하기 위해 탐사를 해야하며, Dyna-Q+ 가 환경을 탐사하기 위해 탐사 보너스를 활용하는 방법에 대해 알아보았다.
• Drew Bagnell: self-driving, robotics, and Model Based RL
  • 자율주행, 로보틱스, 모델기반 강화학습에 대해
    • 자율주행에 대해
      • 거리의 복잡성을 기계학습을 통해 인식함.
      • 의사결정이 필요
        • 타 주체들의 행동에 따른 복잡성, 간단한 규칙 (좌회전 신호에 좌회전을 한다 등) 의 조정 등의 어려움
        • 연속된 상태와 동작
        • 즉, 연속된 상태 및 동작의 모델이 필요함.
    • 모델
      • 현재 상태와 동작을 다음 상태로 매핑하는 전환함수 혹은 동역학
      • 특정상태의 동작을 평가할 수 있는 함수
    • 의사결정 문제
      • 의사결정이 필요한 로봇 학습은 모두 모델기반이다.
        • 로봇들 간의 상호작용에 따르는 효율, 비용적 측면에서 지수적인 차이가 발생
    • 연속된 상태 동작 모델의 활용법
      • 제곱근 가치 함수 근사법 (Quadratic Value Function Approximation)
        • 환경이 선형이거나 선형으로 근사 가능한 경우 사용 가능
        • 여기에서는 다루지 않음
      • Differential Dynamic Programming (DDP)
        • 최적 제어 정책을 추정
        • 여기에서는 다루지 않음
• Week 4 Summary (Planning, Learning, Acting)

  • Types of models (distribution vs sample)

    

    • Distribution models : 모든 전이확률을 모델 데이터로 가지고 있음, 많은 메모리 필요, Sample model 생성 가능
    • Sample models : 전이확률을 따로 저장하지 않음, 많은 메모리 불필요

  • One-step Q-planning

    

    • Q-learning 과 동일하나, 모델에서 생성한 경험을 이용하여 업데이트함.

  • Dyna architecture

    

    • Planning 과 Learning 을 Single agent 에서 수행
    • 많은 planning update 를 통해 학습을 더 빠르게 진행할 수 있음 (환경과의 상호작용을 덜 하게 됨)
    • 불완전한 모델의 경우 상호작용을 통해 모델이 점점 완성되게 된다.

  • Dyna-Q+

    

    • 부정확한 모델의 경우 탐색 보너스를 통해 오랫동안 방문하지 않은 상태를 방문하도록 정책을 유도하여 모델을 업데이트하도록 한다.

• Summary (생각해볼 점)

  • Part 1 에서 배운 강화학습의 종류

  

  • 생각해볼 점
    • 반환(리턴)의 정의: 과제는 에피소드식인지 계속적인지, 할인 적용 여부에 따라 다름.
    • 행동 가치 vs 상태 가치 vs 후상태 가치: 어떤 종류의 가치를 추정해야 하는지? 상태 가치만 추정하는 경우, 행동 선택을 위해 모델이나 별도의 정책(액터-크리틱 방법과 같은)이 필요함.
    • 행동 선택/탐사: 탐사와 활용 사이의 적절한 균형을 유지하기 위해 어떻게 행동을 선택해야 하는지? 우리는 이를 위한 가장 간단한 방법만 고려해봄: e-greedy, 낙관적 초기화, 소프트 맥스 및 상한 신뢰 구간.
    • 동기화 vs 비동기화: 모든 상태의 업데이트는 동시에 수행되어야 하는가, 또는 어떤 순서로 하나씩 수행되어야 하는가?
    • 실제 vs 모의: 실제 경험 또는 모의 경험을 기반으로 업데이트. 둘 다 하는 경우, 각각 어느 정도씩 해야하는지?
    • 업데이트 위치: 어떤 상태나 상태-행동 쌍을 업데이트해야하는지? Model-free 방법은 실제로 만난 상태와 상태-행동 쌍 중에서만 선택할 수 있지만, Model-based 방법은 임의로 선택할 수 있음. 이 부분에는 여러 가지 가능성이 있음.
    • 업데이트 시점: 업데이트는 행동 선택의 일부로 수행되어야 할지, 아니면 그 후에만 수행되어야 할지?
    • 업데이트 기억: 업데이트된 값은 얼마나 오래 유지되어야 할지? 영구적으로 유지, 아니면 휴리스틱 탐색과 같이 행동 선택을 계산하는 동안만 유지
  • 앞으로 살펴볼 점
    • 이러한 차원들은 절대적이거나 상호배반적인 것이 아님.
      • 각각의 알고리즘은 다양한 방식으로 차이가 있으며, 많은 알고리즘들은 여러 차원에서 여러 위치에 위치한다.
      • 예를 들어, Dyna 방법은 실제 경험과 모의 경험을 모두 사용하여 동일한 가치 함수에 영향을 미칩니다.
      • 서로 다른 방식이나 다른 상태 및 행동 표현에 걸쳐 계산된 여러 가치 함수를 유지하는 것도 합리적인 방법임.
    • 그러나 이러한 차원들은 다양한 가능한 방법의 넓은 공간을 묘사하고 탐구하기 위한 일관된 아이디어의 집합을 형성한다.
    • 여기에 언급되지 않은 가장 중요한 차원은 함수 근사의 차원이다.
      • 함수 근사는 한쪽 끝에서는 테이블 기반 방법을 통해 상태 집합, 다양한 선형 방법 및 다양한 비선형 방법으로 이어지는 여러 가지 가능성의 스펙트럼으로 볼 수 있다. 이 차원은 제 2부에서 탐구한다.