Assume that X is a finite space. Let P is a probability distribution over X. if q>0, then, \(S_q(P)\) is concave with respect to P.

proof. \(f(x) = -x \operatorname{ln}_q(x)\)이라고 정의(x>0). 이를 두번 미분.

1번 미분
\(\frac{df(x)}{dx} = -\operatorname{ln}_q(x) -x\operatorname{ln}_q^{'}(x)\)

2번 미분
\(\frac{d^2f(x)}{dx^2} = -\operatorname{ln}_q^{'}(x) -\operatorname{ln}_q^{'}(x) -\operatorname{ln}_q^{''}(x) = -2 \frac{(q-1)x^{q-2}}{q-1} - x\frac{(q-1)(q-2)x^{q-3}}{q-1}\) \(= -2x^{q-2}-x(q-2)x^{q-3} = -qx^{q-2}\)

-q는 항상 음수이고 x의 지수함수는 항상 양수이기 때문에 2번 미분한 값은 항상 음수로 나온다. 이 결과를 이용하여 다음과 같은 특성이 만족하는 것을 보일 수 있다.

\(\lambda_1, \lambda_2 \geq 0\), \(\lambda_1+\lambda_2 =1\)일 경우 probability \(P_1, P_2\)에 대해서 아래의 식을 만족한다.(중간값 정리)

\(S_q(\lambda_1P_1 + \lambda_2P_2) = \underset{x}{\sum}-(\lambda_1P_1(x) + \lambda_2P_2(x))\operatorname{ln}_q(\lambda_1P_1(x)+\lambda_2P_2(x))\) \(\ge \underset{x}{\sum} -\lambda_1P_1(x)\operatorname{ln}_q(P_1(x)) - \lambda_2P_2(x) \operatorname{ln}_q(P_2(x))\) \(=\lambda_1S_q(P_1) + \lambda_2S_q(P_2)\)

*위 식의 부등식(>)은 논문 부등식(<) 반대로 되어있다. 내가 생각하였을 때 중간값 정리를 적용하면 논문과 다르게 부등식이 반대로 되어야한다고 생각된다. 또한 뒤쪽에서 위 식을 사용하는 부분에서는 부등식이 반대로 되어 있기 때문에 > 부등식을 사용하는 것이 맞다고 생각한다.

그러므로 \(S_q(P)\)는 P에 대해서 concave하다.

Assume that X is a finite space. Then, S_q(P) is maximized when P is a uniform distribution. i.e., P= 1|X| where |x| is the number of elements in X.

proof. KKT condition을 이용하여 optimization problem 해결

기본적으로 discrete uniform distribution일 때 entropy가 최대값을 가진다는 것을 알고 있다. 이 논문에서는 다시 한번 증명을 하고 있고 이 내용을 후반 부 증명에서 사용했다.

where, \(\triangle = \{P \mid P(x) \geq 0, \underset{x}{\sum} P(x) =1\}\) is a probability simplex.

KKT condition:

\(\forall x \in X, \frac{\partial(S_q(\pi)-\underset{x}{\sum}\lambda^*(x)P(x) - \mu^*(1-\underset{x}{\sum}P(X)))}{\partial P(x)} \bracevert_{P(x)=P^*(x)}\) \(= -\operatorname{ln}_q(P^*(x))-(P^*(x))^{q-1}-\lambda^*(x) + \mu^*\) \(=-q \operatorname{ln}_q(P^*(x)) -1 -\lambda^*(x) + \mu^* =0\)
\(\forall x \in X, 0 = 1 -\underset{x}{\sum}P^*(x), P^*(x) \geq 0\)
\(\forall x \in X, \lambda^*(x) \leq 0\)
\(\forall x \in X, \lambda^*(x)P^*(x) =0\)

where \(\lambda^*\) and \(\mu^*\) are the Lagrangian multipliers for constraints in \(\triangle\)

세부 증명 1.
\(\frac {\partial S_q(\pi)} {\partial P(x)} = \frac{P(x)^{q-1}-1}{q-1} + P(x) \frac{(q-1)P(x)^{q-2}}{q-1}\)
\(=\frac{P(x)^{q-1}-1}{q-1} + \frac{(q-1)P(x)^{q-1}}{q-1}\) \(=\frac{qP(x)^{q-1}-1}{q-1}\) \(=\frac{qP(x)^{q-1} -q -1 +q}{q-1}\) \(=q\operatorname{ln}_qP(x)-1\)

세부 증명 2. 첫번째 KKT condition을 이용하여 \(P^*(x)\)에 대해서 정리
\(P^*(x) \ge 0\)이므로 \(\lambda^*(x) =0\)이 된다.

\(-q\operatorname{ln}_q(P^*(x)) -1 + \mu^*=0\)
\(\operatorname{ln}_q(P^*(x)) = \frac{-1+\mu^*}{q}\)
\(\frac{P^*(x)^{q-1}-1}{q-1} = \frac{-1 + \mu^*}{q}\)
\(P^*(x)^{q-1}-1 = (q-1) \frac{-1 + \mu^*}{q}\)
\(P^*(x) = (1+(q-1)\frac{-1 + \mu^*}{q})^{\frac{1}{q-1}}=\operatorname{exp}_q(\frac{\mu^* -1}{q})\)

P는 \(\mu\)와 q에 의해서만 결정된다.(constant probability mass) x에 대한 함수가 아니므로 \(P^*(x)=1/\vert S \vert\) where \(S=\{x \mid P^*(x) \ge0\}\)이다.(P가 모든 확률에 대한 uniform이 아닌 일부 확률에 대해서만 동일한 확률을 가질 수 있다. 물론 \(P^*(x) \ge 0\)이라고 condition이 있으므로 이미 uniform이라고 해도 될 것같다.)

Optimal value는 \(S_q(P^*)=-\operatorname{ln}_q(1/ \vert S \vert)\)이다. \(-\operatorname{ln}_q(x)\)는 단조 증가함수이므로 \(\mid S \mid\)는 최대가 되어야한다. S=X일 때 S가 최대가 되므로 \(P^*(x) = 1/\vert X \vert\)이다.

The optimal solution of

is

where the q-potential function \(\psi_q\) is a functional define on {A,r}

\(\psi\)는 아래의 공식의 condition에 의해서 결정된다.

\(\psi^*_q\)를 이용해서 optimal value는 아래와 같이 정의할 수 있다.

proof. \(\operatorname{exp}_q \in [0, \infty)\)는 continous 단조 함수 이기 때문에 \(\underset{a}{\sum} \operatorname{exp}_q(\frac{r}{q} - \xi)\)는 0으로 수렴하고 \(\xi\)가 +,- 무한대일 경우 무한대로 수렴한다. 그러므로 \(\underset{a}{\sum} \operatorname{exp}_q(\frac{r}{q} - \xi^*)=1\)을 만족하는 \(\xi^*\)가 존재한다. 그러므로 \(\psi_q(r/q) = \xi^*\)라고 할 수 있다.

나머지는 KKT condition을 고려하여 구한다. KKT conditon:

\(\forall i, 1-\underset{a}{\sum} \pi^*_q(a) = 0, \pi^*_q(a) \geq 0\)
\(\forall i, \lambda^*(a) \leq 0\)
\(\forall i, \lambda^*(a)\pi^* =0\)
\(\forall i, r(a)-\mu^* - \operatorname{ln}_q(\pi^*_q(a)) - (\pi^*_q(a))^{q-1}+\lambda^*(a)=0\)

마지막 condition은 아래 식으로부터 나온다. \(\frac{\partial}{\partial \pi}(\underset{a \sim \pi}{E}[R] + S_q(\pi) + \mu^*(1-\underset{a}{\sum} \pi(a))+\lambda^*(a)\pi(a))\)

마지막 condition은 아래와 같이 변환이 가능하다. \(0=r(a) -\mu^* - \operatorname{ln}_q(\pi^*_q(a)) - (\pi^*_q(a))^{q-1} + \lambda^*(a)\)
\(0=r(a) -\mu^* - \operatorname{ln}_q(\pi^*_q(a)) - (q-1)\frac{(\pi^*_q(a))^{q-1}}{q-1} + \lambda^*(a)\)
\(0=r(a) -\mu^* - \operatorname{ln}_q(\pi^*_q(a)) - (q-1)\frac{(\pi^*_q(a))^{q-1}+1-1}{q-1} + \lambda^*(a)\)
\(0=r(a) -\mu^* - \operatorname{ln}_q(\pi^*_q(a)) - (q-1)\frac{(\pi^*_q(a))^{q-1}-1}{q-1} -1 + \lambda^*(a)\)
\(0=r(a) -\mu^* - \operatorname{ln}_q(\pi^*_q(a)) - (q-1)\operatorname{ln}_q(\pi^*(a)) -1 + \lambda^*(a)\)
\(0=r(a) -\mu^* - q\operatorname{ln}_q(\pi^*_q(a)) -1 + \lambda^*(a)\)

\(\pi^*_q(a) \ge 0\)이므로 \(\lambda^*(a) =0\)이 된다. 그러므로 위 공식은 아래와 같이 표현된다.

\(0=r(a) -\mu^* - q\operatorname{ln}_q(\pi^*_q(a)) -1\)
\(q\operatorname{ln}_q(\pi^*_q(a))=r(a) -\mu^* -1\)
\(\operatorname{ln}_q(\pi^*_q(a))=\frac{r(a)}{q} -\frac{\mu^* +1}{q}\)
\(\pi^*_q(a) = \operatorname{exp}_q(\frac{r(a)}{q} - \frac{\mu^*+1}{q})\)

이제 \(\mu^*\)를 구해야한다. 이 값은 \(\underset{a}{\sum}\pi^*_q(a)\)를 이용해 구할 수 있다. \(\underset{a}{\sum}\pi^*_q(a) = \underset{a}{\sum} \operatorname{exp}_q (\frac{r(a)}{q} - \frac{\mu^*+1}{q})=1\)

이전에 \(\underset{a}{\sum} \operatorname{exp}_q (\frac{r(a)}{q} - \psi_q (\frac{r}{q}))=1\)로 표현하였다. 위 두 식이 동일하다고 하면

이 된다. 이 식은 \(\mu^*\)에 대해서 풀면 해당 값을 얻을 수 있다.

\(\pi^*_q(a) \ge 0\)를 만족해야한다.(KKT condition)

이므로 \(\pi^*_q(a) \ge 0\)를 만족한다.(위 식은 \(\pi^*_q(a)\)의 definition에 의한 식이다.)

• \(\mu^*\)가 이전 공식에서 비교해서 가져오는 것이 아닌 논문 저자의 수식 표현으로 정의할 때어디서 이 표현 수식의 idea를 가져왔는 지 과정이 궁금하다.

Optimal value problem은 아래의 수식으로 표현 가능하다.

\(\underset{a \sim \pi^*_q}{E}[R] + S_q(\pi^*_q)\)
\(=\underset{a}{\sum}r(a)\pi^*_q(a) - \underset{a}{\sum}[\frac{r(a)}{q} - \psi(\frac{r}{q})]\pi^*_q(a)\)
\(=\underset{a}{\sum}[r(a)\pi^*_q(a) - \frac{r(a)}{q}\pi^*_q(a) + \underset{a}{\sum}\psi_q(\frac{r}{q})\pi^*_q(a)]\)
\(=\underset{a}{\sum} \frac{qr(a)-r(a)}{q} \pi^*_q(a) + \psi_q(\frac{r}{q})\underset{a}{\sum}\pi^*_q(a)\)
\(=(q-1)\underset{a}{\sum}\frac{r(a)}{q}\pi^*_q(a) + \psi_q(\frac{r}{q})\)
\(=(q-1)\underset{a}{\sum}\frac{r(a)}{q}\operatorname{exp}_q(\frac{r(a)}{q} - \psi_q(\frac{r}{q})) + \psi_q(\frac{r}{q})\)

When q=1 and q=2, \(\psi_1, \pi^*_1\) and \(\psi_2, \pi^*_2\)의 연산 결과는 아래와 같다.

proof.

이전 공식 \(\pi^*_q(a) = \underset{a}{\sum} \operatorname{exp}(\frac{r(a)}{q} - \frac{\mu^*+1}{q})\)를 이용

q=1일 경우

\(\pi^*_1\)는 \(\operatorname{exp}(r(a) -\psi_1(r))\)이 된다.(이전의 \(\pi^*_q\)의 공식을 이용)

\(\mu^* +1 = \psi_1(r(a))\)이므로

q=2일 경우

\(\pi^*_2\)는 \(\operatorname{exp}(\frac{r(a)}{2} -\psi_2(\frac{r}{2}))\)이 된다.

\(\frac{\mu^* +1}{2} = \psi_2(\frac{r}{2})\)이므로

proof 1. lower bound

\(\underset{x}{\text{q-max}} (f(x)) = \underset{P \in \triangle}{\text{max}} [\underset{X \sim P}{E}[f(X)] + S_q(P)] \leq \underset{P \in \triangle}{\text{max}} \underset{X \sim P}{E}[f(X)] + \underset{P \in \triangle}{\text{max}} S_q(P)\)
\(= \underset{x}{\text{max}}(f(x)) - \text{ln}_q(\frac{1}{\vert X \vert})\)

proof 2. upper bound

P’이 한 값만 뽑을 수 있게 되어 있다면(P’(x) =1 when \(x=\text{argmax}_{x'}f(x')\), others P(x’)=0) P’의 Tsallis entropy는 0이 될 것이다.

Theorem 9를 증명하기 전 2가지 proposition과 한 개의 lemma를 먼저 얘기하고자한다. 이 식들은 \(\pi\)를 state action visitation인 \(\rho\)로 변환하는 데 사용된다.

• Proposition 5.

위 두식을 만족한다면 식을 만족한다.

• Proposition 6.

만약 \(\rho \in M\)이라면 state action visitation을 이용해 \(\pi_\rho(a|s) \triangleq \frac{\rho(s,a)}{\sum_{a'}\rho(s,a')}\) 로 표현할 수 있고 \(\pi_\rho\)는 state-action visitation이 \(\rho\)인 유일한 policy이다.

• Lemma 9.1

위 두 Proposition 5,6을 통하여 policy와 state action visitation이 1:1 대응이 된다는 것을 알 수 있었다. 이 lemma에서는 \(\pi\)를 \(\rho\)로 변환할 것이다.

위 식을 만족한다면 \(\pi \in \Pi\)의 어떤 stationary policy와 \(\rho \in M\)의 어떤 state-action visitation measure에 대해서 \(S^\infty_q(\pi) = \bar{S}^\infty_q(\rho_\pi)\)를 만족한다.

Proof.

• Corollary 9.1.1

\(\rho\)가 optimal이면 \(\pi\)가 optimal인 것을 설명

where, \(J(\pi) = E_{\tau \sim \pi, P} [\sum^\infty_{t=0} \gamma^t R_t]\)

위 식은 아래 식으로 변경이 가능하다.

하지만 \(\rho^*\)는 optimal이기 때문에 모순이다.

위 식이 맞는 식이 되고 \(\rho^*\)가 optimal이면 \(\pi^*\)도 optimal이 된다.

subject to \(\forall s, a, \rho(s,a) \geq 0, \sum_a \rho(s,a) = d(s) + \sum_{s',a'} P(s |s',a') \rho(s',a')\)

이전의 Proposition 6과 Lemma 9.1을 통하여 Tsallis MDP를 \(\pi\) 대신 \(\rho\)로 표현이 가능하다. 그리고 이 ㅅ식을 이용해서 convcave한 것을 증명할 것이다.

Lemma 9.2 \(\bar{S}^\infty_q(\rho)\) is concave function with respect to \(\rho \in M\)

Proof.

\(f(x) = -x\text{ln}_q(x)\)라고 할 때 2차 미분 값은 \(-qx^{q-2}\)가 되고 이 값은 x가 0보다 클 때 음수가 된다. 즉 f(x)는concave function이라고 할 수 있다. concave function은 다른 방법으로 아래 식과 같은 중간값 정리를 이용하여 증명할 수 있다.

where, \(0<\lambda_1, \lambda_2 < 1\), \(\lambda_1 + \lambda_2 =1\), \(\rho_1, \rho_2 \in M\)

\(\widetilde{\rho}\)를 \(\lambda_1 \rho_1 + \lambda_2 \rho_2\)라고 정의하고 \(\mu_1 = \frac{\lambda_1 \sum_{a'} \rho_1(s,a')}{\sum_{a'} \widetilde{\rho}(s,a')}\) 그리고 \(\mu_2 = \frac{\lambda_2 \sum_{a'} \rho_2(s,a')}{\sum_{a'} \widetilde{\rho}(s,a')}\) 라고 정의한다. 그리고 \(\mu_1 + \mu_2 =1\)이 된다.

그러므로 아래 식을 만족한다.

\(- (\frac{\mu_1 \rho_1(s,a)}{\sum_{a'} \rho_1(s,a')} + \frac{\mu_2 \rho_2(s,a)}{\sum_{a'} \rho_2(s,a')}) \text{ln}_q (\frac{\mu_1 \rho_1(s,a)}{\sum_{a'} \rho_1 (s,a')} + \frac{\mu_2 \rho_2(s,a)}{\sum_{a'} \rho_2 (s,a')})\) \(> - \mu_1 \frac{\rho_1(s,a)}{\sum_{a'}\rho_1(s,a')} \text{ln}_q (\frac{\rho_1(s,a)}{\sum_{a'} \rho_1(s,a')}) - \mu_2 \frac{\rho_2(s,a)}{\sum_{a'}\rho_2(s,a')} \text{ln}_q (\frac{\rho_2(s,a)}{\sum_{a'} \rho_2(s,a')})\)

\(\sum_{a'} \widetilde{\rho}(s,a') \mu_1 \frac{\rho_1(s,a)}{\sum_{a'} \rho_1(s,a')}= \sum_{a'} \widetilde{\rho}(s,a') \frac{\lambda_1 \sum_{a'} \rho_1 (s,a')}{\sum_{a'} \widetilde{\rho}(s,a')} \frac{\rho_1(s,a)}{\sum_{a'} \rho_1(s,a')} = \lambda_1\rho_1(s,a)\)이므로 우리는 위 식을 정리하면 아래를 얻을 수 있다.

위 식을 통해 concave함을 증명하였다. (q가 0보다 클 경우)

• Corollary 9.2.1

subject to \(\forall s, a, \rho(s,a) \geq 0, \sum_a \rho(s,a) = d(s) + \sum_{s',a'} P(s |s',a') \rho(s',a')\)

이 식은 첫 번째 term은 linear하고 두 번째 term은 concave하니 concave problem이라고 할 수 있다.

\(L \triangleq \sum_{s,a} \rho(s,a) r(s,a) - \sum_{s,a} \rho(s,a) \text{ln}_q (\frac{\rho(s,a)}{\sum_{a'}\rho(s,a')}) + \sum_{s,a} \lambda (s,a) \rho(s,a)\) \(+ \sum_s \mu(s) (d(s) + \sum_{s',a'} P(s|s',a') \rho(s',a') + \sum_a \rho(s,a))\)

where \(\lambda(s,a)\) and \(\mu(s)\) are dual variables for nonnegativity and Bellman flow constraints.

KKT condition:

Lagrangian objective에서 \(\bar{S}^\infty_q(\rho)\)의 derivation된 kkt condition 값은 아래와 같이 유도된다.

\(\frac{\partial \bar{S}^\infty_q(\rho)}{\partial \rho(s'',a'')} = -\sum_{s,a} \frac{\partial \rho(s,a)}{\partial \rho(s'',a'')} \text{ln}_q (\frac{\rho(s,a)}{\sum_{a'} \rho(s,a')})\) \(- \sum_{s,a} \rho(s,a) \frac{\partial \text{ln}_q(\rho(s,a)/\sum_{a'} \rho(s,a'))}{\partial \rho(s'',a'')} -1\)

\(= -\text{ln}_q(\frac{\rho(s'',a'')}{\sum_{a'}\rho(s''a,')})\) \(- \sum_a \rho(s'',a)(\frac{\rho(s'',a)}{\sum_{a'}\rho(s'',a')})^{q-2}(\frac{\delta_{a''}(a)}{\sum_{a'}\rho(s'',a')} - \frac{\rho(s'',a)}{(\sum_{a'} \rho(s'',a'))^2})\)

• \(\text{ln}_q x + x^{q-1} = \frac{x^{q-1}-1}{q-1}+x^{q-1} = \frac{x^{q-1}-1 + (q-1)x^{q-1}}{q-1} = \frac{qx^{q-1}-1}{q-1}\) \(= \frac{qx^{q-1}-1 +q-q}{q-1} = q\frac{x^{q-1}-1}{q-1} +1 = q\text{ln}_qx +1\)

\(\mu^*(s)\)를 optiaml value인 \(V^*_q(s)\)라고 칭하고 싶다. 그래서 stationary condition에 \(\pi_{\rho^*}(a|s) = \rho^*(s,a)/\sum_{a'} \rho^*(s,a')\)를 곱한다. 그리고 a에 대해서 정리를 하면 아래처럼 정리된다.

KKT condition에 의해서 \(\lambda^*(s,a) =0\)

\(\sum_{s,a}x^q -1 = \sum_{s,a}(x^q-x) = \sum{s,a} (q-1) \frac{x^{q-1}-1}{q-1}x = (q-1)\sum_{s,a}x\text{ln}_qx\) 식을 이용

그러므로

위 식은 Tsallis Bellman expectation(TBE)를 만족한다. 그러므로 \(\mu^*(s)\)를 $$V^{\pi_{\rho^*}}인 value of optimal policy라고 칭할 것이다. 물론 추가적인 증명이 필요하지만 이는 Theorem 10에서 증명을 할 것이다.

\(\mu^*=V^*_q\)라면 \(Q^*_q(s,a) = E_{s' \sim P}[r(s,a,s') + \gamma\mu^*(s')]\)를 얻을 수 있다.

\(\rho^*(s,a)/\sum_{a'}\rho^*(s,a')\) 를 \(\pi_{\rho^*}(a|s)\)로 치환하고, \(Q^*_q(s,a) = E_{s' \sim P} [r(s,a,s') + \gamma \mu^*(s')]\), \(\mu^*(s) = V^*(s)\)라고 한다면 아래 식을 KKT condition을 이용하여 구할 수 있다.

\(\sum_a\pi(a|s) =1\) 이므로 양변에 \(\sum\)을 넣는다.

이 식은 q-exponential distribution의 normalization equation이다. 그러므로 q-potential과 optimal value function과 관계를 얻을 수 있다.(식 24를 참고)

결론적으로, optimal policy는 \(Q^*_q(s,\cdot)\) q-exponential distribution을 얻을 수 있다.

이를 \(\mu^*\) 식에 대입하면 아래 식을 얻을 수 있다.

결론으로 아래의 Tsallis MDP의optimality condition를 얻을 수 있다.

• Lemma 10.1

Proof.

• Lemma 10.2

1

* 위 식의 부등호 방향이 맞는 지 의문이 있긴함.

• Lemma 10.3

Fixed policy \(\pi\)와 entropic index \(q \ge 1\), TBE operator \(\Gamma^\pi_q\)

Tsallis policy evaluation은 \(F_{k+1} = \Gamma^\pi_qF_k\)로 정의할 수 있다. 그러면 \(F_k\)가 converge하다면 TBE equation을 만족한다.

Proof of Tsallis Policy Evaluation

위의 lemma를 통해 \(\Gamma^\pi_q\)가 \(\gamma\)-contraction임을 증명하였고 Banach fixed point theorem에 의해 unique fixed point \(F_* = \Gamma^\pi_qF_*\)임을 얻을 수 있다. 그러므로 F에서부터 \(F_k\) sequence는 fixed point로 converge하다는 것을 얻을 수 있다. \(F_*\)가 unique이므로 \(F_*\)는 TBE equation을 만족하는 유일한 function이다. 그러므로 \(F_*=Q^\pi_q\)이다.

• Theorem 11: \(\pi_{k+1}\)을 updated policy라고 한다면 \(Q^{\pi_{k+1}}_q(s,a)\)는 \(Q^{\pi_k}_q(s,a)\)보다 더 크다.

Proof

\(\pi_{k+1}\)은 updated policy이고 policy를 최대화하는 것은 concave하므로 아래 식을 만족한다.

• Theorem 12(Optimality of TPI): TPI converges into an optimal policy and value of a Tsallis MDP.

현재까지 TBE와 식의 Improvement를 증명하였다. 여기서는 TPI가 optimal policy와 Tsallis MDP value로 converge함을 증명하고자 한다.

Proof.

reward function r이 \(r_{\text{max}}\)의 uppder bound이고 \(Q^{\pi_k}_q\) 또한 한계가 있다. 그리고 \(Q^{\pi_k}_q\)는 monotonically non-decreasing(Theorem 11)이므로 어떤 \(\pi_*\)에 converge한다. \(Q^{\pi_k}_q\)의 unique한 solution은 \(\pi_*\)이고 Theorem 9에 의해 식들이 Optimal하므로 \(\pi_*=\pi^*_q\)가 되어 optimal solution이 된다.

• lemma 14.1

\([\Gamma F](s,a)\) \(\triangeq E_{s' \sim P}[r(s,a,s') + \gamma \underset{a'}{\text{max}}F(s',a') | s,a]\)

Proof. k=1이라면 Lemma 13.1에 의해 아래 식을 만족한다.

\([\Gamma F]\) \((s,a) = E_{s' \sim P} [r(s,a,s') + \gamma \underset{a'}{\text{max}}F(s',a') |s,a]\) \(\leq E_{s' \sim P}[r(s,a,s') + \gamma q-\underset{a'}{\text{max}}F(s',a') | s,a] =\) \([\Gamma_qF](s,a)\)

k=n이라면

그러므로

Theorem 14.

Proof.

Upperbound는 original MDP가 \(J(\pi)\)를 최대화 하기 때문에 \(J(\pi^*_q) \leq J(\pi^*)\)가 된다.

Lower bound는 아래 식을 이용하여 증명된다.