9.1-introduction.md

9.1 Introduction

이전 chapter에 다른 agent들의 학습행동을 자신의 optimization term에 넣는 Learning with Opponent-Learning Awareness(LOLA)에 대해 배워보았습니다. 이 과정에서 업데이트하려는 agent는 다른 agent의 learning step을 미분할 수 있어야 했습니다. 이 과정에서 높은 차수의 gradient를 발생시키는 것을 보았습니다. 하지만 이 때, objective는 미분 불가하고(Go를 예로 들었을 때, 이겼을 때 1, 졌을 때 -1 이라면, 이 reward는 당연히 불연속적이고 미분 불가) 이를 해결하기 위해 sampling을 하여 해결하는 monte-carlo-estimation을 하게 됩니다. 이 때, 1차 미분은 policy gradient에서 많이 쓰이는 score function trick($\mathrm{\nabla }\log (\pi )$)를 사용해 추정 가능하지만 높은 차수의 미분은 좀 더 복잡합니다. 그렇기에 높은 차수의 미분을 좀 더 정의할 수 있다면, pytorch나 tensorflow 같은 auto-diff deep learning library에게 이를 맡기면 됩니다. 이는 LOLA에서 원하는 것을 넘어서 다른 여러 optimization technic에 유용할 수 있으며, 수렴을 가속할 수 있습니다.이는 meta-learning에서도 유용하게 사용됩니다.

• Monte-Carlo-Estimation을 사용하는 접근은 stochastic computation graph(SCG)로부터 surrogate objective를 생성하는 surrogate loss(SL)를 사용하는 method로, (이 용어들이 처음들어본다면 9.2 Background를 먼저 읽고 오시는것이 도움이 될 수 있습니다.) 미분이 될 때, SL가 원래 objective의 1차 미분의 추정값을 내놓게 됩니다.

하지만 위에서 언급한 1차 gradient를 구했던 방법은 높은 차수의 미분값을 구할 때 auto-diff library에 잘 맞지 않습니다. 높은 차수의 gradient estimator도 똑같은 score function trick을 사용해야하기 때문에 미분 값이 sampling distribution에 의존하게 됩니다. 또한 이처럼 미분하는 것은 이미 Finn의 연구결과에서 잘못된 term을 가져온다는 것을 보였습니다.

높은 차수의 score function gradient estimator를 구하는데 만족되지 않는 두 가지 점이 존재합니다.

• 첫째로, estimator를 sampling같은 방법이 아닌 analytical하게 유도하거나 구현해야합니다. 이는 번거롭고 오류가 나기 쉽고 auto-diff에 적용되기 어렵습니다.
• 둘째로, 새로운 objective를 위한 SL의 반복적인 적용을 적용하는 방법인데, 이는 점점 복잡한 그래프를 수반하게 됩니다.

SL에선 1차 미분 후 cost를 고정된 sample로 다룹니다. 이것이 높은 차수의 gradient estimator로 갔을 때, 얼마나 비정확한 term을 만드는지 보이는데, 이는 높은 차수의 gradient가 적용되야하는 method의 적용 범위를 제한하게 됩니다.

여기에선 위의 문제점들을 해결하기 위해 Infinitely Differentiable Monte-Carlo Estimator(DiCE)를 제시합니다. DiCE는 원래의 objective를 추정할 수 있는 정확한 미분값을 얻을 수 있다는 특징이 있습니다. SL의 접근방법과는 다르게 DiCE는 높은 차수의 gradient계산을 auto-diff에 의존합니다.

Dice는 Operator MAGICBOX(여기서는 $◻$로 표현하겠습니다.)를 정의합니다. SCG에서 original loss에 영향을 미치는 stochastic node ${\mathcal{W}}_c$를 모두 포함합니다. 만약 미분이 일어난다면, 이 MagicBox는 sampling distribution에 대한 정확한 gradient를 내놓습니다. MagicBox는 두 가지 성질을 가지는데, 이는 뒤에서 자세하게 설명하겠습니다.

                                          $$ \nabla_{\theta}\square(\mathcal{W}_c) = \square(\mathcal{W}_c)\nabla_{\theta}\sum_{w\in \mathcal{W}_c}{\log(p(w;\theta))}$$

                                                                            $$ \square(\mathcal{W}) \rightarrow 1$$

MagicBox operator는 위의 특성을 가지기 위해 auto-diff library에서 다음과 같이 쉽게 구현 가능합니다.

                                                            $$ \square(\mathcal{W}) = \exp(\tau-\bot(\tau))$$

                                                              $$ \tau = \sum_{w \in \mathcal{W}}{\log(p(w;\theta)}$$

$$ \bot$$는 $$ \nabla_x\bot(x)=0$$이 되는 operator입니다. 이후에 어떻게 baseline을 통해 variance를 줄이는지에 대해 보입니다.

이번 chapter내에서 DiCE의 증명과 실험을 통해 정확성에 대해 보입니다. 또한, LOLA에 DiCE를 적용한 모습도 보입니다.