On an optimal strategy of ergodic control(Nonlinear Analysis and Convex Analysis)

On

an

optimal

strategy

of

ergodic control

新潟大学理学部数学科 田中謙輔 (Kensuke Tanaka)

In this paper, stochastic control processes have been investigated as dynamic

pro-gramming models with an infinite horizon. Then, we want to seek for an optimal

strategy under the expected average loss criterion. It has been shown to exist an

optimal strategy under the various conditions. However, optimal strategy may not

exist under weak conditions. Under some weak condition, we introduce a

modi-fied form of the dynamic model, which we want to call as dual dynamic one. By

Fenchel’sduality theorem, we show thatoptimal valueof the original model isequal

toone ofthedual model. Moreover, weshow that there exists an optimal strategy

for the dual model.

Keywords: dynamicprogramming,optimalpolicy,Fenchelinequality,and Fenchel’s

duality theorem

1

制御

D.P

モデル

の記号と構成

次のような簡単な

D.P

モデル $(S, A, B, H_{P},, r)$ _{の平均期待損失基準のもとでの}

最適性について考察する

.

ただし

,

(1)

$S=\{1,2,3, \cdots, i, \cdots\}$

,

システムの状態空間

(2)

$A,$ $B$

,

システムの制御空間で共に

Banach

space

(3)

$A(i)$

,

_各状態 $i\in S$ _{に対応する許容制御集合} $A(i)\subseteq A$

(4)

$H_{i}$

,

各状態 $i\in S$ に対応する連続な線形写像私 $\in L(A, B)$

(5)

$P$: 各 $(i, H_{i}a)\in S\cross B$ に対応する $S$ 上の確率

(6)

$r(i, a)$

,

_損失関数 $r:S\cross Aarrow R\cup\{\infty\},$ $\not\equiv\infty$

この時, マルコフ制御戦略 $\pi=(f_{1}, f_{2}, *\cdot\cdot, f_{t}, \cdots)$

,

$f_{t}$

:

$Sarrow A$

,

のみについて

考察し

,

各戦略 $f_{t},$$t=1,2,3,$ $\cdots$

,

が現時点での状態のみに依存するのでマルコフ

制御戦略

,

又は単にマルコフ戦略と呼ばれており) このような制御戦略の全体を記

号 $\Pi$ で表す

.

更に, 各初期状態 $i\in S$ と制御戦略 $\pi\in\Pi$ に対応する平均期待損

失を

$I( \pi)(i)=\lim_{narrow}\sup_{\infty}|_{1}E[\pi r(S_{t,ft}(st))|S1=i]$

で与える

.

この時, 確率過程 $i^{s_{t}}\}_{t}=1,2,\cdots$_, は戦略 $\pi$ によって生成される $S$ 上のマル

コフ過程を構成している

.

ここで,

最適化問題を次のように表現する

:

Definition 1

この $(\mathrm{M}\mathrm{P})$ 問題で

$\overline{I}(i)=$

inf

_$I(\pi)(i)$

$\pi\in\Pi$

を満たす値 $\overline{I}(i)$ は初期状態 $i\in S$ に対応する最適損失値) 又は単に最適値と呼ぶ

Definition

2

この $(\mathrm{M}\mathrm{P})$ 問題で) もし $\overline{I}(i)=I(\overline{\pi})(i)$ を満たす制御戦略 $\overline{\pi}\in\Pi$ が

存在すれば

,

この $\overline{\pi}\in\Pi$ を初期状態 $i\in S$ に対応する最適制御戦略と呼ぶ

.

更に

この $\overline{\pi}\in\Pi$ が全ての初期状態 $i\in S$ に対応する最適制御戦略であるとき, 単に最

適制御戦略

(optimal

control

strategy),

又は最適戦略と呼ぶ

.

2

補助定理と定理の証明

本論の主な補助定理と定理の証明を与える為に次の記号を用いる

.

この章を通し

て, $g$

:

$Sarrow R\cup\{\infty\},$ $\not\equiv\infty$

,

な関数の全体を $B(S)$ とおき

,

$u\in B(S)$ に対して次

のような記号を導入する

.

1.

