### Without delays

##### Description:
Trading problem:
We will trade a item on infinite time horizon. The item only has 5 possible prices: 3,4,5,6,7, the following table gives transition matrix, the element $p_{ij}$ represents the probability from current price $i$ to next price $j$. The possible inventory positions are -1, 0, 1 where -1 represents shorting one item and 1 represents longing one item. At each time step, we observe the price and change our position immediately, then we will hold the position till the next time step. Profit is given by the P&L at next time step, plus a transaction fee with a rate $\gamma$ per item.

| i\\j | 3   | 4   | 5   | 6   | 7
| ---  | --- | --- | --- |--- |--- |
| 3    | 0.0 | 1.0 | 0.0 | 0.0 | 0.0
| 4    | 0.25| 0.0 | 0.75| 0.0 | 0.0
| 5    | 0.0   | 0.5 | 0.0 | 0.5 | 0.0
| 6    | 0.0   | 0.0 | 0.75| 0.0 | 0.25
| 7    | 0.0   | 0.0 | 0.0 | 1.0 | 0.0

##### Formulation:
* Stages: $i = 1,2,\cdots$.
* State Space: $\mathcal{X} = \{-1, 0, 1\}\times\{3,4,5,6,7\}$, $x_t = (q_t, p_t)$ where $q_t$ is the number of items on hand, $p_t$ is the current price of this item.
* Control Space: $\mathcal{U} = \{-1,0,1\}$, holding position from current time step to next time step. Position will be immediately changed and be kept till the next time step.
* Feasible control mapping $\mathcal{X}\rightarrow\mathcal{U}: \mathcal{U}(x)=\{-1,0,1\}$
* Transition mapping, given $x_i, u_i$, $\mathcal{X}\rightarrow [0,1]$, for $i\in \{1,2,\cdots\}$. It is not difficult to see that $q_{t+1}=u_t$ by the definition of $u$. Price process is Markovian and it changes independently from $q_t$, and it follows above table.

For $q_t$:
$$P(q_{i+1} \mid q_i, u_i) = 
\begin{cases}
1,\quad &q_{i+1}=u_i\\
0, \quad & o.w.
\end{cases}
 $$
 
For $p_t$:
 $$P(p_{i+1} \mid p_i, u_i) =  
\begin{cases}
0.25\cdot (p_i-3),\quad &p_{i+1}=p_i-1\\
1-0.25\cdot (p_i-3), \quad &p_{i+1}=p_i+1\\
0, \quad & o.w.
\end{cases}
 $$
* Reward function $\mathcal{X}\times\mathcal{U}\rightarrow\mathbb{R}$: 
$$r(x_t, u_t)=r((q_t, p_t), u_t)=\mathbb{E}[p_{t+1}-p_t\mid p_t]\cdot u_t-|u_t-q_t|\cdot \gamma$$
The first term is profit & loss and the last term is transaction cost.
* Let $v^*(x)$ be the optimal value function for state $x$, so it satisfies the following equation:

\begin{align}
    v^*(x_i) = &\max_{u\in \mathcal{U}(x)}\{r(x_i, u)+\alpha\mathbb{E}[v^*(x_{i+1})]\}\\
\end{align}

And it can be solved by value iteration:

\begin{align}
    v^{k+1}(x_i) = \mathcal{D}(v)(x_i) = &\max_{u\in \mathcal{U}(x)}\{r(x_i, u)+\alpha\mathbb{E}[v^k(x_{i+1})]\}\\
\end{align}
with arbitrary $v^0$, since $\mathcal{D}$ is a contraction mapping.


```python

```


```python
from itertools import product
import numpy as np
import pandas as pd
from copy import deepcopy
import random
```


