[2] Multi-arm Bandits

Reinforcement Learning : An Introduction - [2] Multi-arm Bandits

Chapter 2. Multi Arm Bandits

Multi Arm Bandits Problem

먼저 강화학습에 대한 전체적인 통찰을 얻기 위한 1 state problem 인
multi arm bandits problem 부터 시작해보자.

카지노에 승률이 다른 슬롯머신(bandits)들이 있고 이들중 돈을 걸고 레버(arm)을 내려야한다면?
또한 이 슬롯머신들의 승률이 시간에 따라서 변화한다면?
어떻게 하는 것이 가장 많은 돈(rewards)을 얻는 방법인가?

Evaluation feedback

강화학습을 다른 알고리즘들과 구분하는 가장 큰 차이점 중 하나는,
학습 정보를 사용하여 actions 를 "평가" 하는 것이지, "지시" 하지 않는 다는 것이다.

이로 인해서, exploration(탐색) 에 대한 필요가 생기고, trial-and-error search for good behavior 를 하게 된다.
따라서 강화학습은 Evaluation feedback 을 하는 것으로 볼 수 있다.

• Evaluation feedback

: how good the action taken is, but not whether it is the best or the worst action possible.

-> Basis of methods for function optimization, including evolutionary methods.

-> depends on entirely on the action taken.

• Intructive feedback

: indicates the correct action to take, independently of the action actually taken.

-> Supervised learning. Pattern classification,

-> indendent of the action taken

Exploiting , Exploring

그렇다면, action 을 우선 선택한 후에 평가하게 된다는 말인데, action 을 선택하기 위한 방식은 어떻게 결정해야할까?

먼저 가장 좋은 reward 를 줄 것이라고 예상되는 action 을 greedy action 이라고 부른다.

• greedy action

: action whose estimated value is greatest

하지만 현재의 정보로 가장 greedy 한 action 만이 최종적으로(long run) total reward가 좋은 선택이라고 볼 수 없는데, 때문에 exploring 과 exploiting 의 선택의 문제가 발생하게 된다.

• exploiting

: select greedy action

• exploring

: non greedy action

explore, exploit 의 발란싱 결정은 정확한 값의 추정과 불확실성, 남아있는 스텝에 의존한다.

이에 발란싱에 관련된 수학적인 수식이 존재한다. 하지만 대부분의 방식은 stationary 나 priory knowlege 에 대한 강한 가정을 하며 실제에서는 이를 위반하거나 불가능할수 있다. (따라서 후속 챕터에서 이 방식에 대한 optimality 와 bounded loss의 가정은 편리한 측면이 있다.)

N armed bandit prob. 에서는 몇가지 간단한 balancing methods 를 보일 것이며 이것이 항상 exploit 하는 방식(greedy)보다 더 잘 작동한다는 것을 보일 것이다.

Action Value 추정 방법

그렇다면 exploiting 의 기준이 되는 최대 reward 값의 지표인 action value 는
어떤 방식으로 구한 지표로 추정해야 할까? 가장 대표적인 예로 sampling average method가 있다.

• Sampling Average Method

$$
Q_t(a)=\dfrac{R_1+R_2+...+R_N}{N_t(a)}
$$

$$
N_t(a) \Rightarrow \infty , Q_t(a) \Rightarrow q(a)
$$

하나의 action value 추정 방법으로 sampling average method 를 쓸 수 있다.
action a 를 선택할때의 추정된 value 값인 $Q_t(a)$ 값은,
해당 action a 를 선택한 횟수 $N_t(a)$ 와 얻었던 reward 를 평균 내는 것이다.
이는 하나의 방법일 뿐이므로 반드시 최적 추정 값은 아니다.

Action Selection Rule

위의 Action Value 를 추정 하고 난 뒤, 그 값들을 참고하여 어떤 action 을 선택할 것인지를 정해야한다.

• greedy method
  $$
  A_t = {argmax}_{a}Q_t(a)
  $$

가장 간단한 action selection rule 은 가장 높이 추정되는 action value 인 action 을 선택하는 것으로, 다시말해서 step t에서 가장 greedy 한 action 을 선택하는 것이다.
이는 샘플링 타임이 소요되지 않으며 즉각적으로 maximize immediate reward 를 선택하게 된다.

• $\epsilon$-greedy method

반면 작은 확률로 $\epsilon$ 만큼 random 하게 같은 확률로 독립적으로 모든 액션중에서 선택하는 방식을
$\epsilon$-greedy methods 라고 부른다. $\epsilon$ 확률만큼 최적의 선택이 아닌 값을 random 하게 선택한다.