$T_{a}u(i)=r(i, a)+\Sigma_{j\in s^{u}}(j)p(j|i, Hia)=r(i, a)+G(H_{i}a, u)(i)$

$2$

.

_{$Tu(i)= \inf_{a\in A(i)}\tau_{a}u(i)$}

3.

$r^{*}(i,p)= \sup_{a}\in A(i)[\langle a,p\rangle-r(i, a)],$ $p\in A^{*},$ $A^{*}$ は $A$ の双対空間

4.

$G^{*}(q, u)(i)=\mathrm{s}\mathrm{u}\mathrm{p}b\in B[\langle q, b\rangle-G(b, u)(i)],$ $q\in B^{*},$ $B^{*}$ は $B$ の双対空間

5.

$T_{q}^{*}u(i)=-r^{*}(i, -H_{i}^{*}q)-G*(q, u)(i),$ $H_{i}^{*}\in L(B^{*}, A^{*})$ $6$

.

_{$T^{*}u(i)= \sup_{q\in B*q}T*u(i)$}

この時, 全ての $a\in A,$$q\in B^{*}$ と全ての $i\in S$ に対して, $T_{a}u(i),$$\tau_{q}*u(i)$ に

Fenchel

の不等式を適用して, 次の補助定理が示される

.

Lemma

1全ての $i\in S$ _に対して

,

Tu

$(i)\geq T^{*}u(i)$

Proof

各 $i\in S,$$u\in B(S)$ について, 全ての $a\in A,$$q\in B^{*}$ に対して,

Fenchel

の

不等式を適用して

$T_{a}u(i)-T_{q}^{*}u(i)$ $–r(i, a)+G(H_{i}a, u)(i)+r^{*}(i, -H_{i}^{*}q)+G^{*}(q, u)(i)$

$\geq$ $\langle-H_{i^{*}}q, a\rangle+\langle q,$$H_{\mathrm{i}}a)$

$=$ $-\langle q, H_{i}a\rangle+\langle q,$$H_{i}a)$

よって, 全ての $a\in A,$$q\in B^{*}$ に対し,

$T_{a}u(i)\geq T_{q}^{*}u(i)$

上の不等式で

,

$a\in A$ _{に対して下限を} $q\in B^{*}$ に対して上限を取る事より結論の不

等式が得られる. 口

次に

,

各 $i\in S$ _{に対して,}

dom

$r^{*}(i, \cdot)=A_{i}^{*}\subset A^{*},$$\mathrm{d}\mathrm{o}\mathrm{m}G^{*}(\cdot, u)(i)=B_{i}^{*}(u)\subset$

$B^{*}(u)$ に対して, 以下のような写像を導入する

:

$\Psi_{i}$

:

$A_{i}^{*}\cross B_{i}^{*}(u)arrow R\mathrm{x}A^{*}$

$\Psi_{i}(p, q)=(-r^{*}(i,p)-G^{*}(q, u)(i),$ $p+H_{i}^{*}q)$

上の写像を用い,

Fenchel

の双対定理を示す証明の流れの–部を適用し, 次の

補助定理が得られる

.

Lemma

2全ての $i\in S$ _と $u\in B(S)$ に対して,

domr

$(i, \cdot)=A_{i}\subset A(i),$$\mathrm{d}_{\mathrm{o}\mathrm{m}G}(\cdot, u)(i)=$

$B_{i}(u)\subset B$ とおき$\rangle$

$\theta\in \mathrm{i}\mathrm{n}\mathrm{t}(H_{i}A_{i}-B_{i}(u))\subset B,$ $\theta\in H_{i}^{*}B_{i}^{*}(u)+A_{i}^{*}\subset A^{*}$

を満たすとする. ただし記号

int

は集合の内点の全体

.

この時全ての $i\in S$ _に対し

て, 次の式を満たす写像 $f^{*}:$ $Sarrow B^{*}$ _{が存在する}

$T^{*}u(i)=T_{f^{*}}^{*}u(i)$

Proof

各状態 $i\in S$ _{と $u\in B(S)$ に対して, 結果の式を満たす} $B^{*}$ の対応する点

$f^{*}(i)$ が存在する事を示せば証明は終わる

.

そこで, $T^{*}u(i)$ の定義から $T^{*}u(i)$ に

