\documentclass[10pt]{article}
\renewcommand{\baselinestretch}{1.5}
\usepackage{epsfig}
\usepackage{subfigure}
\newcommand\s{{\bf s}}
\newcommand\x{{\bf x}} 
\newcommand\y{{\bf y}} 
\newcommand\p{{\bf p}} 
\newcommand\e{{\bf e}} 
\renewcommand\a{{\bf a}} 
\renewcommand\b{{\bf b}} 

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\setlength{\textheight}{22cm} \setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0pt} \setlength{\evensidemargin}{1pt}
\setlength{\oddsidemargin}{1pt} \setlength{\headsep}{10pt}
\parskip=2mm
\parindent=8mm

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{remark}[theorem]{Remark}
\begin{document}

\title{CME307/MS\&E311 Suggested Course Project III: Value-Iteration Method for MDP}
%\author{(You don't need to answer all the questions posted in the project)}
\maketitle

As described in Lectures, Rainforcement Learning (RL) and Markov Decision Processes (MDP) provide a mathematical framework for 
modeling sequential decision-making in situations where outcomes are partly random and partly under the control of a 
decision maker. MDPs are useful for studying a wide range of optimization problems solved via Dynamic Programming (DP), where it was 
known at least as early as the 1950s (cf. Shapley 1953, Bellman 1957). Modern applications include dynamic planning, reinforcement learning, social networking, and almost all other dynamic/sequential decision game strategy making problems in Mathematical, Physical, Management and Social Sciences.

As talked in class, the MDP problem with $m$ states and total $n$ actions can be formulated as a standard form linear program with
$m$ equality constraints and $n$ variables:
\begin{equation}\label{mdplp}
\begin{array}{rccccl}
\mbox{min}_{\x}  &\sum_{j\in {\cal A}_1}c_jx_j  +   &...        &+\sum_{j\in {\cal A}_m}c_jx_j  &  &   \\
\mbox{s.t.} & \sum_{j\in {\cal A}_1}(\e_1-\gamma \p_j)x_j +&...&+\sum_{j\in {\cal A}_m}(\e_m-\gamma \p_j)x_j&=&\e,\\
                  &     ...         &x_j    &   ...     &\ge &0,\ \forall j,
\end{array}
\end{equation}
where ${\cal A}_i$ represents the set of all actions available in state $i$, $\p_{j}$ is the state transition probabilities from state 
$i$ to all states and $c_j$ is the immediate cost when action $j$ is taken, and $0<\gamma<1$ is the discount factor. Also,
$\e\in R^m$ is the vector of ones, and $\e_i$ is the unit vector with $1$ at the $i$-th position and zeros everywhere else.
Variable $x_j,\ j\in {\cal A}_i$, is the state-action frequency or flux, or the expected present value of the number of times in which the process visits state $i$ and takes state-action $j\in {\cal A}_i$. Thus, solving the problem entails choosing a state-action frequencies/fluxes that minimize the expected present value sum of total costs. The dual of the LP is
\begin{equation}
\begin{array}{rccl}
\mbox{maximize}_{\y}&\e^T\y=\sum_{i=1}^my_i&    \\
\mbox{subject to} &y_1-\gamma \p_{j}^T\y&\le &c_{j},\ j\in {\cal A}_1\\
                           &  & \vdots  &\\
                           &y_i -\gamma \p_{j}^T\y &\le &c_{j},\ j\in {\cal A}_i\\
                           &  & \vdots  &\\
                           &y_m-\gamma \p_{j}^T\y&\le &c_{j},\ j\in {\cal A}_m.
\end{array}
\end{equation}
where $y_i$ represents the cost-to-go value in state $i$.

\begin{enumerate}
\item {\bf Question 1:} Prove that in (\ref{mdplp}) every basic feasible solution represent a policy, i.e., the basic variables have exactly one variable from each state $i$. Furthermore, prove each basic variable value is no less than $1$, and the sum of all basic variable values
is $\frac{m}{1-\gamma}$.

\item {\bf Question 2:} Value Iteration Method: This is a first-order optimization method -- starting with any vector $\y^0$, then iteratively update it
\begin{equation}\label{VI}
y^{k+1}_i=\min_{j\in {\cal A}_i}\{ c_{j}+\gamma \p_{j}^T\y^k\},\ \forall i.
\end{equation}
Prove the contraction result:
\[ \|\y^{k+1}-\y^*\|_{\infty}\le \gamma \|\y^{k}-\y^*\|_{\infty},\ \forall k.\]
where $\y^*$ is the fixed-point or optimal value vector, that is,
\[y^*_i=\min_{j\in {\cal A}_i}\{ c_{j}+\gamma \p_{j}^T\y^*\},\ \forall i.\]

\item {\bf Question 3:} In the VI method, if starting with any vector $\y^0\ge \y^*$ and assuming $\y^1\le \y^0$, then prove the following entry-wise monotone property:
\[\y^*\le \y^{k+1}\le \y^k,\ \forall k.\]
On the other hand, if we start from a vector such that 
\[y^0_i <\min_{j\in {\cal A}_i}\{ c_{j}+\gamma \p_{j}^T\y^0\},\ \forall i\]
($\y^0$ in the interior of the feasible region), then prove the entry-wise monotone property:
\[\y^*\ge \y^{k+1}\ge \y^k,\ \forall k.\]
This monotone property has been used in a recent paper (see \cite{SWWY17}) on the VI method using samples.

\item {\bf Question 4:} Rather than go through all state values in each iteration, we modify the VI method, call it RamdomVI:
In the $k$th iteration, randomly select a subset of states $B^k$ and do
\begin{equation}\label{randomVI}
y^{k+1}_i=\min_{j\in {\cal A}_i}\{ c_{j}+\gamma \p_{j}^T\y^k\},\ \forall i\in B^k.
\end{equation}
In RandomVI, we only update a subset of state values at random in each iteration.

What can you tell the convergence of the RandomVI method? Does it make a difference with the classical VI method? How is the sample size affect the performance? Use simulated computational experiments to verify your claims.

Rather than randomly select a subset of all states in each iteration, suppose we build an ``influence tree'' from a given subset of states, say $B$, for all sates, denoted by $I(B)$, that are connected by any state in $B$. Then when states in $B$ are updated in the current iteration, then selected a subset of states in $I(B)$ for updating in the next iteration. Redo the computational experiments using this strategy for a sparsely connected ($\p_j$ is a very sparse distribution vector for each action $j$) MDP network. In doing so, many unimportant or irrelevant states may be avoided which results a state-reduction.

\item {\bf Question 5:} Here is another modification, called CyclicVI: In the $k$th iteration do 
\begin{itemize}
\item Initialize $\tilde{\y}^k=\y^k$.

\item For $i=1$ to $m$
\begin{equation}\label{CyclicVI}
\tilde{y}^{k}_i=\min_{j\in {\cal A}_i}\{ c_{j}+\gamma \p_{j}^T\tilde{\y}^k\}
\end{equation}

\item $\y^{k+1}=\tilde{\y}^k$.
\end{itemize}
In the CyclicVI method, as soon as a state value is updated, we use it to update the rest of state values.

What can you tell the convergence of the CyclicVI method? Does it make a difference with other VI methods? Use simulated computational experiments to verify your claims. How is this cyclic method related to the method at the bottom of Question 4?

\item {\bf Question 6:} In the CyclicVI method, rather than with the fixed cycle order from $1$ to $m$, we follow a random permutation order, or sample without replacement to update the state values. More precisely, in the $k$th iteration do 

\begin{itemize}
\item[0.] Initialize $\tilde{\y}^k=\y^k$ and $B^k=\{1,2,...,m\}$

\item[1.] 
\begin{itemize}
\item Randomly select $i\in B^k$

\item \begin{equation}\label{RcyclicVI}
\tilde{y}^{k}_i=\min_{j\in {\cal A}_i}\{ c_{j}+\gamma \p_{j}^T\tilde{\y}^k\}
\end{equation}
\item remove $i$ from $B^k$ and return to Step 1.
\end{itemize}

\item[3.] $\y^{k+1}=\tilde{\y}^k$.
\end{itemize}
We call it the randomly permuted CyclicVI or RPCyclicVI in short

What can you tell the convergence of the RPCyclicVI method? Does it compare with other VI methods? Use simulated computational experiments to verify your claims.
\end{enumerate}

In this project, you may generate a Maze Game in 2D by assign actions with different costs and probability distributions to test your algorithms.

\item {\bf Question 7:} Tic-Tac-Toe Game: In this problem, we want to develop the optimal strategy for the cross-player. We assume that the cross-player plays first, and the opponent is a random player. That is, the opponent puts a circle in an empty square with equal probability in each round. Please formulate the $3\times3$ tic-tac-toe game as an MDP problem and find the optimal policy. 

In addition, what can you tell about the optimal first step for the cross player in the $4\times4$ tic-tac-toe game? 

\begin{thebibliography}{1}
\bibitem[Ber13]{bertsekas2013abstract}
Dimitri~P Bertsekas.
\newblock {\em Abstract dynamic programming}.
\newblock Athena Scientific, Belmont, MA, 2013.

\bibitem[HMZ13]{hansen13}
Thomas~Dueholm Hansen, Peter~Bro Miltersen, and Uri Zwick.
\newblock Strategy iteration is strongly polynomial for 2-player turn-based
  stochastic games with a constant discount factor.
\newblock {\em J. ACM}, 60(1):1:1--1:16, February 2013.

\bibitem[How60]{howard1960dynamic}
Ronald~A. Howard.
\newblock {\em Dynamic programming and {M}arkov processes}.
\newblock The MIT press, Cambridge, MA, 1960.

\bibitem[LDK95]{littman1995complexity}
Michael~L Littman, Thomas~L Dean, and Leslie~Pack Kaelbling.
\newblock On the complexity of solving markov decision problems.
\newblock In {\em Proceedings of the Eleventh conference on Uncertainty in
  artificial intelligence}, pages 394--402. Morgan Kaufmann Publishers Inc., 1995.

\bibitem[Put14]{puterman2014markov}
Martin~L Puterman.
\newblock {\em {M}arkov decision processes: discrete stochastic dynamic
  programming}.
\newblock John Wiley \& Sons, 2014.

\bibitem[Sch13]{scherrer2013improved}
Bruno Scherrer.
\newblock Improved and generalized upper bounds on the complexity of policy
  iteration.
\newblock In {\em Advances in Neural Information Processing Systems}, pages
  386--394, 2013.

\bibitem[SWWY17]{SWWY17}
Aaron Sidford, Mengdi Wang, Xian Wu, Yinyu Ye.
\newblock Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes.
\newblock SODA2018 and https://arxiv.org/abs/1710.09988

\bibitem[Ye11]{ye2011simplex}
Yinyu Ye.
\newblock The simplex and policy-iteration methods are strongly polynomial for
  the markov decision problem with a fixed discount rate.
\newblock {\em Mathematics of Operations Research}, 36(4):593--603, 2011.

\end{thebibliography}

\end{document}