이는 확률적으로 선택을 하게 되지만, $N_t(a)\rightarrow\infty$ 할때, $Q_t(a)\rightarrow q(a)$ 로 수렴을 보장한다.
이때 optimal action 을 선택할 확률은 1-$\epsilon$으로 수렴한다.

결과에서 초반에는 greedy method 가 약간더 빠르게 향상되었지만, 후에는 leveled off 되었다.

$\epsilon$-greedy method 가 결국적으로 greedy method 보다 좋은 성능을 낱아내었으며 이는 지속적인 exploration 때문이다.

$\epsilon$=0.1 방식은 조금더 일찍 optimal 값을 찾아냈지만 결국적으로는 $\epsilon$ =0.01 방식이 느리지만 더 좋은 성능을 나타내었다.
$\epsilon$-greedy 방식은 task 에 따라 다른 결과를 나타내게되며, n=1인경우에 더 noisy 한 reward 는 더 많은 exploration을 요구하게된다.

하지만 reward variance 가 0 인 경우, greedy method 는 각 action 에 대한 true value 를 알 수 있게 되고 이 경우에는 greedy method가 항상 가장 좋은 performance 가 되게 된다.

또한 deterministic case임에도 non-stationary case 의 경우는 true values of actions 가 시간에 따라서 변화하므로, 이 경우에는 exploration이 필요하게 되고 이때는 non-greedy actions이 greedy action 보다 낫게 된다.

이처럼 exploration 과 exploitation 은 balancing 은 중요한 문제이다.

Incremental Implementation

연산 로드를 줄이기 위한 incremental 방식

$$
Q_t(a)=\dfrac{R_1+R_2+...+R_N}{N_t(a)}
$$

을 이용한 sampling average 의 경우 $R_1,R_2,…R_N$ 의 저장으로 인한 momery 와 computational requirement 가 증가하게 된다. 따라서 더 적은 수의 파라메터를 이용하기 위하여 incremental update formulas 를 이용하게 된다.

• Incremental Update Formulas

$$
Q_{k+1}=\dfrac{1}{k} \sum_{k=1}^k R_i $$

$$
= \dfrac{1}{k} ( R_k + \sum_{k=1}^{k-1} R_i)
$$

$$
=\dfrac{1}{k}(R_k + (k-1)Q_k + Q_k - Q_k)
$$

$$
=\dfrac{1}{k}(R_k + kQ_k-Q_k)
$$

$$
=Q_k+\dfrac{1}{k}[R_k - Q_k]
$$

$$
NewEstimate\leftarrow OldEstimate +Stepsize [ Target - OldEstimate]
$$

$[Target - OldEstimae]$ 는 추정상의 에러값을 나타낸다. Target 은 나아가야할 방향이며, 이는 noisy 할 수 있다.

여기서 step size-parameter 는 $\dfrac{1}{k}$ 이며 이 책에서 step size-parameter 는 $\alpha$ 로 표기하므로 $\alpha=\dfrac{1}{k}$ 이다.

Tracking a Nonstationary Problem

Nonstationay -> Step-size control

** 이건 좀 확인해보자

non stationary problem 에서는 시간에 따라서 변화하는 효과를 고려할때
최근의 reward 에 과거보다 더 큰 weight 을 주는것이 좋다.
한가지 유명한 방법은 constant step-size parameter 를 사용하는 것이다.

• Constant Step-Size Parameter

Where the step-size parameter $\alpha$ $\in$(0,1] is constant,

여기서 $\alpha(1-\alpha)^{k-i}$ 는 $R_i$ 에 의존하는 weight 이며 k-i 는 how many rewards ago 였는지를 반영한다.

사실 이 weight은 exponentially decays 하게 되는 데 이는 1-$\alpha$ 의 지수승 때문이다. 이는 따라서 때때로 exponential, recency-weighted average (weight 의 합이 항상 1이 되기 때문)라고 불린다.

• Changing Step-Size parameter.

때때로는 변화하는 step-size parameter 를 사용하는 것이 편리한데,

$\alpha_k(a)=\dfrac{1}{k}$ 는 큰수의 법칙에 의해 수렴을 보장하나 모든 {$\alpha_k(a)$}에 대해서 이와 같은 수렴을 보장하지 않는다.

가장 잘 알려진 stochastic approximation 이론은 확률 1 의수렴을 아래와 같이 보장한다.
$$
\sum_{k=1}^\infty \alpha_k(a)=\infty, \sum_{k=1}^\infty \alpha_k^2(a)<\infty
$$

