Bandit

강화학습은 무엇인가?

현재 state에서 어떤 action을 하면 cummulative reward를 최대화 할 수 있는지를 찾는 알고리즘이다.

중요한 건 현재 상황에서 가장 좋아보이는 action을 고르는 것과 다양한 state action을 탐험해 local maxima에 빠지지 않게 하는 exploration-exploitation의 균형을 잘 맞추는 것.

Bandit은 일반적인 강화학습(RL)의 단순한 버전이다.

Bandit Problem의 대표적인 예시는 도박장의 여러 슬롯머신(slot machine) 중 어떤 것을 선택할지 결정하는 것이다.

기계 1번이든 기계 2번이든 내가 직전에 작동시켰다고 다음에 777이 나올 확률이 변하지 않는다. 즉, 매 시행이 독립적이다.

매 action선택이 timestep과 무관하게 독립적이라서 action이 자신의 상태(state)에 영향을 주지 않고, 당장 바로 앞의 single step reward만 관찰한다.

그래서 Bandit Problem을 Single step decision problem이라고도 한다.

Contextual Bandit

조금 더 복잡한 상황을 커버하기 위해 상태 정보를 제공하고 싶으면 contextual bandit이라는 분야도 있다. 이때는 agent의 상태에 따라 action이 달라야 최적의 해가 될 수 있어서 어떤 상태가 영향을 준다. 하지만 bandit 문제이기에 single step (action,reward)만 고려하고, 매 시행은 독립적이어서 action이 그 상태를 변화시키지 않는다. 그래서 일반적인 MDP 랑은 다르게, state를 따로 두지 않고 context라 표현한다.

cbandit) context(state)에 따라 최적의 action이 다르다 -> context는 time step 이나 action과 무관하게 유지된다

MDP) state에 따라 최적의 action이 변한다 -> action에 따라 next state가 변할 수 있다 -> 다른 state에선 다른 action이 최적이다

현재 상황이 다양할 수 있고, state가 timestep이나 이전 action에 무관한 경우 contextual bandit을 이용해 문제를 모델링할수도 있다.