収束し, 次の条件を満たす実数列 $v_{n}^{*}(i)$ と $p_{n}\in A_{i}^{*},$$q_{n}\in B_{i}^{*}(u)$ が存在する

:

$v_{n}^{*}(i)=-r^{*}(i, p_{n})-G^{*}(q_{n}, u)(i),$ $p_{n}=-H_{i}^{*}q_{n}$

即ち

,

$(v_{n}^{*}(i),p_{n}+H_{i}^{*}q_{n})\in\Psi_{i}(A_{\mathrm{i}}^{*}\cross B_{i}^{*}(u))$

ただし, $r_{n}=p_{n}+H_{i}^{*}q_{n}$ とおくとき, 全ての $n=1,2,$ $\cdots$

,

に対して, $r_{n}=\theta$ _で

ある. また

,

この補助定理の仮定より, 次の条件を満たす半径 $\epsilon>0$

,

中心 $\theta$

の球

$B_{\epsilon}\subset B$ が存在する

:

$B_{\epsilon}\subset \mathrm{i}\mathrm{n}\mathrm{t}(H_{i}A_{i^{-}}B_{i}(u))$

ここで, 任意の $z\in B$ に対して, $\frac{\epsilon}{||z||}z=H_{i}a-b$ と書ける $a\in A_{i},$$b\in B_{i}(u)$ が存

在する

.

この事より,

$\frac{\epsilon}{||z||}\langle z, q_{n}\rangle$ $=$ $\langle H_{\mathrm{i}}a-b, qn\rangle$

$=$ $-\langle a, -H_{i^{*}}q_{n}\rangle-\langle b, q_{n}\rangle$

$=$ $-\langle a,p_{n}\rangle-\langle b, q_{n}\rangle$

$\geq$ $-\{r(i, a)+r^{*}(i,p_{n})\}-\{G(b, u)(i)+G^{*}(q_{n}, u)(i)\}$

$=$ $v_{n}^{*}(i)-\{r(i, a)+G(b, u)(i)\}$

が成立する

.

この時に鳩

(i)

は $T^{*}u(i)$ に収束する事から, 全ての $z\in B$ に対して

$\inf_{n\geq 1}\langle z, q_{n}\rangle>-\infty$

だ成立する. よって, $q_{n}$ の列は弱*コンパクトとなり, $B^{*}$ のある点 $q^{*}$ に弱

*

収束

する部分列先

J

があり, 同時に部分列 $p_{n’}$ は $p^{*}=-H_{i}^{*}q^{*}$ に弱

*

収束する

.

更に共

役関数の構成法より $-r^{*},$ $-G^{*}$ は弱

*

上半連続であるから

$-r^{*}(i,p^{*}.)-G*(q^{*}, u)(i)$ $\geq$ _{$\lim_{narrow}\sup_{\infty}\{-r^{*}(i,p_{n})\}+\lim_{narrow}\sup_{\infty}\{-G^{*}(qn’ u)(i)\}$} $\geq$

$\lim_{narrow}\sup_{\infty}\{-r^{*}(i,pn)-G^{*}(qn’ u)(i)\}$

$=$ $\lim_{narrow\infty}v_{n}(*i)=T^{*}u(i)$

が成立する. 以上の理由から次の事が成立している

$-r^{*}(i,p^{*})-G*(q^{*}, u)(i)\geq T^{*}u(i),$ $p^{*}+H_{i}^{*}q^{*}=\theta$

かくて, 各 $i\in S$ _に対して $f^{*}(i)=q^{*}\in B^{*}$ とおくと

,

全ての $i\in S$ _に対して

$T_{f^{*}}^{*}u(i)\geq T^{*}u(i)$

を満たす $f^{*}$

:

$Sarrow B^{*}$ が得られる. –方 $T^{*}u(i)$ の構成より全ての $q\in B^{*}$ に対

して

$T^{*}u(i)\geq T_{f^{*}}^{*}u(i)$

が成り立つので

,

結論が得られ定理の証明は終わる

.

口

次の重要な補助定理を与えるために

,

定義された写像働に凸錐 $Q$

$Q=[0, \infty)\cross\{\theta\}\subset R\cross A^{*}$

を導入する.

Lemma

