강화학습12 Contextual Bandits - LinUCB 금번 포스팅을 시작하면서 multi-armed bandit 포스팅의 초반부를 상기시켜보겠습니다. Bandit을 크게 stochastic, non-stochastic으로 분류했고, 그 다음 분류는 context-free, context로 분류했습니다. 지금까지 살펴본 ε-greedy, UCB, Thompson Sampling의 알고리즘은 context-free에 해당하는 방법이었습니다. 즉 action을 선택하기 앞서 주어진 환경을 전혀 고려하지 않고 매시도 독립적으로 의사결정을 해왔습니다. 이번 포스팅에서는 context를 고려하는 contextual bandits, 그 중에서도 가장 유명한 Li, Lihong, et al., 2010의 LinUCB를 살펴보겠습니다. 어떠한 형태의 co-work도 환영합.. 2021. 1. 30. Bayesian Bandits - Thompson Sampling 이번 포스팅은 Bayesian Bandits을 살펴보려고 합니다. 특히 Bayesian Bandits 중 대표적인 알고리즘인 Thompson Sampling을 부제로 선정했습니다. :) On The View of Bayesian Frequentist는 확률을 상대빈도의 관점으로 바라보지만, Bayesian은 확률을 어떤 사건에 대한 믿음의 정도로 해석합니다. 동전을 던져서 앞면이 나올 확률에 대해서 Frequentist는 "10000번 던지면 앞면이 5000번 나온다."고 해석하는 것이고, Bayesian은 "경험에 의하면 앞면이 나온다고 50% 믿는다."라고 해석합니다. Prior vs. Posterior Probability? 위 예시에서 Bayesian의 멘트 중 "경험에 의하면"이라는 문구가 있습.. 2021. 1. 14. Stochastic Bandits (3) - UCB (Upper Confidence Bound) 이번 포스팅은 Stochastic Bandits 그리고 Frequentists 관점의 연속입니다. 직전 포스팅에서는 reward의 확률 분포를 Point Estimation하는 관점에서 살펴보았고, 대응하는 알고리즘으로는 ε-greedy를 살펴보았습니다. 이번 포스팅에서는 Interval Estimation하는 관점의 algorithm인 Upper Confidence Bound Algorithm (UCB Algorithm)이 메인입니다. Point Estimation vs. Interval Estimation Frequentist의 확률 철학은 많은 시도를 반복했을때 사건이 발생한 상대빈도를 의미한다고 했습니다. 이러한 상대빈도를 추청하는 방식에는 크게 두가지 방식이 있는데, Point Estimatio.. 2021. 1. 3. Multi-Armed Bandits 곧 추천시스템(Recommendation System)에서 활용가능한 관점의 Multi-Armed Bandits에 관한 포스팅이 하나둘 써내려갈 예정입니다. 많은 관심부탁드립니다. 많은 분들이 공감하시겠지만, $\epsilon$-greedy, UCB (Upper Confidence Bound), TS (Thompson Sampling)등 토막토막의 MAB관련된 글들은 영문이든, 국문이든 구글에서 쉽게 찾아볼 수 있지만, MAB의 큰틀을 제시해줄 수 있는 문서가 부족합니다. 앞으로 이어질 포스팅 하나하나를 연결하고 큰 밑그림을 그려가는 작업이 순탄하지는 않았고, 부족한 점이 많을 것으로 생각됩니다. 그럼에도 불구하고 많은 피드백을 주시면 정말 감사하겠습니다. ㅎㅎ 곧 찾아뵙겠습니다. 감사합니다:) yjjo.. 2020. 11. 26. Tabular Temporal Difference Learning - Sarsa, Q-learning, Double Q-learning Reinforcement Learning/Tabular Methods에 있는 이전 글에서 Dynamic Programming, Monte Carlo Learning을 알아보았습니다. 위 두 가지 방법은 역사적으로 중요한 방법으로, 각각의 장점을 취한 방법이 Temporal Difference Learning (TD)입니다. 또한 강화학습에서 가장 중요한 방법과 학습의 컨샙은 TD라고 할 수 있습니다. 이번 포스팅에서는 Tabular Methods 세 가지 방법 중 마지막인 TD에 대하여 살펴보겠습니다. Temporal Difference Learning DP 와 MC의 장단점 DP 장점: 최종 상태에 도달하지 않더라도 그때 그때 발생하는 보상을 이용하여 가치함수 업데이트가 가능하다. 단점1: Model-.. 2019. 11. 11. Monte Carlo Methods in RL (2) 이번 포스팅에서는 저번 포스팅에 이어서 몬테카를로 방법에 대해 알아보겠습니다. 특히 저번 포스팅에선 개념과 on-policy 방법이 주였다면, 이번 포스팅에서는 off-policy 방법을 살펴보겠습니다. Monte Carlo Iteration (Off-policy) Off-policy Learning Off-policy Learning은 목표 정책 (Target Policy, $\pi$)와 행동 정책 (Behavior Policy, $b$)를 구별하여 학습하는 방법을 일컫습니다. 즉 에이전트가 움직일 때는 행동 정책을 따라서 움직이지만, 거기에서 얻어진 보상으로는 목표 정책을 학습하는 것 입니다. 행동 정책을 별도로 운용함으로써 탐색과 활용의 균형을 유지할 수 있습니다. Off-policy learnin.. 2019. 11. 1. Monte Carlo Methods in RL (1) 이번 포스팅에선 Monte Carlo 추정법을 이용하여 가치 함수를 추정하는 방법을 소개하고자합니다. 개요 이전 포스팅에서 DP를 이용하여 가치함수를 계산하는 방법을 살펴보았습니다. 몬테카를로 방법에 들어가기 앞서 왜 우리가 공부해야되는지 가벼운 동기부여를 하겠습니다. 바로 앞문장에 '계산'이라는 말에 하이라이트되어 있듯 엄연히 DP는 주어진 정책과 모델을 알고있는 상황에 대하여 가치함수를 계산한 것이기 때문에 '학습'을 했다고 보기 어렵습니다. 다시 바로 앞 문장에선 모델을 알고 있는 상황을 대전제로 했습니다. 즉, 모델을 알고 있어야만 DP로 가치함수를 계산할 수 있습니다. 하지만 실제로 대부분의 상황에선 모델을 알 수 없기 때문에 적용하기 힘듭니다. 진정한 의미의 학습과 모델을 모르는 상황에서도 가.. 2019. 10. 30. Dynamic Programming In RL (1) 이전 포스팅에서 강화학습이 무엇인지 살펴 보았고, 이를 MDP로 정의할 수 있음을 살펴 보았습니다. MDP로 정의하는 이유는 가치 함수를 이용하여 순차적 의사결정을 하는 강화학습 문제를 풀기위함이었습니다. 즉 우리가 강화학습문제를 해결하기 위해선 가치함수의 값을 알고 있어야 합니다. 가치함수를 추정하는 방법은 상태공간($\mathcal{S}$)의 크기에 따라서 tabular method와 approximation method 두 가지 방법이 존재합니다. Tabular method는 기본적으로 각 상태에 대한 가치함수 값을 모두 저장하고 있습니다. 이에 따라 상태 공간 크기가 너무 크면 각 상태에 대한 가치함수의 값을 저장하는데 한계가 있어 tabular method를 적용하기 어렵고, 해당 경우에는 ap.. 2019. 10. 11. Multi-Armed Bandit for RL(3) - Gradient Bandit Algorithms 이번 포스팅에서는 Gradient Bandit Algorithms에 대해 알아보겠습니다. 내용은 심플한데 업데이트 알고리즘을 유도하는 과정이 조금 복잡합니다. 유도하는 과정을 이해하지 않더라도 충분히 적용가능하니 유도하는 내용은 취사적으로 읽어보면 좋을 것 같습니다. Gradient Bandit Algorithm MAB(2)에서는 action value 이용한 행동 선택 전략을 알아봤습니다. 물론 좋은 방법이지만 당연히 action value가 아닌 다른 방법으로도 행동 선택 전략을 수립할 수 있습니다. 또 다른 대표적인 행동 선택 전략은 선호도(preference)를 이용하는 gradient bandit algorithm입니다. $H_{t}(a)$를 $t$ 시점에서 행동 $a$의 선호도로 정의하겠습니다.. 2019. 9. 17. Multi-Armed Bandit for RL(2) - Action Value Methods 이번 포스팅에선 이전 포스팅에서 다룬 MAB의 행동가치함수기반 최대보상을 얻기위한 행동선택법을 취하는 전략을 살펴보겠습니다. Action Value Methods 큰 제목은 action value methods입니다. 즉 행동가치함수 기반 행동을 취하는 전략의 모음입니다. 기본적으로 action value methods는 행동가치가 큰 쪽으로 행동을 취합니다. 행동가치함수가 $t$ 시점에서 $Q_{t}$로 추정되었다는 대전제 아래 차근차근 살펴보겠습니다. Greedy Action Selection 뼈대가 되는 방법은 탐욕 행동 선택법(greedy action selction)입니다. 탐욕 행동 선택법은 각 시점에서 기대보상이 최대인 행동을 취하는 전략 방법으로 아주 심플합니다. 가볍게 수식으로 정리하면,.. 2019. 9. 15. Multi Armed Bandit for RL(1) - 개요 이번 포스팅에서는 Multi Armed Bandit (MAB)을 다루려고 합니다. 다만 여기에서는 Reinforcement Learning으로 나아가기 위한 관점에서 서술합니다. (철저한 MAB 관점의 글은 이곳에서 확인할 수 있습니다.) MAB은 엄밀하게 강화학습은 아니지만, 강화학습으로 나아가기 위한 과도기적 방법이고, 적용이 간편하여 널리 사용되고 있습니다. Multi Armed Bandit (MAB) MAB 정의 MAB 정의는 굉장히 심플합니다. 아래 그림과 같이 살펴보겠습니다. MAB는 위 상황으로부터 출발합니다. k개의 슬롯머신이 있는데 에이전트는 각 시도 마다, k개중 단 1개의 슬롯을 당겨 최종적으로 최고의 보상을 얻고 싶은 상황을 말합니다. 다시 말하면 에이전트가 1000번의 게임을 하는.. 2019. 9. 15. 강화학습개요 이번 포스팅에선 강화학습이 무엇이고, 머신러닝의 큰 틀 안에서 어떤 포지션을 잡고 있는지 살펴보겠습니다. 강화학습개요를 시작으로 강화학습의 전반적인 내용을 다룰 생각입니다. 강화학습개요 강화학습이란? 강화학습(Reinforcement Learning)은 머신러닝의 한 영역으로 행동심리학에서 영감을 받은 방법입니다. 어떤 환경(Environment)안에서 행동의 주체인 에이전트(Agent)가 선택 가능한 행동(Action)들 중 보상(Reward)을 최대화하는 행동 또는 행동 순서를 선택하도록 학습하는 방법입니다. (Wikipedia, Reinforcement Learning) 머신러닝의 한 영역 치고는 새롭게 등장하는 용어(환경, 에이전트, 행동, 보상)가 많아서 잘 와닿지 않을 것 같습니다. 이번 포스.. 2019. 9. 12. 이전 1 다음
