- 입실론 탐욕적 행동 선택에서 두 개의 행동이 있고
$\varepsilon=0.5$ 라면 탐욕적 행동을 선택할 확률은 얼마인가?
행동이
$a_{1}$ ,$a_{2}$ 이 있고, 최적 행동이$a_{1}$ 이라고 하자.$\varepsilon=0.5$ 이기 때문에$1-\varepsilon=0.5$ 이고 따라서 50% 확률로$a_{1}$ 을 선택하게 된다. 나머지 50% 선택은 가능한 모든 행동을 균등한 확률로(random) 두고 하게 된다. 따라서$0.5\times0.5 = 0.25$ , 즉$a_{1}$ ,$a_{2}$ 를 각각 25% 확률로 선택하게 된다. 정리해보면 최적 행동인$a_{1}$ 은$0.5+0.25=0.75$ , 75% 확률로 선택되며$a_{2}$ 는$0.25$ , 25% 확률로 선택된다.
-
(다중 선택 예제) 네 개의 행동 중 하나를 선택하는 다중 선택 문제를 생각해 보자. 각 행동은 번호 1, 2, 3, 4로 구분한다.(
$a_{1}$ ,$a_{2}$ ,$a_{3}$ ,$a_{4}$ ) 이 문제에 입실론 탐욕적 행동 선택을 이용한 다중 선택 알고리즘을 적용한다고 생각해 보자. 이때 이 알고리즘은 표본 평균 행동 가치 추정값을 이용하고 초기 추정값$Q_{1}(a)=0$ 을 적용한다. 시간 단계에 따른 행동 및 가치의 몇몇 초기값들이$A_{1}=1$ (=$a_{1}$),$R_{1}=-1$ ,$A_{2}=2$ (=$a_{2}$),$R_{2}=1$ ,$A_{3}=2$ (=$a_{2}$),$R_{3}=-2$ ,$A_{4}=2$ (=$a_{2}$),$R_{4}=2$ ,$A_{5}=3$ (=$a_{3}$),$R_{3}=0$ 이라고 가정해보자. 이 시간 단계 중 일부에서 행동이 무작위로 선택되는 입실론 상황이 발행했을 수 있다. 어떤 시간 단계에서 이 상황이 확실하게 발생했을까? 어떤 시간 단계에서 이 상황이 발생하는 것이 가능했을까?
시간 순서대로 선택한 것을 기반으로 행동 가치 Q 테이블을 작성하면 아래와 같다. time step마다 선택된 행동은 ✔️로 표시했다.
| action | |||||
|---|---|---|---|---|---|
| -1:heavy_check_mark: | -1 | -1 | -1 | -1 | |
| 0 | 1:heavy_check_mark: | -0.5:heavy_check_mark: | 0.333:heavy_check_mark: | 0.333 | |
| 0 | 0 | 0 | 0 | 0:heavy_check_mark: | |
| 0 | 0 | 0 | 0 | 0 |
$Q_{t}(n)=\frac{\sum_{i=1}^{t-1} R_{i} \cdot \mathbb{1}{A{i}=a}}{\sum_{i=1}^{t-1} \mathbb{1}{A{i}=a}}$ 수식을 이용하여 계산했다.
$t_{3}$ ,$t_{4}$ 인 2번의 시간 단계에서 무작위로 선택되는입실론 상황이 발생했다. 먼저$t_{3}$ 일 때까지 완성된 테이블에서 최적 행동은$a_{3}$ 이나$a_{4}$ 였지만,$a_{2}$ 가 선택되었기 때문이다.$t_{4}$ 일 때 까지의 최적 행동은$a_{2}$ 였으며 선택은$a_{3}$ 을 했으므로입실론 상황이 또 발생한 것으로 볼 수 있다. 따라서 총 2번의입실론 상황이 일어났다.
- 그림 2.2의 비교 그래프에서
누적 보상과최고의 행동을 선택할 확률을 고려할 때 어떤 방법이 장기적으로 가장 좋은 성능을 보여줄 것인가? 얼마나 더 좋을 것인가? 이 문제에 대해 정량적으로 답변해 보라.
그림 2.2에서
$\varepsilon=0.01$ 인 상황이 장기적으로 좋은 성능을 보여줄 것으로 예상된다.
그래프 2개에서 각각 시간 단계가 1000까지 나타나 있다. 그래프의 기울기가 완만하면 더 이상 값이 변화하지 않을 것으로 판단되기 때문에 그래프의 추세선 기울기로 앞으로 평균 보상이 더 올라갈 수 있는가를 예상해볼 수 있다. 또 다른 지표로는 최적 행동의 비율로 볼 수 있다. 최적 행동 비율이 높다는 것은 곧 탐험을 통해 최적 행동을 잘 식별하게 되었다는 것을 의미한다.
$\varepsilon=0$ 인 상황은 약 100 step 이전에 평균보상 1과 최적 행동 비율 35%정도에서 정체 되었고 장기적으로 변동을 보이지 않을 만한 평평한 추세선이 그려진다. 즉, 준최적 행동을 수행하는 상황에 걸렸다고 볼 수 있다. 따라서$\varepsilon=0.1$ 인 상황(A)과$\varepsilon=0.01$ 인 상황(B)을 비교해보겠다. 시간 단계 1000에서 A는 평균 보상 값이 B보다 0.1정도 높지만 최적 행동의 비율을 보면 완만한 기울기로 정체되어 있으며 더 이상 최적 행동 비율을 높일 가능성 적다. 반면 B는 최적 행동 비율 추세선이 좀 더 가파르며 A와의 평균보상 차이가 크지 않기 때문에 1000단계 이상의 장기적인 관점에서 A보다 B의 평균 보상이 더 높아져서 좋은 성능을 보일 수 있다.
- 시간 간격의 크기
$\alpha_{n}$ 이 고정된 값이 아니라면 추정값$Q_{n}$ 은 이전까지 받은 보상들의 가중 평균이고, 이때 가중치는 식 2.6에서 주어지는 것과는 다르다. 식 2.6과 유사한 일반적인 경우에 있어서 바로 이전 보상에 적용할 가중치는 얼마인가? 시간 간격의 크기와 관련하여 답변해 보라.
- (식2.6): $$\begin{aligned} Q_{n+1} &=Q_{n}+\alpha\left[R_{n}-Q_{n}\right] \ &=\alpha R_{n}+(1-\alpha) Q_{n} \ &=\alpha R_{n}+(1-\alpha)\left[\alpha R_{n-1}+(1-\alpha) Q_{n-1}\right] \ &=\alpha R_{n}+(1-\alpha) \alpha R_{n-1}+(1-\alpha)^{2} Q_{n-1} \ &=\alpha R_{n}+(1-\alpha) \alpha R_{n-1}+(1-\alpha)^{2} \alpha R_{n-2}+\ & \quad \cdots+(1-\alpha)^{n-1} \alpha R_{1}+(1-\alpha)^{n} Q_{1} \ &=(1-\alpha)^{n} Q_{1}+\sum_{i=1}^{n} \alpha(1-\alpha)^{n-i} R_{i} \end{aligned}$$
what..?
-
(programming) 표본평균 방법을 비정상적(nonstationary) 문제에 적용하기 어렵다는 점을 보여주는 실험을 설계하고 수행하라. 모든 $q_{}(a)$가 동일한 초깃값으로부터 시작하며 독립적으로 무작위 값을 갖도록 변형한 10중 선택 문제를 활용하라(말하자면, 평균이 0이고 표준 편차가 0.01인 정규 분포를 따르는 확률 변수를 각 시간 단계에서 $q_{}(a)$에 더하도록 함으로써). 점증적으로 계산한 표본평균을 활용하는 행동 가치 방법과 고정된 시간 간격(
$\alpha=0.1$ )을 사용하는 또 다른 행동 가치 방법에 대해 각각 그림 2.2와 같은 그래프를 그려 보라.$\varepsilon=0.1$ 을 적용하고 더 많은 단계, 말하자면 10,000번의 단계를 적용해 보라.
- 신비한 스파이크 그림 2.3에 보이는 결과는 무작위로 선택한 2000번의 10중 선택 결과에 대한 평균이기 때문에 매우 믿을 만하다. 그렇다면 왜 긍정적 방법의 경우 곡선의 처음 부분에서 요동(oscillation)과 스파이크(spike)가 나타나는가? 다시 말하면 무엇이 이 방법의 성능을 평균적으로, 특히 처음 부분에서 특별히 더 좋거나 더 나쁘게 만드는가?
-
편차 없는 고정 시간 간격 기법 이 장의 대부분에서 행동 가치를 추정하기 위해 표본평균을 이용했다. 그 이유는 표본평균을 사용하면 고정 시간 간격의 경우 발생하는 초기 편하를 없앨 수 있기 때문이다(식 2.6의 분석을 참고하라). 하지만 표본평균은 완전히 만족스러운 해결책은 아니다. 비정상적 문제에서는 형편없는 성능을 보일 수 있기 때문이다. 비정상적 문제에 대해 고정 시간 간격의 장점을 유지하면서도 편차를 없애는 것이 가능할까? 한 가지 방법은 특별한 행동에 대해 n번째 보상을 처리하기 위해 다음과 같은 시간 간격을 이용하는 것이다. $$\beta_{n} \doteq \alpha / \bar{o}{n}$$ 여기서 $\alpha>0$는 계속 하용하던 고정 시간 간격이고, $\bar{o}{n}$는 0에서 시작하는 값의 일반항이다. $$\vec{o}{n} \doteq \bar{o}{n-1}+\alpha\left(1-\bar{o}{n-1}\right), \quad \bar{o}{0} \doteq 0, n \geq 0인 경우$$ 식 2.6과 같은 분석을 수행하여
$Q_{n}$ 이 초기 편차가 없는 기하급수적 최신 가중 평균임을 보여라.
- UCB 스파이크 그림 2.4에서 UCB 알고리즘은 11번째 단계의 성능에서 뚜렷한 스파이크를 보여준다. 왜 이런 현상이 생길까? 완전히 만족스러운 답변을 하려면 11번쨰 단계에서 왜 보상이 증가하는지, 그리고 왜 이어지는 단계에서는 감소하는지를 설명해야 한다. 힌트: c=1이면 스파이크가 덜 두드러진다.
- 행동이 두 개일 경우, 통계학과 인공지능 신경망에서 자주 사용되는 로지스틱 또는 시그모이드 함수로 주어지는 분포가 소프트맥스 분포와 같음을 보여라.
- 행동 가치의 참값이 단계마다 무작위로 변하는 이중 선택 문제가 있다고 해 보자. 매 단계에서 행동 1과 2에 대한 가치의 참값이 0.5의 확률로 각각 0.1과 0.2인 경우(경우 A)와 0.5의 확률로 각각 0.9와 0.8인 경우(경우 B)를 가정해 보자. 어떤 단계가 어떤 경우에 해당하는지를 모른다고 할 때, 얻을 수 있는 최고의 기댓값은 얼마이며 그 기댓값을 얻기 위해서는 어떻게 행동해야 하는가? 이제 매 단계가 어떤 경우인지를 안다고 하면(행동 가치의 참값은 여전히 모르지만), 이것은 연관 탐색 문제가 된다. 이 문제에서 얻을 수 있는 최고의 기댓값은 얼마이며, 그것을 얻기 위해 어떻게 행동해야 하는가?