캐글, 산타 2020-사탕 지팡이 대회 결과 제출
A Simple Bandit Algorithm vs Random
캐글에서 개최된 산타 2020-사탕 지팡이 대회 참여한 경험을 공유합니다. 목표는 강화학습의 이론을 배우고 단계적으로 배운 이론을 대회 결과 파일로 구현 후 제출하는 것입니다.
Introduction
캐글에서는 전통적으로 매년 크리스마스에 산타 대회를 개최합니다. 20년 대회 이름은 "Santa 2020 - The Candy Cane Contest"입니다. multi-armed bandit 모델을 기반으로 한 강화학습 문제입니다.
"Santa 2020 - The Candy Cane Contest" 대회에 대해 간단히 알아보겠습니다.
2020년 산타마을의 사기가 코로나로 인해 많이 저하되었습니다. 사기를 올리기 위해 사탕 지팡이를 공급하기로 결정하고 이번 대회를 개최하게 되었습니다. 사탕 지팡이를 공급하기 위해서는 휴게실의 자판기를 이용해야 합니다. 자판기는 100대가 있으며 휴게실에는 사회적 거리두기로 2명의 엘프만이 들어갈 수 있습니다. 100대의 자판기는 한 번에 한 개의 레버만 당길수 있으습니다. 레버를 당기면 사탕 지팡이가 지급 되며 1 또는 0의 보상을 받게 됩니다. 고려할 점이 레버를 당길 때마다 알려지지 않은 보상 확률은 0.97의 비율로 감소합니다. 목표는 2000번의 레버를 당김으로써 보상을 극대화하는 전략을 마련하는 것입니다.
위 최적화 문제는 고전적인 MAB (multi-armed bandit) 문제입니다. 강화학습 첫걸음에 잘 설명되어있어 아래와 같이 발췌해 왔습니다.
강화학습에서 가장 단순한 형태의 문제는 n개의 손잡이(=arm)가 달린 밴딧(bandit), 즉 멀티 암드 밴딧(multi-armed bandit)입니다. 여기서 밴딧은 '손잡이가 n개인 슬롯머신'이라고 생각하면 쉽습니다. 각각의 손잡이는 다른 확률로 보상을 제공합니다. 에이전트의 목표는 시간의 흐름에 따라 가장 높은 보상을 제공하는 손잡이를 찾아내고 항상 이 손잡이를 선택함으로써 돌아오는 보상을 최대화하는 것입니다.
...
처음 강화학습에 대해 학습할 때 n개인 슬롯머신이 좋은 시작점이 되는 이유는 시간 의존성, 상태 의존성에 대한 고민할 필요가 없기 때문입니다. 손잡이가 n개인 슬롯머신에서 고려해야 하는 것은, 어떤 보상이 어떤 액션과 연관되어 있는지, 그리고 우리가 최적의 액션을 선택하도록 보장하는 것이 전부입니다. (정책=Policy)
정책은 주어진 환경의 어떤 상황에서 어떤 에이전트가 취하게 되는 일련의 액션을 기술합니다. 에이전트가 주어진 환경 내에서 최대의 보상을 얻는 정책을 최적의 정책으로 간주하게 됩니다.
[출처. 강화학습 첫걸음 - 2장 벤딧 문제 중]
ELLA 작가님이 이번 대회를 재미있게 그려주셨습니다. 바탕화면으로 해놓고 지칠 때마다 보면서 힘을 얻고 있습니다. 작가님 고맙습니다. ^^/
by ELLA
"Exploration vs. Exploitation Dilemma"의 Principles은 아래와 같습니다.
Principles
Naive(or Ramdom) Exploration : Add noise to greedy policy (e.g. Epsilon-greedy, SoftMax)
Optimistic Initialisation : Assume the best until proven otherwise
Optimism in the Face of Uncertainty : Prefer actions with uncertain values (e.g. UCB)
Probability Matching : Select actions according to probability they are best (e.g. Thompson sampling)
Information State Search : Lookahead search incorporating value of information
출처 : lilianweng.github.ioMAB(multi-armed bandit)는 Stationary or Nonstationary MAB로 구분됩니다. 보상값의 확률 분포가 시간이 지나도 변화지 않는 Stationary MAB로 시작하겠습니다. 문제를 단순화하고 단계적으로 하나하나 쉽게 접근하기 위해 "a simple bandit algorithm"을 구현해보고 캐글에 제출까지 해보겠습니다.
"a simple bandit algorithm"은 아래와 같습니다.
Reinforcement Learning An Introduction - Chapter 2: Multi-armed Bandits (2.4)대회 참여 후 캐글 노트북에서 구현해봅니다.
강화학습 환경인 kaggle_environments를 import 후 mab 환경을 생성합니다. 환경을 초기화해주고 env.run을 통해 생성한 Agent를 실행하여 경쟁하도록 합니다. 에이전트들은 파일로 만들어 아래와 같이 env.run의 인자로 넣어주도록 되어있습니다.
mab - kaggle environmentsrandom 에이전트는 아래와 같습니다. "%%writefile 파일명"으로 파일을 생성합니다. 이후 생성한 파일은 대회 결과 제출 파일로 사용됩니다.
random agent에이전트의 인자 값으로 observation과 configuration은 아래와 같이 대회 초기 설정값들로 설정되어있습니다. episodeSteps=2000으로 최대 레버를 당기는 횟수, reward(=보상) 1, 0으로 리턴됩니다. 해당 값은 계속 누적되게 되어있어 코드에서 차이를 계산하여 보상을 리턴해야 합니다. 그 외 decayRate = 0.97로 설정된 부분을 확인할 수 있습니다.
a simple bandit 에이전트를 구현 후 파일로 생성합니다.
(수정이 필요한 부분이 있으면 github에 이슈 등록 부탁드립니다.)
a simple bandit agent"a simple badit" 에이전트를 대회 결과로 제출 후 같은 수준의 캐글러가 제출한 에이전트와 경쟁해보니 Public Score가 479점이 나왔습니다. 참고로 "Epsilon-greedy", Thompson sampling로 구현한 에이전트는 700점 대가 나오는 것을 확인할 수 있습니다.
전체 코드는 "Santa 2020 - beginner (/w a simple bandit)" 또는 github에서 확인 가능합니다.
Public Score - simple bandit algorithm : 479.4 점multi-armed bandit 문제를 단순화하여 a simple bandit 알고리즘으로 산타 대회 결과를 제출해보았습니다. 성능이 좋은 알고리즘을 단계적으로 적용하여 대회 상위권에 도전해보도록 하겠습니다.
by ELLA