첫번째 조건은 step이 충분히 크다면 초기 조건과 random 섭동을 극복할 수 있음을 뜻하며
두번째 조건은 결국적으로 step이 감소하여 수렴하게 됨을 뜻한다.

Constant step size parameter 인 $\alpha_k(a)$=$\alpha$ 의 경우는 수렴성을 보장할 수 없는데, 지속적으로 변화하는 반응을 최근에 받은 rewards 에 따라서 생성하기 때문이다. 하지만 이는 오히려 nonstationary environment 에 적합하게 된다.

Optimistic Initial Values

exploration을 증가 시키는 방법 optimistic initial values

위에 언급된 방식들의 경우 초기 값에 영향을 받는다. 통계학적인 설명으로 그들의 초기 추정 값에 bias 되어 있다.
sampling average 방식에서는 이 편향은 모든 action 이 적어도 한번씩 선택됨에 따라 사라지게 된다.

하지만 constant step-size 방식에서는 이 편차는 지속적으로 줄어들기는 하지만 남아있게 된다.

실제로 이런 편차는 문제가 되지 않는데, 이는 오히려 매우 유용하다.
초기 추정은 user 에 의해서 반드시 설정되어야 하는 값이다. (모두 0으로 설정할 지라도)

down side , upside -> 이거뭔지 체크

이는 선행지식을 제공하는 쉬운 방법을 제공한다. 어떤 보상의 수준이 예상되는 지에 대한.
초기 action 값은 exploration 을 encouraging 하는 쉬운 방법으로 사용 될 수 있다.

초기 action value 들이 모두 0이 아닌 +5로 setting 되어 있다면 (우리가 10-armed bandit 에서 그랫듯이)

이는 wildly optimistic 하다. 이 optimism 은 action-value 방식을 더 explore 하도록 장려한다.

(cf. q(a) 는 N(0,1) 로 세팅 되어 있다.)

이 그림에서 10-armed bandit testbed 에서의 각방식의 성능을 확인할 수 있는데

greedy method using $Q_1(a)=+5$ for all a 와 $\epsilon$-greedy method with $Q_1(a)=0$ 의 대조를 보여준다.

초기에 optimistic method 는 더 나쁜 성능을 나타내지만 결국적으로 더 나은 성능을 보여준다.

이는 exploration 이 시간에 따라 줄어들기 때문이다.
우리는 이 방식을 encouraging exploration optimistic initial values. 라고 부른다. 이 단순한 trick 이 stationary problems 에서 꽤 효과적으로 여겨진다.

이는 일반적으로 사용되는 exploration 을 증가시키는 방식이다.
하지만 이 방식은 nonstationary problems 에서는 적합하지 않는데,
이는 exploration 이 inherently temporary 하기 때문이다.

만약, task 가 시간에 따라서 변화한다면 renewed need for exploration 이 필요하게 되는데 이 방식은 도움이 되지 않기 때문이다.

실제 initial state 에 집중하는 어떠한 방법도 일반적으로 nonstationary case 에 도움이 잘 되지 않는데, the beginning of time 은 한번의 수행으로 굳이 집중해야할 필요가 없으며 sampling avegrage 방식에서는 모든 sequent rewards 를 같은 weight 으로 나누기 때문이다.

그럼에도 불구하고 이 방식은 매우 간단하며 몇가지 방식은 종종 실제에서 쓰이곤 한다. 이 책의 나머지에서는 우리는 몇가지 간단한 exploration technique 을 더 다룰 것이다.
-> check more

Upper - Confidence - Bound Action Selection

exploration 을 random 하게 말고 조금 더 optimal(greedy)게 해보자.

Exploration 은 action values 에 대한 추정의 불확실성 때문에 꼭 필요하다.

greedy actions 는 현재에서 가장 최선의 값을 보지만, 다른 action 들이 장기적 관점에서 더 좋은 선택일 수 있다.

$\epsilon$-greedy action selection 은 non-greedy action 을 시도할 수 있으나 매우 greedy 에 적합한 환경이나

적은 uncertain 이 있는 환경에서 preference 가 없다는 문제점 이 있다.

• Upper confidence bound (UCB)

: non-greedy actions 을 action value 추정이 얼마나 maximal 에 가까운 지, 또는 uncertainties 가 얼마나 있는지에 따라서 선택하는 것이 필요할때, action 을 선택하는 방법중 하나인 UCB는 아래와 같은 지표를 사용하는 것이다.

$$
A_t = {argmax}_a[Q_t(a)+c\sqrt{{lnt}\over{N_t(a)}}]
$$

