CMU10703 - Maximum Entropy Inverse RL, Adversarial imitation learning

in Reinforcement learning / Reinforcement learning on Cmu

Table of Contents

  1. Inverse Reinforcement learning
    1. Introduction
    2. Notation and Problem Formulation
      1. Markov Decision Processes
      2. Basic Properties of MDPs
      3. Inverse Reinforcement Learning
      4. IRL in Finite State Spaces
  2. Reference

Inverse Reinforcement learning

An image with a caption
  • IRL은 diagram을 뒤집은 것
    • Demonstration trajectories의 finite set이 주어지고, reward R 및 policy \(\pi^*\)을 복구!

  • DAGGER setup과 대조적으로, 추가적인 label에 대해서 전문가와 상호작용하는 query가 필요없다.

  • 수식적으로 imitation은 distribution matching problem 으로 압축:
    • Learner는 resulting state, action trajectory distribution이 expert trajectory distribution과 매칭 되는 reward/policy로 구성되어야 한다.

Introduction

  • IRL 문제는 (Russell, 1998) 와 같이 비공식적으로 아래와 같이 특징되어(characterize)질 수 있다:
    • Given :
      1. 다양한 상황에서, time에 따른 agent’s behavior 측정 값.
      2. 필요에 따라, agent에 대한 sensory input 측정 값.
      3. 가능하다면, 환경 모델.
    • Determine:
      • 최적화되는 reward function.
  • 기존에는 “expert”의 policy 를 학습.
    • 저자는 expert’s reward function을 복구하고 desirable behavior를 생성을 제안
    • RL은 policy보다 reward function이 더욱 succinct, robust, transferable 하다는 전제에 기반.
  • 이 논문에서는, 머신러닝관점에서 IRL 문제를 다룸(경제학, 제어에서도 IRL 문제를 풀려는 시도가 존재)
    • Section 2. MDP 및 IRL 정의
      • model 및 policy가 완전히 주어진 상태에 focus.
    • Section 3. 주어진 policy가 최적가 최적인 모든 reward function들의 집합에 대해 다룸
      • Problem: 많은 degenerate solution (e.g., reward function = 0) 들을 포함한 집합에 대해 시연.
      • Solution: Sub-optimal policy들과 observed policy의 차이를 최대화하는 reward function을 식별(identify)하는 heuristics 를 통해 문제 해결.
      • LP(Linear Programming) 를 사용하여 discrete case에서 효과적으로 진행.
    • Section 4. large or infinite state space에 대해 다룸.
      • Reward function의 tabular representation은 infeasible.
      • 고정된 basis function 및 임의의 linear combination으로 fitting된 reward function을 표현한다면, IRL 문제는 LP로 분류하고 효율적으로 풀 수 있음.
    • Section 5. 관측되는 trajectory들의 finite set을 통해서만 policy를 알 수 있는 현실적인 경우에 대해 다룸.
      • 단순히 iterative 알고리즘으로 해결.
    • Section 6. 위 세가지 알고리즘 적용.
      • Discrete, continous stochastic navigation 문제. “mountain-car” 문제
      • 모든 경우에 observed behavior를 잘 “설명”할 수 있는 reward function을 복구 할 수 있다.
    • Section 7. 요약 및 후속 연구 방향 소개

Notation and Problem Formulation

  • Notation, definition, basic theorems for MDPs에 대해 소개.
  • 우리가 앞으로 다룰 IRL 문제에 대해 정의.

Markov Decision Processes

  • (finite) MDP: tuple \((S, A, {P_{sa}}, \gamma, R)\), where
    • S: N개 states 의 finite set.
    • \(A = {a_1, ..., a_k}\): k actions 의 집합.
    • \(P_{sa}(\cdot)\) : state s 에서 action a 를 취하는 state transition probabilities.
    • \(\gamma \in [0, 1)\) : discount factor.
    • R : \(S \mapsto \mathbb{R}\) : reinforcement function, \(R_{max}\)에 의한 절대 값으로 bounded.
  • 설명(exposition)을 단순화 하기 위해서, R(s,a)을 R(s)로 reward 표기, extension은 trivial.
  • Policy: map \(\pi: S \mapsto A\) 으로 정의
  • Value function: policy \(\pi\) 에 대해 \(s_1\)에서 평가 될 때 다음과 같다.
\[\begin{aligned} V ^{\pi} (s_1) = E[R(s_1) + \gamma R(s_2) + \gamma ^2 R(s_3) + \cdots | \pi] \end{aligned}\]