```python
state_space = list(product([-1,0,1], [3,4,5,6,7]))
control_space = [-1,0,1]
gamma = 0.2
alpha = 0.95
def trans_prob(next_x, x, u):
    q, p = x
    next_q, next_p = next_x
    if next_q != u:
        return 0.0
    else:
        if next_p == p - 1:
            return 0.25*(p-3)
        elif next_p == p + 1:
            return 1-0.25*(p-3)
        else:
            return 0.0
def reward(x, u):
    q, p = x
    # E[next_p-p]*u = (1-0.5*(p-3))*u
    return (1-0.5*(p-3))*u-abs(u-q)*gamma
```


```python
v = pd.DataFrame({x:[0.0]*3 for x in [3,4,5,6,7]}, index = [-1,0,1])
pi = pd.DataFrame({x:[0]*3 for x in [3,4,5,6,7]}, index = [-1,0,1])
```


```python
def value_iteration(state_space, control_space, trans_prob, reward, alpha, v, pi, MAX_ITER = 1000000, threshold = 1e-6):
    for _ in range(MAX_ITER):
        next_v = deepcopy(v)
        for x in state_space:
            tmp = [reward(x, u)+alpha*
                   np.sum([v.loc[next_x[0], next_x[1]]*trans_prob(next_x, x, u) for next_x in state_space]) 
                   for u in control_space]
            next_v.loc[x[0], x[1]] = np.max(tmp)
            pi.loc[x[0], x[1]] = np.argmax(tmp)-1
        if abs(next_v-v).values.max()<1e-6:
            break
        else:
            v = next_v
            
    return v, pi
```


```python
v, pi = value_iteration(state_space, control_space, trans_prob, reward, alpha, v, pi)
```


```python
v
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>-1</th>
      <td>6.466842</td>
      <td>5.775624</td>
      <td>5.676842</td>
      <td>6.175624</td>
      <td>6.866842</td>
    </tr>
    <tr>
      <th>0</th>
      <td>6.666842</td>
      <td>5.975624</td>
      <td>5.676842</td>
      <td>5.975624</td>
      <td>6.666842</td>
    </tr>
    <tr>
      <th>1</th>
      <td>6.866842</td>
      <td>6.175624</td>
      <td>5.676842</td>
      <td>5.775624</td>
      <td>6.466842</td>
    </tr>
  </tbody>
</table>
</div>




```python
pi
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>-1</th>
      <td>1</td>
      <td>1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
    </tr>
    <tr>
      <th>0</th>
      <td>1</td>
      <td>1</td>
      <td>0</td>
      <td>-1</td>
      <td>-1</td>
    </tr>
    <tr>
      <th>1</th>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>-1</td>
      <td>-1</td>
    </tr>
  </tbody>
</table>
</div>



### With observation delays $o=1$

* Stages: $i = 1,2,\cdots$.
* State Space: $\mathcal{I} = \mathcal{X}\times\mathcal{U}= \{-1, 0, 1\}\times\{3,4,5,6,7\}\times\{-1, 0, 1\}$, $I_t = (x_{t-1}, u_{t-1}) = ((q_{t-1}, p_{t-1}), u_{t-1})$ where $q_{t-1}$ is the number of stocks on hand, $p_{t-1}$ is the price process at time step $t-1$.
* Control Space: $\mathcal{U} = \{-1,0,1\}$
* Feasible control mapping $\mathcal{I}\rightarrow\mathcal{U}: \mathcal{U}(x)=\{-1,0,1\}$
* Transition mapping， given $I_k, u$, $\mathcal{X}\rightarrow [0,1]$, for $i\in \{1,2,\cdots\}$

$$P'(I_{k+1} \mid I_k, u) = P'((x_{k}, u_{k}) \mid (x_{k-1}, u_{k-1}), u)= 
\begin{cases}
P(x_k\mid x_{k-1}, u_{k-1}), &\quad u_k=u\\
0, &\quad o.w.\\
\end{cases}
$$
 