3全ての $i\in S$ _と $u\in B(S)$ に対して

$\theta\in \mathrm{i}\mathrm{n}\mathrm{t}(H_{i}A_{i}-B_{i}(u)),$ $\theta\in H_{i}^{*}B_{i}^{*}(u)+A_{i}^{*}$

の条件の下で) 全ての $i\in S$ _に対して

(Tu

$(i),$$\theta$

)

$\in\Psi_{i}(A^{*}(i), B*(i))-Q$

を満たすと仮定する

.

この時, 全ての $i\in S$ _に対して

Proof

Lemma

2

とこの補助定理の条件を適用すると

,

全ての $i\in S$ _に対して

$p^{*}+H_{i}^{*}q^{*}=\theta$ を満たす $p^{*}\in A^{*},$ $q^{*}\in B^{*}$ が存在して

Tu

$(i)\leq$ $-r^{*}(i,p^{*})-G*(q^{*}, u)(i)$

$=T_{q^{*u}}^{*}(i)$ $\leq T^{*}u(i)$ が得られる. また

Lemma 1

より

Tu

$(i)\geq T^{*}u(i)$ が成立する事より, 補助定理の結論が得られ証明は終わる

.

ロ

本論文の主定理を成立させるために

,

次の仮定を導入する

.

この仮定が成立す

るためのいろいろな充分条件が研究されて来ているが

,

ここでは省略する

.

Assumption

最適方程式

:

全ての $i\in S$ _{に対して,} $g+w(i)$ $=$ $Tw(i)$ $=$

inf

$T_{\alpha}w(i)$ $a\in A(i)$

$=$ $\inf\{r(i, a)+G(H_{i}a, w)(i)\}$ $a\in A(i)$

を満たす定数 $g$ と実関数 $w:Sarrow R$ が存在する

Theorem 1

$D.P$ _{モデルが上の仮定のもとで}

)

_{次の条件を満たしている}

.

_全ての

$i\in S$ _に対して,

1.

$\theta\in H_{i}^{*}.B_{i}^{*}(u)+A_{i}^{*},$ $\theta\in \mathrm{i}\mathrm{n}\mathrm{t}(H_{i}A_{i}-B_{i}(u))$

2.

(Tu

$(i),$$\theta$

)

_{$\in\Psi_{i}(A_{i}^{*}, Bi*(u))-Q,$}

$\forall u\in B(S)$

3.

$\lim_{narrow\infty}\frac{E_{\pi}[w(_{S_{n})|s_{1}=}+1i]}{n}=0,\forall\pi\in\Pi$ この時

,

全ての $i\in S$ _{に対して,}

inf

$I(\pi)(i)=I^{*}(\pi*)(i)$ $\pi\in\Pi$

を満たすある双対定常戦略 $\pi^{*}=(f^{*}, .f^{*}, \cdots, f^{*}, \cdots),$ $f^{*}:$ $Sarrow B^{*}$ _{が存在する}

.

_た

だし

,

$I^{*}( \pi)*(i)=\lim_{narrow\infty}\frac{1}{n}T*(n)(\pi^{*})w(i)$

Proof

最適方程式についての仮定より

,

全ての $i\in S$ _と任意の $f$

:

$Sarrow A$ に対 して $g+w(i)\leq T_{f}w(i)$ 即ち

,

$w(i)\leq T_{f}w(i)-g$ が得られ, 任意の $\pi.\cdot=(f_{1}, f_{2}, \cdots)\in\Pi$ に対して, 上の不等式を繰り返し適用し

,

$T$. の単調

-|‘4

を用いて

$w(i)$ $\leq$ $T_{f1}(T_{f2}w(i)-g)-g$

$=$ $T_{f1}T_{f}w(2i)-2g$

$\leq T_{f}T\cdots\tau w1J2fn(i)-ng$