where expection is over the distribution of the state sequence \((s_1, s_2, ...)\) we pass through when we execute the policy \(\pi\) strating from \(s_1\).

  • Q-function:
\[\begin{aligned} Q ^{\pi} (s,a) = R(s) + \gamma E_{s' ~ P_{sa}(\cdot)} [V ^{\pi} (s')] \end{aligned}\]

(where the notation \(s' ~ P_{sa}(\cdot)\) means the expectation is with respect to s’ distributed according to \(P_{sa} (\cdot)).\)

  • Optimal value function: \(V^* (s) = sup _{\pi} V ^\pi (s)\)

  • Optimal Q-function: \(Q^* (s,a) = sup _\pi Q^\pi (s,a)\)

Discrete, finite space 경우에는, 모든 이러한 함수들은 boldface notation 으로 쓰였으며, state에 index된 vector들로 표현. 더욱 정확하게 finite state space S 의 1부터 N까지 열거하는 것.

  • Reward: i th 요소가 MDP의 i th state 에서 reward를 가지는, N-차원 vector R 로 정의.
  • \(V^\pi\): state i 에서 평가되는 \(\pi\) 에 대한 i th 요소를 가지는 vector.

  • \(P_a\): 각 action a 에 대해서, element (i, j) 가 satet i 에서 action a 을 취해 state j 로 transitioning의 probability를 주는 N-by-N matrix.

  • 일반적인 RL의 목표는 \(V ^\pi\) 를 최대화하는 policy \(\pi\)를 찾는 것.
    • 모든 \(s \in S\) by \(\pi = \pi ^*\) 에 대해서 \(V^\pi\) 가 동시에 최대화되는 하는 optimal policy \(\pi ^*\) 가 하나라도 존재하는 것을 보였다. (e.g., Sutton & Barto, 1998; Bertsekas & Tsitsiklis, 1996)

Basic Properties of MDPs

  • IRL 문제에 대한 저자의 solution을 위해, MDPs (Sutton & Bartp, 1998; Bertsekas & Tsitsiklis, 1996) 에 대해서 고전적인(classical) 두 개의 결과가 필요.

  • Theorem 1 (Bellan Equations)

    • _Let an MDP M = \((S, A, {P_{sa}}, \gamma, R)\) and policy \(\pi\) : S \(\mapsto\) A be given.
    • Then, for all s \(\in S, a \in A, V ^\pi Q ^\pi\) 는 다음을 만족.
\[\begin{aligned} V^\pi (s) = R(s) + \gamma \sum _{s'} P _{s \pi(s)} (s') V ^\pi (s') \qquad (1) \\ Q^\pi (s, a) = R(s) + \gamma \sum _{s'} P _{sa} (s') V ^\pi (s') \qquad (2) \end{aligned}\]
  • Theorem 2 (Bellan Optimality)
    • Let an MDP M = \((S, A, {P_{sa}}, \gamma, R)\) and policy \(\pi\) : S \(\mapsto\) A be given.
    • Then \(\pi\) is an optimal policy for M if and only if, for all \(s \in S\),
\[\begin{aligned} \pi (s) \in argmax _{a\in A} Q ^\pi (s, a) \qquad (3) \end{aligned}\]

Inverse Reinforcement Learning

  • IRL 문제는 obsercved behavior를 설명할 수 있는 reward funcion를 찾는 것
  • State space가 finite, model이 알려져 있고, 완벽히 policy가 관측될 때의 간단한 경우부터 시작.
    • 구체적으로, finite state space S, k actions A =\({a_1, ..., a_k}\)의 집합, transition probabilities \({P_{sa}}\), a discount factor \(\gamma\), policy \(\pi\) 가 주어짐.
    • 목표: MDP \(S, A, {P_{sa}, \gamma, R}\)에서 \(\pi\)가 optimal policy인 가능한 reward function R의 set를 찾는 것.
    • 필요에 따라 action들을 rename하여, loss of generality 없이 \(\pi(s) \equiv a_1\)을 가정.
      • 이것은 notation을 단순화하기 위한 기술.

IRL in Finite State Spaces

  • 저자는 주어진 policy가 optimal인 모든 reward function들의 집합의 단순한 특징(characterization)을 제공.
An image with a caption

Reference

  • [Algorithms]

© 2020. All rights reserved.

Powered by Hydejack v8.1.1