Machine Learning

CS234의 마지막 강의인 15-16강을 들었습니다.

15강에서는 High-confidence Off-Policy Evaluation이라는 (아마도 교수님의 연구실에서 다뤘던 토픽인) 최근의 연구 결과를 다루고 있는데, 대략 새로운 policy의 expected return의 lower confidence bound를 계산함으로써 monotonic improvement를 일정 수준으로 보장하는 학습의 안전성을 얻기 위한 방법이라고 볼 수 있을 것 같습니다. 기초를 배우는 입장이라서 대충 이런게 있구나 하고 넘어갔습니다.

16강에서는 Monte-Carlo Search Tree에 대해 다루고 있습니다. 우리가 흔히 알고 있는 게임 트리와는 달리, 전체 스페이스를 탐색하는 것이 아니라, 일정 수의 시뮬레이션만을 수행하고, 일부 트리에 해당하는 이 데이터를 기반으로 결정을 내립니다. 또한, UCB1과 마찬가지로, upper confidence bound를 적용해 액션을 결정하여 exploration/exploitation을 수행합니다 (UCT). 결과적으로는 마치 UCB1이 적용된 MAB를 각 node마다 실행하는 느낌입니다. MCTS는 이 이름을 가지기 전부터 바둑에서의 강력함을 증명해오다가 DNN을 접목한 AlphaGo에까지 적용되었습니다. MCTS의 주요 페이퍼들과 AlphaGo에 관련한 페이퍼들을 읽어볼 생각입니다.

이로서 1월 중순 무렵에 시작했던 CS234 Reinforcement Learning 강의와 이에 관련한 Sutton & Barto 책을 통한 공부를 마쳤습니다. 주요 RL 알고리즘을 구현해보는 동시에, 공부를 시작할 때 사둔 Foundations of Deep Reinforcement Learning을 읽어볼 생각인데, 효과적인 학습을 위해 다른 토픽으로 1-2달 정도 넘어갔다가 진행해 볼 생각입니다.

Exploration을 다루는 CS234 11-13강을 들었습니다.

우선 MDP에 비해 상대적으로 단순한 multi-armed bandits 문제와 regret과 같은 framework의 formulation으로 시작합니다.

이어서, 불확실한 상황에서 탐색을 통한 정보를 얻는 것의 가치를 높게 보는 Optimism in the face of Uncertainty 원리로부터 UCB1 알고리즘을 설명합니다. UCB 알고리즘들은 여러 경로로 접해왔지만, 이러한 원리 하에서 이해하게 된 것은 처음입니다. 또한, 각 arm들을 확률변수로 보고 Hoeffding’s Inequality를 통해 모르는 정보들을 제거하고 UCB1 알고리즘을 유도하는 과정도 꽤 흥미로웠습니다.

다음으로 reward distribution에 대해 Bayesian inference를 이용하는 Bayesian Bandits을 배우게 됩니다. Bayesian inference는 분석적으로 계산하기 까다로운데 conjugate prior를 통해서 이를 가능하게 하는 것도 처음으로 알게되었습니다. Bayesian bandits 하에서 Probability matching 접근을 하는 대표적인 알고리즘으로 Thomson Sampling이 다루어집니다. Thomson Sampling 알고리즘에서는 posterior로부터 sampling을 하고 이에 기반해 action을 결정하고, 이에 따른 reward를 다시 posterior에 반영하는 단순한 휴리스틱으로 되어있는데, 경험적으로 매우 잘 동작한다고 하네요.

마지막으로 PAC (Probably Approximately Correct) 개념과 이에 해당하는 알고리즘을 배웁니다. Supervised Learning에서와 비슷하게, 일정 이상의 확률로 optimal value로부터 일정 이하의 차이가 보장되는 것을 말합니다. 이러한 알고리즘의 예로 MBIE-EB를 들고 있고 어떤 RL 알고리즘이 PAC을 만족하기 위한 조건들도 다룹니다.

이번에는 강의도 쉽지 않았고 Bayesian Inference에 대해 정확하게 이해하기 위해 별도로 공부를 해야만 했습니다. exploration 방법들을 MDP에 적용하는 내용도 있었지만 이번에는 skip했습니다. 이번에 배운 내용들을 Bandit Algorithms 책과 인터넷에서 다시 한번 복습을 해보고 나머지 강의들을 들을 예정입니다.

Policy Search를 다루는 CS234 Reinforcement Learning 9-10강을 들었습니다.

9강은 Sutton Chapter 13에서도 다루고 있는 REINFORCE with baseline에 관한 내용입니다. 10강에서는 이러한 Policy Gradient method에서 monotonic improvement를 보장하기 위해서 step size를 결정하는 문제를 다룹니다. 여기서 매우 유명한 TRPO (Trust Region Policy Optimization) 알고리즘에 이르는 과정을 배우게 됩니다. Policy gradient의 iteration에서 새로운 policy의 value를 알 수는 없지만, lower-bound를 계산할 수 있고, 이러한 lower-bound가 개선되는 것을 보장할 수 있는 objective function과 constraint를 제안합니다. 이를 통해서 policy value를 최대화하면서 안정적인 학습이 이루어질 수 있도록 step size를 결정하는 알고리즘이 TRPO 알고리즘입니다.