위의 Greedy selection

$$
A_t = {argmax}_{a}Q_t(a)
$$

와 비교해보면 루트항이 exploration을 조정하는 항임을 알 수 있다. (t=전체 선택횟수, $N_t(a)$=t에서 a의 선택횟수)

여기서 lnt 는 t에 대한 log 지표를 반영하며, c 는 exploration 의 정도를 조절한다.

($N_t(a)$= 0 일시 a 는 maximizing action 임뜻한다.)

root 항은 uncertainty 와 a 값의 추정의 variance 를 나타내는 부분이다. maxed over 되는 값 = possible true value of action 은 일종의 upper bound 로 작용한다. c parameter 는 신뢰도의 수준을 나타낸다.

매번 a 를 선택해감에 따라서 uncertainty 는 낮아져가게 되고 $N_t(a)$가 증가하며 이를 반영한다.
반면 a 를 선택해감에 따라서 t 는 증가하게 되고, 이는 uncertainty estimate 가 증가함을 나타낸다.
자연로그를 사용한 이유는 증가분이 시간에 따라 작아짐을 반영하면서도 unbounded 되기 위해서이다.

​ Average performance of UCB action selection on the 10-armed bandit testbed.

위에 그림에서 UCB 알고리즘은 $\epsilon$-greedy action selection 보다 더 나은 성능을 보여준다.
초기에는 random 하게 아직 선택되지 않은 action들을 선택하기 때문에 e-greedy action 이 더 나은 성능을 보인다.

RL 에서의 또하나의 중요한 문제점은 non-stationary problems 이다.
다른 어려움은 state spaces 가 큰 경우를 다루는 문제이다. 특히 function approximation이 Part 3에서 다루어지는 이유이다. 여기에서 더 advanced 된 setting 을 다룰 것이며, 거기에는 ucb를 사용한 실제적 예가 알려져 있지 않다. (n-armed bandit 문제 외의 일반적으로 다른 강화학습 문제들에서 $\epsilon$-greedy 방법보다 성능이 좋지 않다.)

gradient bandits

action을 선택할때 gradient 한 preference를 이용하자

지금까지는 우리는 action values를 추정하는 방식에 대해서 배웠고, action을 선택하는 데에 그 추정을 사용하였다.
이는 종종 좋은 접근이지만, 유일한 방법은 아니다. 이 장에서는 우리는 수식적으로 선호되는 $\H_t(a)$ , preference에 대해서 고려해보고자 한다.

더 큰 preference 를 가지는 action일수록 더 자주 선택된다. 그러나 preference 는 reward 관점에서 해석이 없다.
오직 상대적인 preference 는 하나의 action 이 다른 action 에 비해 더 중요도를 가짐이다.

$$
Pr{$A_t$=a} = ${e^{H_t(a)}\over\sum^n_{b=1}e^{H_t(a)}}=\pi_t(a)$
$$

$\pi_t(a)$ 는 t에서 a를 선택할 확률이며 gradient 방식에서는 Soft-max distribution (Gibbs, boltzmann distribution) 을 사용한다. 초기에는 모든 preference 가 동등하다. (예를 들어 $H_1(a)=0$, all a)

이 stochastic gradient ascent 의 아이디어에 기반한 natural learning algorithm이 있다.
각 스텝에서 action $A_t$ 가 선택된 후에, 보상인 $R_t$ 를 받으면서 preference 는 다음과 같이 update 된다.

$\bar{R_t}$ 는 baseline 으로 사용되며, reward 가 baseline 보다 높다면, $A_t$ 를 선택할 확률이 증가한다.
반면, reward가 baseline 보다 낮다면, $A_t$ 를 선택할 확률이 감소한다. 선택되지 않은 action은 반대방향으로 움직인다.

위 그림에서, true expected rewards 는 normal distribution with a mean of +4 로 선택된 경우(with baseline)와 +0 으로 선택된 경우(without baseline) 두가지를 비교하고 있다. shifting up of all the rewards 는 알고리즘 상에서는 영향이 없는데, 이는 reward baseline term 은 즉각적으로 new level 을 adapts 하기 때문이다. 하지만, baseline 이 있을때가 없을때 보다 좋은 성능을 나타내고 있는 것을 볼 수 있다.

cf.
사실 위 알고리즘 은 gradient ascent 의 통계적 근사에 의해서 구해진 것이므로 아래 식이 보다 정확한 표현이다.

하지만, 책의 후속 내용에서 두가지가 같은 값임을 보이는 수학적 기술이 있다.