<!-- * Policy $\pi': \mathcal{I}\rightarrow \mathcal{U}$, $\pi: \mathcal{X}\rightarrow \mathcal{U}$
$$u_k = \pi'(I_k)=\pi'(s_{k-1}, a_{k-1})=\pi(M(s_{k-1}, a_{k-1}))$$
where $M(x,u)=argmax_{x'\in\mathcal{X}}P(x'\mid x,u)$ -->
* Reward function $\mathcal{I}\times\mathcal{U}\rightarrow\mathbb{R}$: 
$$r^{(1)}(I_k, u_k) = \mathbb{E}[r(x_k,u_k)\mid I_k]$$
$$r^{(2)}(I_k, u_k)=r(x_{k-1}, u_{k-1})$$



```python
state_space_d = list(product([-1,0,1], [3,4,5,6,7], [-1, 0, 1]))
control_space = [-1,0,1]
gamma = 0.2
alpha = 0.95
def trans_prob_d(next_x, x, u):
    q, p , a = x
    next_q, next_p, next_a = next_x
    if u == next_a:
        return trans_prob((next_q,next_p), (q, p), a)
    else:
        return 0.0
def reward_1(x, u):
    q, p, a = x
    # E[r(x_k, u_k)|(x_{k-1}, u_{k-1})]
    return np.sum([trans_prob(x_k, (q, p), a)*reward(x_k, u) for x_k in state_space])
    # E[next_p-p]*u = (1-0.5*(p-3))*u

def reward_2(x, u):
    q, p, a = x
    # E[next_p-p]*u = (1-0.5*(p-3))*u
    return reward((q, p), a)
```


```python
v_1 = np.array([0.0 for _ in state_space_d])
pi_1 = np.array([0 for _ in state_space_d])
```


```python
def value_iteration(state_space, control_space, trans_prob, reward, alpha, v, pi, MAX_ITER = 1000000, threshold = 1e-6):
    for _ in range(MAX_ITER):
        next_v = deepcopy(v)
        for x_idx, x in enumerate(state_space):
            tmp = [reward(x, u)+alpha*
                   np.sum([v[next_x_idx]*trans_prob(next_x, x, u) 
                           for next_x_idx, next_x in enumerate(state_space)]) 
                   for u in control_space]
            next_v[x_idx] = np.max(tmp)
            pi[x_idx] = control_space[int(np.argmax(tmp))]
#         print(next_v)
        if abs(next_v-v).max()<threshold:
            break
        else:
            v = next_v
            
    return v, pi
```


```python
v_1, pi_1 = value_iteration(state_space_d, control_space, trans_prob_d, reward_1, alpha, v_1, pi_1)
```


```python
v_1
```




    array([2.37389249, 2.57389249, 2.77389249, 1.99357187, 2.19357187,
           2.39357187, 2.08389249, 2.08389249, 2.08389249, 2.39357187,
           2.19357187, 1.99357187, 2.77389249, 2.57389249, 2.37389249,
           2.37389249, 2.57389249, 2.77389249, 1.99357187, 2.19357187,
           2.39357187, 2.08389249, 2.08389249, 2.08389249, 2.39357187,
           2.19357187, 1.99357187, 2.77389249, 2.57389249, 2.37389249,
           2.37389249, 2.57389249, 2.77389249, 1.99357187, 2.19357187,
           2.39357187, 2.08389249, 2.08389249, 2.08389249, 2.39357187,
           2.19357187, 1.99357187, 2.77389249, 2.57389249, 2.37389249])




```python
pi_1
```




    array([ 1,  1,  1,  1,  1,  1, -1,  0,  1, -1, -1, -1, -1, -1, -1,  1,  1,
            1,  1,  1,  1, -1,  0,  1, -1, -1, -1, -1, -1, -1,  1,  1,  1,  1,
            1,  1, -1,  0,  1, -1, -1, -1, -1, -1, -1])




```python
v_2 = np.array([0.0 for _ in state_space_d])
pi_2 = np.array([0 for _ in state_space_d])
```