계산이 어려운 문제를 계산 가능한 문제로 전환하고 이로부터 실용적인 알고리즘을 제안하는 과정이 ‘아름답다’고 밖에는 말할 수 없는 흥미로운 토픽이었습니다.

RL Introduction Chapter 13 Policy Gradient Methods를 읽었습니다.

Value function을 approximation해서 optimal policy를 찾아내는 접근과 달리, parametrized policy를 정의하고, parameter에 대한 policy performance의 gradient를 통해 optimal policy를 직접 찾아내는 방법입니다.

Policy Gradient Theorem에 기초해서 REINFORCE라는 알고리즘을 얻는 과정을 설명하고, variance를 줄이기 위해 baseline을 도입한 REINFORCE 알고리즘을 얻는 과정도 배울 수 있었습니다.

이어서 Actor-Critic method도 소개하는데 REINFORCE with baseline 알고리즘에서 baseline으로 state-value function을 사용해서 action의 결과를 평가하기 위한 기준 역할을 합니다. state-value function은 semi-gradient TD를 통해서 학습하고, REINFORCE 알고리즘에 자연스럽게 통합될 수 있습니다.

Policy Gradient Method들은 stochastic한 policy를 자연스럽게 학습할 수 있고, exploration을 얼마나 할지도 학습할 수 있는 장점이 있습니다. 또한, action space가 연속적일 때도 적용할 수 있습니다.

이 책에서 다루는 전통적인 RL 방법들에 대해서는 어느 정도 기초가 마련된 것 같고, 당장은 CS234 강의를 마저 듣고, 그 다음에는 Deep Reinforcement Learning 방법을 공부하기 위한 책으로 넘어가볼까 합니다.

Reinforcement Learning 7, 8강을 들었습니다. 각각 Imitation Learning과 Policy Search의 도입부를 다루고 있습니다.

Imitation Learning은 전문가의 시연로부터 어떻게 모방할 수 있는가의 문제를, 전문가의 state, action 샘플로부터 reward function을 추정하거나 이로부터 optimal policy를 학습함으로써 풀고 있습니다.

그동안 value function을 학습해서 policy evaluation 및 control을 해왔던 value-based method를 다뤄왔습니다만, 8강에서는 policy 자체를 학습하는 접근을 다루기 시작합니다. policy 자체를 파라미터를 이용해 표현하고, policy의 value를 최대화하는 파라미터를 찾는 최적화 문제로 다룹니다. 최적화 방법에는 여러가지가 있지만, Likelihood Ratio / Score Function Policy Gradient에 temporal structure를 도입함으로써 결국 잘 알려진 REINFORCE 알고리즘을 얻게 되는 과정을 설명합니다.

다음 강의들을 듣는 동시에, Intro to Reinforce Learning의 Chapter 13도 함께 읽어볼 예정입니다.

Chapter 9 On-policy Prediction with Approximation을 읽었습니다.

state space가 매우 크고 이에 따르는 데이터가 큰 문제에 대해 샘플로부터 value function을 approximation하는 문제로 넘어가게 됩니다. state를 대표하는 feature들로부터 value를 계산할 수 있는 function의 weight를 샘플들을 통해서 찾는 supervised learning 문제로 바라봅니다.

여기서부터는 SGD라든가 여러 basis function들을 기반으로 하는 linear method들, non-linear method로서의 neural network 등의 일반적인 방법들이지만 그동안의 RL 연구에서 자주 활용된 방법들을 소개하고 있는 것 같습니다. 이 과정에서 convergence 문제라든가 dimensionality reduction에 관련한 이슈도 다루고 있습니다. coarse coding이나 tile coding 등은 처음 들어본 것이라서 살짝 흥미로웠습니다. 현재는 deep learning이 트렌드가 되었기 때문에 긴장감이 좀 떨어지지만, 그래도 기존의 접근들을 기반으로 새로운 접근들을 쌓아올라가는 면들이 현재도 있는 것 같아서 도움이 될 수도 있겠다는 생각 정도는 들었습니다.

이어서 Atari 관련한 DeepMind 페이퍼들을 좀 읽어볼 예정입니다.

CS234 Reinforcement Learning 강의 6강까지 들었습니다. function approximation으로 넘어갔고, 아타리 게임을 플레이하는 것으로 화제가 되었던 DeepMind의 DQN까지 배웠습니다. function approximation + off-policy에서의 convergence 문제 때문에 관심이 시들하다가 DQN 때문에 다시 많은 관심을 얻게된 것 같네요. 그나저나 TRPO와 PPO의 주저자인 J. Schulman이 OpenAI의 cofounder인 것도 이 강의를 통해 알게 되었네요.

유튜브에 공개되어있는 2019년 겨울의 CS234 Reinforcement Learning 강의 4강까지 들었습니다. 3강을 듣다가 이해하기가 좀 어려워서 RL: An Introduction (Sutton and Barto)의 관련 chapter들을 먼저 읽고나니 강의를 훨씬 편하게 들을 수 있었습니다.