上の不等式を変形して $g \leq\frac{1}{n}\sum_{t=1}nE\pi[\Gamma(_{S_{t},f}t(_{S_{t}})|_{S}1=i]+\frac{E_{\pi}[w(_{S_{t})|s_{1}=}+1i]}{n}-\frac{w(i)}{n}$ が得られ

,

定理の条件

3

より $narrow\infty$ とすると $g\leq I(\pi)(i)$

また、最適方程式を繰り返し適用して

$g= \lim_{narrow\infty}\frac{1}{n}T^{n}w(i)$ が得られ

,

よって $\lim_{narrow\infty}\frac{1}{n}Tnw(i)=\inf_{\pi}I(\pi)(i)$ 次に

,

補助定理 2,

3

と定理の条件

1,

2 より $g+w(i)=Tw(i)=T_{f^{*}}^{*}w(i)$ を満たす $f^{*}:$ $Sarrow B^{*}$ が存在する

.

そこで, この式を繰り返し適用して $w(i)=T_{\pi^{*}}^{*(n}w()i)-ng$ が得られ

,

$narrow\infty$ とすると $g= \lim\underline{1}T_{\pi^{*}}^{*}(n)w(i)$ $narrow\infty n$ かくて, 定理の結果が得られ証明は終わる

.

口

References

[1] $\mathrm{J}.\mathrm{P}$.Aubin, Optima and Equilibria –An Introduction to Nonlinear Analysis,

Springer-Verlag, New York, 1993.

[2] $\mathrm{J}.\mathrm{P}$.Aubin,Mathematical MethodsofGame and EconomicTheory, RevisedEdition,

North-Holland, Amsterdam, 1982.

[3] $\mathrm{J}.\mathrm{P}$.Aubin,

&I.Ekeland,

Applied Nonlinear Analysis, Wiley-Interscience, 1984.

[4] $\mathrm{J}.\mathrm{P}$.Aubin,

&H.Frankowska,

Set-Valued Analysis, Birkh\"auser, Boston, 1990.

[5] $\mathrm{D}.\mathrm{P}$.Bertsekas and S.E.Shreve, Stochastic Optimal Control: The Discrete Time Case,

Aca-demic Press, New York, 1978.

[6] D.Blackwell, Discrete dynamic programming, Ann. Math. Statist. 33 (1962) 719-726.

[7] D.Blackwell, Discounted dynamic programming, Ann. Math. Statist. 36 (1965) 226-235.

[8] $\mathrm{R}.\mathrm{M}$.Dudley, RealAnalysis and Probability, Wadsworth&Brooks, 1989.

[9] $\mathrm{E}.\mathrm{B}$.Dynkin and $\mathrm{A}.\mathrm{A}$.Yushkevich, Controlled Markov Processes, Springer-Verlag,

Berlin,

1979.

[10] I.Ekeland, On the variational principle, J.Math.Anal.Appl., 47 (1974) 324-353.

[11] I.Ekeland, Nonconvexminimization problems, Bull. Amer. Math.,47 (1979) 443-474.

[12] K.Hinderer, Foundations of non-stationary dynamic programming with discrete time

pa-rameter, Lecture Notes on Operations Research and Mathematical Systems 33, Springer-Verlag, Berlin, 1970.

[13] S.Iwamoto, Reverse function, reverse program, and reverse theorem in mathematical

pro-gramming, J. Math. Anal. Appl. 95 (1983) 1-19.

[14] S.Iwamoto, AdynamicInversion of the classical variationalproblems,J. Math.Anal. Appl.

100 (1984) 354-374.

[15] $\mathrm{D}.\mathrm{G}$.Luenberger, OptimizationbyVector Space Methods, John Wiley&Sons, inc., 1969.

[16] $\mathrm{R}.\mathrm{T}$.Rockafellar, Extension of Fenchel’s duality theorem for convex functions. Duke Math.

J. 33 (1966) 81-89.

[17] K.Tanaka, On discounted dynamic programming with constraints, J. Math. Anal. Appl.

155 (1991) 264-277.

[18] K.Tanaka, On a perturbation of dynamic programming, Lecture Notes in Economic and

Mathematical Systems, Springer-Verlag, Berlin, 419 (1995) 275-287.

[19] K.Tanaka, M.Hoshino, ans D.Kuroiwa, On a perturbation ofcontinuous time Markov

de-cision processes, Proceedings ofAPORS’94, edited by M.Fushimi and K.Tone, World

Sci-entific, (1995) 320-329.

[20] K.Tanaka, M.Hoshino, and D.Kuroiwa, On an $\epsilon$-optimalpolicy ofdiscrete time stochastic