1.1 Martingale sequences: examples and further patterns  (Page 2/3)

Suppose the observed state is j and the action is $a\in A$ . Two results ensue:

1. A return $r(j,a)$ is realized
2. The system moves to a new state

Let:

$Y_n=$ state in n th period, $0\le n\le N-1$

$A_n=$ action taken on the basis of $Y_0,A_0,\cdots ,Y_{n-1},A_{n-1},Y_n$

[ A ₀ is the initial action based on the initial state Y ₀ ]

A policy π is a set of functions $({\pi }_0,{\pi }_1,\cdots ,{\pi }_{N-1})$ , such that

The expected return under policy π , when $Y_0=j_0$ is

The goal is to determine π to maximize $R(\pi ,j_0)$ .

Let $Z_k=(Y_k,A_k)$ and $W_n=(Z_0,Z_1,\cdots ,Z_n)$ . If $\{Y_k:0\le k\le N-1\}$ is Markov, then use of (CI9) and (CI11) shows that for any policy the Z -process is Markov. Hence

We assume time homogeneity in the sense that

We make a dynamic programming approach

Define recursively $f_N,f_{N-1},\cdots ,f_0$ as follows:

$f_N\left(j\right)=0,\forall j\in \mathbf{E}$ . For $n=N,N-1,\cdots ,2,1$ , set

Put

Then, by A4-2 , $(X_{\mathbf{N}},Z_{\mathbf{N}})$ is a MG, with $E\left[X_n\right]=0,0\le n\le N$ and

IX A4-4

We may therefore assert

Hence, $R(\pi ,Y_0)\le E\left[f_0\left(Y_0\right)\right]$ . For $Y_0=j_0,R(\pi ,j_0)\le f_0\left(j_0\right)$ . If a policy π ^* can be found which yields equality, then π ^* is an optimal policy.

The following procedure leads to such a policy .

• For each $j\in \mathbf{E}$ , let ${\pi }_{n-1}^{*}(Y_0,A_0,Y_1,A_1,\cdots ,A_{n-2},j)={\pi }_{n-1}^{*}\left(j\right)$ be the action which maximizes
  $${\displaystyle r(j,a)+\sum _{k\in \mathbf{E}}{f}_n\left(k\right)p\left(k\right|j,a)=r(j,a)+E\left[f_n\left(Y_n\right)\right|Y_{n-1}=j,A_{n-1}=a]}$$
  Thus, $A_n^{*}={\pi }_n^{*}\left(Y_n\right)$ .
• Now, $f_{n-1}\left(Y_{n-1}\right)=r(Y_{n-1},A_{n-1}^{*})-E\left[f_n\left(Y_n\right)\right|Z_{n-1}^{*}]$ , which yields equality in the argument above. Thus, $R({\pi }^{*},j)=f_0\left(j\right)$ and π ^* is optimal.

Note that π ^* is a Markov policy, $A_n^{*}={\pi }_n^{*}\left(Y_n\right)$ . The functions f _n depend on the future stages, but once determined, the policy is Markov.

A4-9 doob's martingale

Let X be an integrable random variable and Z _N an arbitrary sequence of random vectors. For each n , let $X_n=E\left[X\right|W_n]$ . Then $(X_{\mathbf{N}},Z_{\mathbf{N}})$ is a MG.

A4-9a best mean-square estimators

If $X\in {\mathbf{L}}^2$ , then $X_n=E\left[X\right|W_n]$ is the best mean-square estimator of X , given $W_n=(Z_0,Z_1,\cdots ,Z_n)$ . $(X_{\mathbf{N}},Z_{\mathbf{N}})$ is a MG.

A4-9b futures pricing

Let X _N be a sequence of “spot” prices for a commodity. Let t ₀ be the present and $t_0+T$ be a fixed future. The agent can be expected to know the past history $U_{t_0}=(X_0,X_1,\cdots ,X_{t_0})$ , and will update as t increases beyond t ₀ . Put $Y_k=E\left[X_{t_0+T}\right|U_{t_0+k}]$ , the expected futures price, given the history up to $t_0+k$ . Then $\{Y_k:0\le k\le T\}$ is a Doob's MG, with $Y=X_{t_0+T}$ , relative to $\{Z_k:0\le k\le T\}$ , where $Z_0=U_{t_0}$ and $Z_k=X_{t_0+k}$ for $1\le k\le T$ .

A4-9c discounted futures

Assume rate of return is r per unit time. Then $\alpha =1/(1+r)$ is the discount factor . Let

Then

Thus $\{V_k:0\le k\le T\}$ is a SMG relative to $\{Z_k:0\le k\le T\}$ .

Implication from martingale theory is that all methods to determine profitable patterns of prediction from past history are doomed to failure.

IX A4-5

A4-10 present discounted value of capital

If $\alpha =1/(1+r)$ is the discount factor, X _n is the dividend at time n , and V _n is the present value, at time n , of all future returns, then