```python
v_2, pi_2 = value_iteration(state_space_d, control_space, trans_prob_d, reward_2, alpha, v_2, pi_2)
```


```python
v_2
```




    array([1.25519687, 2.24519687, 3.23519687, 1.39389249, 1.88389249,
           2.37389249, 1.97969687, 1.77969687, 1.57969687, 2.77389249,
           1.88389249, 0.99389249, 3.63519687, 2.24519687, 0.85519687,
           1.05519687, 2.44519687, 3.43519687, 1.19389249, 2.08389249,
           2.57389249, 1.77969687, 1.97969687, 1.77969687, 2.57389249,
           2.08389249, 1.19389249, 3.43519687, 2.44519687, 1.05519687,
           0.85519687, 2.24519687, 3.63519687, 0.99389249, 1.88389249,
           2.77389249, 1.57969687, 1.77969687, 1.97969687, 2.37389249,
           1.88389249, 1.39389249, 3.23519687, 2.24519687, 1.25519687])




```python
pi_2==pi_1
```




    array([ True,  True,  True,  True,  True,  True,  True,  True,  True,
            True,  True,  True,  True,  True,  True,  True,  True,  True,
            True,  True,  True,  True,  True,  True,  True,  True,  True,
            True,  True,  True,  True,  True,  True,  True,  True,  True,
            True,  True,  True,  True,  True,  True,  True,  True,  True])



### With action delays $a=1$

* Stages: $i = 1,2,\cdots$.
* State Space: $\mathcal{I} = \mathcal{X}\times\mathcal{U}= \{-1, 0, 1\}\times\{3,4,5,6,7\}\times\{-1, 0, 1\}$, $I_t = (x_{t}, u_{t-1}) = ((q_{t}, p_{t}), u_{t-1})$ where $q_t$ is the number of stocks on hand, $p_t$ is the price process at time step $t$.
* Control Space: $\mathcal{U} = \{-1,0,1\}$
* Feasible control mapping $\mathcal{I}\rightarrow\mathcal{U}: \mathcal{U}(x)=\{-1,0,1\}$
* Transition mapping， given $I_k, u$, $\mathcal{X}\rightarrow [0,1]$, for $i\in \{1,2,\cdots\}$

$$P'(I_{k+1} \mid I_k, u) = P'((x_{k+1}, u_{k}) \mid (x_{k}, u_{k-1}), u)= 
\begin{cases}
P(x_{k+1}\mid x_{k}, u_{k-1}), &\quad u_k=u\\
0, &\quad o.w.\\
\end{cases}
$$
<!--  
* Policy $\pi': \mathcal{I}\rightarrow \mathcal{U}$, $\pi: \mathcal{X}\rightarrow \mathcal{U}$
$$u_k = \pi'(I_k)=\pi'(s_{k-1}, a_{k-1})=\pi(M(s_{k-1}, a_{k-1}))$$
where $M(x,u)=argmax_{x'\in\mathcal{X}}P(x'\mid x,u)$ -->
* Reward function $\mathcal{I}\times\mathcal{U}\rightarrow\mathbb{R}$: 
$$r^{(1)}(I_k, u_k) = \mathbb{E}[r(x_{k+1},u_k)\mid I_k]$$
$$r^{(2)}(I_k, u_k)=r(x_{k}, u_{k-1})$$



```python

```

d55057001ab35340deb3b48a49134244afdd38ce
ipynb
Jupyter Notebook
Delayed_MDP-Copy1.ipynb
Theling/Delayed_MDP
db1a8808a05917a5915220947cf65268f0524fa9
MIT
Delayed_MDP-Copy1.ipynb
Theling/Delayed_MDP
db1a8808a05917a5915220947cf65268f0524fa9
MIT
Delayed_MDP-Copy1.ipynb
Theling/Delayed_MDP
db1a8808a05917a5915220947cf65268f0524fa9
MIT
Qwen/Qwen-72B
1. YES
2. YES