%\documentclass[12pt]{article}
\documentclass{llncs}
\usepackage[noend]{algorithmic}
\usepackage[ruled]{algorithm}
\usepackage{graphicx}

%\newtheorem{theorem}{Theorem}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{lemma}[theorem]{Lemma}
\newcommand{\etal}{\mbox{\it et al.}}
\newcommand{\etc}{\mbox{\it etc.}}
\newcommand{\eg}{\mbox{\it e.g.}}
\newcommand{\ie}{\mbox{\it i.e.}}
\newcommand{\Eg}{\mbox{\it E.g.}}
\newcommand{\Ie}{\mbox{\it I.e.}}
\newcommand{\new}{\mbox{KBI }}
\newcommand{\old}{\mbox{KBN }}

%\newcommand{\PROOF}[1]{\noindent \proofbegin {#1} \proofend}
%\newcommand{\proof}[1]{\noindent \proofbegin {#1} \proofend}
%\newcommand{\proofbegin}{\mbox{\bf Proof: \ }}
%\newcommand{\proofend}{\Math{\Box}}
%\newcommand{\proofend}{$\Box$}
\newcommand{\comment}[1]{}

\newcommand{\ds}[2]{\textit{Downstream}\ensuremath{(#1,#2)}}
\newcommand{\pd}[2]{\textit{Policydesc}\ensuremath{(#1,#2)}}
\newcommand{\equ}[1]{\textit{Equiv}\ensuremath{(#1)}}
\newcommand{\equp}[1]{\textit{Equiv}\ensuremath{^+(#1)}}
%\newtheorem{lemma}{Lemma}
%\newenvironment{proof}{\noindent{\bf Proof }}{\hspace*{\fill} 
%      \textbf{QED}\vspace{1ex}}

\newcommand{\ps}[2]{\textit{Downstream}\ensuremath{(#1,#2)}}

\begin{document}

\title{Finding Best $k$ Policies}
\author{                                                                            
Peng Dai\inst1,                                                        
% \thanks{URL: .}                                                                   
% \quad and \quad                                                                   
Judy Goldsmith\inst2                                                             
}                                                                                   
                                                                                    
                                                                                    
\institute{%     
Computer Science \& Engineering
University of Washington, Seattle WA 98195-2350\\                      
http://www.cs.washington.edu/homes/daipeng, 
\email{daipeng@cs.washington.edu}\\                          
\and                                                                                
Univ. of Kentucky, Dept. of Comp. Sci.                                           
Lexington, KY, USA 40506-0046 \\ 
http://www.cs.uky.edu/\symbol{126}goldsmit,
\email{goldsmit@cs.uky.edu}
}                                             

%\date{}
\maketitle
\begin{abstract}                                                                    
An optimal probabilistic-planning algorithm solves a problem, usually modeled by a Markov decision process, by finding its optimal policy. In this paper, we study the \emph{$k$ best policies} problem. The problem is to find the $k$ best policies. %ranked by the expected value of the initial state, tie-broken by the ``closeness" to a better policy, followed by the lexical order on the policies. When $k=1$, this is the optimal planning problem. 
The $k$ best policies, $k>1$, cannot be found directly using
dynamic programming. Na\"ively, finding the $k$-th best policy can be Turing reduced to the optimal planning problem, but the number of problems queried in the na\"ive algorithm is exponential in $k$. We show empirically that solving $k$ best policy problem by using this reduction requires unreasonable amounts of time even when $k=3$.  
We then provide a new algorithm, based on our theoretical contribution to prove that the $k$-th best policy differs from the $i$-th policy, for some $i<k$, on exactly
one state. We show that the time complexity of the algorithm is quadratic in $k$, but the number of optimal planning problems it solves is linear in $k$. We demonstrate empirically that the new algorithm has good scalability. 
\end{abstract}                                                                      


\section{Introduction}

Markov Decision Processes (MDPs)~\cite{b57} are a powerful and
widely-used formulation for modeling probabilistic planning
problems~\cite{bdh99,bg00}. For instance, NASA researchers use MDPs to
model the Mars rover decision making problems~\cite{bdmrsw02,bjmr05}.
MDPs are also used to formulate military operations
planning~\cite{atz04} and
coordinated multi-agent planning~\cite{mcgdb07}, \etc

An optimal planner typically takes an MDP model of a problem and outputs
an optimal plan. This is not always sufficient.  In many
cases, a planner is expected to generate more than one solution. 
%For
%example, in adaptive routing, a system must be able to adjust routes
%during network congestion or in case of a link failure. The process of
%rerouting usually involves pre-computation of backup routes (plans).
%Human drivers might plan different routes, in case of traffic or
%distractions.  In academic advising, in order to provide a student with
%diversity and backup plans, an advisor might offer her advisee several
%plans. 
%In completing an article writing task, a requester of Amazon mechanical Turk~\cite{turk} sometimes 
%creates several identical jobs ahead of time in case of any unqualified drafts.

Furthermore, in the modeling phase, not every aspect of  nature can
be easily factored in a problem representation. For the case of NASA
rover, for example, there are many safety constraints that need to be
satisfied~\cite{bjmr05}. An optimal plan might be very close to a risky value---but
another may not have many risks and so it is better to prefer the
slightly suboptimal one. Similarly there are many decision criteria---probability 
of reaching the goal, expected reward, expected risk,
various preferences, \etc\ Combining them into a single
criterion is hard, and multi-objective planning is too
slow~\cite{gp06,bck07}. Thus, a good alternative is to look for many
suboptimal plans given a single criterion and later pick one that looks
the best according to all criteria.

In this paper, we look at the \emph{$k$ best policies} problem. Given an
MDP model, the problem is to find the $k$ best policies, ranked by the
expected value of the initial state, tie-broken by the ``closeness" to a better policy, followed by lexical order of the
policies. The classical optimal planning problem is a special case of
the $k$ best policy problem where $k=1$. The optimal planning problem can be
solved by \emph{dynamic programming}, as the property of the optimality
of sub-problems holds. The $k$ best policy problem 
%does not have this
%property, so it cannot 
be directly solved by dynamic programming.
However, finding the $k$-th best policy can be brute-force reduced to
exponentially many instances of the optimal planning problem.  Our
experiments show that solving the $k$ best policy problem this way
requires unreasonable time even when $k=3$.

A very similar problem has been explored by Nielsen, et al. 
\cite{neilsen:ejor:06,neilsen:orl:06,neilsen:cor:05}.
Nielsen and Kristensen observed that the problem of finding optimal 
\emph{history-dependent} policies (maps from the state space crossed
with the time step to the action space) can be modeled as finding ``a minimum weight hyperpath"
in directed hypergraphs.  A vertex in the hypergraph represents a state of the MDP
at a particular time;  the hypergraphs are, therefore, acyclic.
They present an elegant and efficient algorithm for finding the
$k$ best time-dependent policies for an MDP.  
%THEIRS is |V|^2*|A|*n*k, where n is time time horizon.
%OURS is |V|^2*|A|*n*|V|*|A| (the first factors are the complexity of DP algs.)
%I bet we can speed ours up some, but not that much.
However, their algorithm cannot handle MDPs with probabilistic cycles,
therefore its usefulness is limited.


Our new solution to the $k$ best policy problem follows from the
property: \emph{The $k$-th best policy differs from a better policy  on
exactly one state.} We propose an original algorithm for the $k$ best
policy problem that leverages this property. We demonstrate both
theoretically and empirically that the new algorithm has low complexity
and good scalability.
%Therefore, it is practical in solving real MDP problems.

\section{Background}

\subsection{Markov Decision Processes}

AI researchers often use MDPs to formulate probabilistic planning problems.
An MDP is defined as a four-tuple $\langle {\cal S}, {\cal A}, T, C\rangle$, where ${\cal 
S}$ is a finite set of discrete states, ${\cal A}$ is a finite set of all applicable actions, 
$T$ is the transition matrix describing the domain dynamics, and $C$ denotes the cost of 
action transitions.

The agent executes its actions in discrete time steps called \emph{stages}. At each 
stage, the system is at one distinct state $s\in {\cal S}$. The agent can pick any action 
$a$ from a set of \emph{applicable actions} $Ap(s)\subseteq {\cal A}$, incurring a cost of 
$C(s,a)$. The action takes the system to a new state $s'$ stochastically, with 
probability $T_{a}(s'|s)$.

The \emph{horizon} of an MDP is the number of stages for which costs are accumulated. 
%For ease of illustration, 
We focus our attention on a special set of MDPs called \emph{stochastic 
shortest path} (SSP) problems. The horizon in such an MDP is indefinite and the costs are 
accumulated with no discounting. There are an initial state $s_0$, and a set of sink
\emph{goal states} ${\cal G}\subseteq {\cal S}$. Reaching any state $g\in {\cal G}$
terminates the execution. The cost of the execution is the sum of all costs along the 
path from $s_0$ to $g$. 
%Despite its simplicity, SSP is a general representation. 
Any infinite horizon discounted reward MDP can easily be converted to an 
undiscounted SSP~\cite{bt96}.

To solve the MDP we need to find an \emph{optimal policy} ($\pi^*:{\cal S}\rightarrow 
{\cal A}$), a probabilistic execution plan that reaches a goal state with the minimum 
expected cost. We evaluate any policy $\pi$ by a \emph{value function}. 
\[
V_{\pi}(s)=C(s,\pi(s))+\sum_{s' \in {\cal S}}T_{\pi(s)}(s'|s)V_{\pi}(s').
\] 
Any optimal policy must satisfy the following system of \emph{Bellman equations}:

\begin{eqnarray}
\label{optval}
V^*({s}) &=& 0 ~~~\mbox{if $s\in {\cal G}$ else} \\
\nonumber V^*({s}) &=& {\min_{a\in {Ap(s)}}[C(s,a)+\sum_{s'\in {\cal S}}T_a(s'|s)V^*(s')]}.
\end{eqnarray}

The corresponding optimal policy can be extracted from the value function:
\[
\pi^*({s})=argmin_{{a}\in {Ap(s)}} [C({s},{a})+\sum_{s'\in {\cal S}}T_{a}({s'}|{s})V^*({s'})].
\]

\subsection{Dynamic Programming}

We define a \emph{sub-problem} of an MDP with state space ${\cal S'}\subseteq{\cal S}$ to be a self-contained MDP with state space ${\cal S'}$ and  associated action transitions. We define the \emph{sub-policy} of a policy $\pi$ given a sub-problem with state space ${\cal S'}\subseteq{\cal S}$ to be the mapping from all $s\in{\cal S'}$ to $\pi(s)$. An optimal policy satisfies the following necessary and sufficient condition: for any sub-problem, the corresponding sub-policy is also optimal. Many optimal MDP algorithms are based on dynamic programming. Its usefulness was first 
proved by a simple yet powerful algorithm called \emph{value iteration} (VI)~\cite{b57}. Value 
iteration first initializes the value function arbitrarily. Then  the values are updated 
iteratively using an operator called \emph{Bellman backup} to create successively better 
approximations per state per iteration. Value iteration stops updating when the value 
function converges (one future backup can change a state value by at most $\epsilon$, a pre-defined threshold).   

Another algorithm, named \emph{policy iteration} (PI)~\cite{h60}, starts from an arbitrary policy and iteratively improves the policy. Each iteration of PI consists of two sequential steps. The first step, \emph{policy evaluation}, finds the value function of the current policy. Values are calculated by solving the system of linear equations (in the original PI algorithm), or by iteratively updating the value functions in the VI manner till convergence
% (in an improved algorithm called \emph{modified policy iteration}~\cite{p94}). 
(modified policy iteration \cite{p94}). The second step, \emph{policy improvement}, updates the current policy by choosing a greedy action per state by a one step lookahead, based on the value function calculated in the policy evaluation step. PI stops when the policy improvement step
% finds the same policy.
doesn't change the policy.

\comment{
Let's write a policy $\pi$ by a 2-tuple $(V_{\pi}(s_0),\pi(s\in {\cal S}))$. $(V_{\pi}(s_0)$ is the value of the initial state under $\pi$, and $\pi(s\in {\cal S}))$ is a vector of actions for each state. The \emph{Hamming distance} between two policies $\pi$ and $\pi'$ is the total number of positions for which the two action vectors differ.

Within the set of policies that have value $v$, there is a lexicographically least such policy.  Let's call that $\pi_v^*$.

We order those policies with value $v$ so that policies that differ from $\pi_v^*$ by $j$ actions precede those that differ from $\pi_v^*$ by $k$ actions, when $j<k$.  For those policies with value $v$ that differ from $\pi_v^*$ on $k$ actions, we sort lexicographically.


We write $A\prec B$ iff $A$ precedes $B$ in the lexicographic order, which is a total order on alphanumeric strings.  We define a total order on policies as follows:  $\pi > \pi'$ iff $[V_{\pi}(s_0)<V_{\pi'}(s_0)$ or
$V_{\pi}(s_0)=V_{\pi'}(s_0)$ and $\pi \succ \pi']$.
Intuitively, a policy with a better (smaller) initial state value is ranked higher than one with a worse (larger) value. We further define 
\begin{eqnarray*}
\equ{\pi}&= \{&\pi'\neq \pi:\ \pd{s_0}{\pi}=\pd{s_0}{\pi'} \\
 &\wedge &\forall s\in \pd{s_0}{\pi}[\pi(s)=\pi'(s)]\}.
\end{eqnarray*}
%Note that if $\ps{s_0}{\pi}\neq \cal{S}$ then $\equ{\pi}$ is nonempty.

The problem of \emph{$k$ best policy} is to find the list of $k$ most highly ranked policies in this total order. 
}

\newcommand{\ham}{\textrm{Ham}}

\section{$k$ Best Policy Problem}

Classical dynamic programming successfully finds \emph{one} optimal policy of an MDP in time polynomial in $|{\cal S}|$ and $|{\cal A}|$~\cite{ldk95,b07}. In this paper, we 
%are interested in a more general problem: finding
find the $k$ best policies of an MDP. We first give the formal definition of the $k$ best policy problem. Then we introduce the main theoretical contribution of the paper by proving a very strong result about the $k$-th best policy.



Let $M$ be an MDP, $\pi$ a policy for $M$.  We define the \emph{policy graph} of $M$ given $\pi$, denoted by $G_{\pi}$, to be a graph constructed by: (1) the set of states (vertices) that are reachable from $s_0$ given $\pi$, and (2) their corresponding transitions in $\pi$ (edges).

Let $s$ and $s'$ be states of $M$. We say that $s'$ is a \emph{policy descendant} of $s$ with respect to $\pi$ if
there is a path from $s$ to $s'$
in $G_{\pi}$ or if $s=s'$.   We define $ \pd{s}{\pi}$ to be the set of all policy descendant states of $s$ under policy $\pi$.
We assume that, for every state $s\in{\cal S}$, there are at least two possible actions for $s$. 
%(If not, we can factor the single action's effects on $s$ into any transition leading to $s$, and remove $s$ from the model.)

Note that, for a given MDP and a given value function, there may be multiple policies with that value function.  We define a notion of ``best among equals", namely, the ``closest" to better policies followed by a lexicographic ordering, so that the notion of ``best policy'' is well defined.

\begin{lemma}\label{lem:best}
Using value iteration, we can find an optimal value function for $M$, 
and the optimal $V_{\pi^*}(s_0)$.
We can then find the lexicographically least policy, $\pi_1$,  that has that value
for $V_{\pi_1}(s_0)=V_{\pi^*}(s_0)$.
\end{lemma}

The proof of Lemma \ref{lem:best} is straightforward.  Given the value function, for each state, we choose the lexicographically first action that achieves the desired value.   (If ${\cal A}= \{a_0, a_1, \ldots, a_j\}$, the lexicographically first action satisfying a property is the lowest-numbered $a_i$ with that property.)  Once we have the \emph{best} policy, we then need to define an ordering on policies so that we may define the $k$-th best.

\begin{definition}
Given two policies $\pi$ and $\pi'$, we can 
consider them as vectors of length $|{\cal S}|$ over alphabet $|{\cal A}|$, and 
define the Hamming distance $\ham(\pi,\pi')$ to be the number of states on which $\pi$ and $\pi'$ differ.
We also define $ <_{lex}$ to be the lexicographic ordering on such vectors.
\end{definition}

Finally, we define an order on policies.

\begin{definition}
Given an MDP $M$ and a dynamic list of $p$ best policies generated so far $\{\pi_1\ldots, \pi_p\}$, the next best policy is computed based on the following ordering $\prec$ on the rest of the policies for $M$.

\begin{eqnarray*}
\begin{array}{lll}
\pi\prec \pi' & \mbox{\bf if } & V_{\pi}(s_0)< V_{\pi'}(s_0)\\
 & \mbox{\bf else if } & min_{j\leq p}\ham(\pi_j, \pi) < min_{j\leq p}\ham(\pi_j, \pi')\\
 & \mbox{\bf else if } & \pi <_{lex}\pi'.\\
 \end{array}
\end{eqnarray*}
\end{definition}

Intuitively, two policies with the same initial state value are first compared by how ``close" each one is to some better policy, followed by   lexicographic order if they are equally close.  

%\begin{lemma}
%Let $M$ be an MDP, 
%and let $\pi$ be a policy for $M$ with $\pd{s_0}{\pi}\neq {\cal S}$.  Then $\equ{\pi}$ is nonempty, so the set 
%$\equp{\pi} = \equ{\pi}\cup \{\pi\}$ has at least two elements, all of which have the same value $V_{\pi}(s_0)$.  
%Then for any $\pi' \in \equp{\pi} $ there is a $\pi''\in \equp{\pi} $ such that $\pi'$ and $\pi''$ differ on exactly one state.
%\end{lemma}

\begin{theorem}\label{thm:main}
Let $M$ be an MDP, and let $\{\pi_1, \ldots, \pi_k\}$ be the $k$ best policies for $M$, in order.
Let $k\geq 1$.  Then there is some $m<k$ such that $\pi_k$ differs from $\pi_m$ on exactly one state.
\end{theorem}

%
%\begin{corollary}
%Given an MDP $M$ and $k+1$ best policies $\Pi_{k+1}=\{\pi_1\ldots, \pi_{k+1}\}$, and some $\pi \notin \Pi_k$,
%then $min_{j\leq k}\ham(\pi_j, \pi)\leq min_{j\leq k+1}\ham(\pi_j, \pi)+1$.
%\end{corollary}
%In other words, that minimum Hamming distance can shrink\footnote{shrink or increase? Also, why we care about this Corollary?} by at most one when $\pi_{k+1}$ is also considered.

The proof sketch to Theorem \ref{thm:main} is provided in the Appendix.

\section{Algorithm}

\begin{algorithm}[ht!]
   \caption{$k$ best na\"ive (KBN)}
  \label{alg:bf}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} $M$ (an MDP), $k$
   \STATE find best policy $\pi_1$ by VI
   \STATE $\Pi\leftarrow\{\pi_1\}$
   \FOR {$i\leftarrow 2$ to $k$}
   \STATE $\pi_i\leftarrow$ best policy that differs from any policy $\pi\in\Pi$ by at least one state
   \STATE $\Pi\leftarrow\Pi\cup\{\pi_i\}$
   \ENDFOR
   \STATE return $\pi_1,\ldots,\pi_k$
\end{algorithmic}
\end{algorithm}

\comment{
We already know that the optimality on sub-problems of $k$-th best policy does not hold. However, we can transform the problem and  reduce it to many optimal planning problems, and solve them each by dynamic programming. Before illustrating the reduction, we present our first algorithm's high-level pseudo-code of in Algorithm~\ref{alg:bf}. We call it \emph{$k$ best na\"ive} algorithm (KBN), as it is based on the following simple reduction (an expansion of Algorithm~\ref{alg:bf} Line 5).

Note that the $i$-th best policy is the best policy among ones that are different from any policy $\pi\in\Pi$. More concretely, when $i=2$,
\[
\pi_2=argmin_{\pi}\ s.t.\ \overline{(\pi(s_0)=\pi_1(s_0))\wedge\ldots\wedge(\pi(s_{|{\cal S}|})=\pi_1(s_{|{\cal S}|}))},
\]
or equivalently,
\[
\pi_2=argmin_{\pi}\ s.t.\ (\pi(s_0)\neq\pi_1(s_0))\vee\ldots\vee(\pi(s_{|{\cal S}|})\neq\pi_1(s_{|{\cal S}|})).
\]
This suggests a two-step method. First, we change the MDP by constraining  it to be different from one action of the best policy, and solve the remaining MDP by value iteration. We do this once for each state-action pair of the best policy.  Second, we pick the best policy of those calculated in the first step. The first step involves solving $|{\cal S}|$ new MDPs, i.e., $|{\cal S}|$ calls to value iteration. The second step has $|{\cal S}|$ comparisons. So, the complexity of finding the second best policy is $|{\cal S}|\times O(value\ iteration)$.

This algorithm does not scale as $i$ increases. For example, when $i=3$,
\begin{eqnarray}
\nonumber \pi_3=argmin_{\pi}\ s.t.\ \overline{(\pi(s_0)=\pi_1(s_0))\wedge\ldots\wedge(\pi(s_{|{\cal S}|})=\pi_1(s_{|{\cal S}|}))} \\
\nonumber \wedge \overline{(\pi(s_0)=\pi_2(s_0))\wedge\ldots\wedge(\pi(s_{|{\cal S}|})=\pi_2(s_{|{\cal S}|}))}, 
\end{eqnarray}
or equivalently,
\begin{eqnarray}
\label{equ:third}
\nonumber \pi_3=argmin_{\pi}\ s.t.\ (\pi(s_0)\neq\pi_1(s_0)\wedge\pi(s_0)\neq\pi_2(s_0))\vee\ldots \\
 \vee (\pi(s_{|{\cal S}|})\neq\pi_1(s_{|{\cal S}|})\wedge\pi(s_{|{\cal S}|})\neq\pi_2(s_{|{\cal S}|})). 
\end{eqnarray}
Equation~\ref{equ:third} contains $|{\cal S}|^2$ disjuncts, so when we use the same two-step method as for the second best policy, the first step involves  $|{\cal S}|^2$ calls to value iteration.

Generalizing our computation above to $k$, \old has a complexity $|{\cal S}|^k\times O(value\ iteration)$, an exponential function of $k$.
}

Consider the $k$-th ($k>1$) best policy of an MDP $M$, called $\pi_k$. The necessary and sufficient condition of the optimality on sub-problems does not hold. With the loss of the optimality on sub-problems, dynamic programming is not immediately applicable. However, we can reduce it to many optimal planning problems, each solved by dynamic programming. Before illustrating the reduction, we present the high-level idea of our first algorithm in Algorithm~\ref{alg:bf}. We call it \emph{$k$ best na\"ive} algorithm (KBN), as it is a brute force algorithm that doesn't use Theorem~\ref{thm:main}. KBN is based on the following observation:
The $k+1$-st best policy must differ from each of the $k$ best 
policies on at least one state.  
%This can be operationalized by enumerating
We can enumerate the possible sets of state/action pairs the 
new policy must avoid, and find an optimal policy for each
thus-constrained MDP, then take the best of those policies.

For instance, given the best and second best policies, $\pi_1$ and $\pi_2$,
to find $\pi_3$, we say that either it differs from $\pi_1$ on $s_0$
and from $\pi_1$ on $s_0$, or from $\pi_1$ on $s_0$
and from $\pi_1$ on $s_1$, or....  In this case, we solve $|{\cal S}|^2$
many optimal planning problems.  To find the $k$-th best policy, we
solve $|{\cal S}|^k$ many.  Each newly-computed policy will be 
compared with the best policy computed so far, so that the number
of comparisons is linear in the number of policies computed.
Suppose we use VI to solve those optimal planning problems, \old has a complexity $|{\cal S}|^k\times O(VI)$, an exponential function of $k$.

Some of these combinations of
constraints may constrain away all actions for a particular state,
%in which case they will 
so do not yield a next-best policy.  However,
the next best policy must be among those computed, and will be
the best such.

\begin{algorithm}[ht!]
   \caption{$k$ best improved (KBI)}
  \label{alg:kbest}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} $M$ (an MDP), $k$
   \STATE find best policy $\pi_1$ by VI
   \STATE ${\cal P}\leftarrow$ empty set
   \FOR {$i\leftarrow 2$ to $k$}
%   \STATE generate distinct $k-i+1$ best policies that each differs from $\pi_{i-1}$ on exactly one state and add them to ${\cal P}$
      \STATE generate distinct $k-i+1$ best policies that each differs from $\pi_{i-1}$ on exactly one state and differs from $\{\pi_1,\ldots,\pi_{i-1}\}$ and insert them into ${\cal P}$ in order, discarding duplicates   
       \STATE $\pi_i\leftarrow$ \ the best policy in ${\cal P}$
       \STATE  delete $\pi_i$ from ${\cal P}$
   \ENDFOR
   \STATE return $\pi_1,\ldots,\pi_k$
\end{algorithmic}
\end{algorithm}

Using Theorem~\ref{thm:main}, we have a new algorithm, called \emph{$k$ best improved} (KBI). The KBI pseudo-code is shown in Algorithm~\ref{alg:kbest}. KBI keeps a set of candidate policies ${\cal P}$, which is initially empty. We first find the optimal policy by value iteration. To find the $i$-th best policy, we generate $k-i+1$ distinct policies as candidates.
%for potential $k$ best policies. 
These candidates (1) must not be duplicates of any policy in ${\cal P}$, and (2) each differs from $\pi_{i-1}$ on exactly one state. We have the following theorem.
\begin{theorem}
\label{the:ith}
The $i$-th best policy must be an element of ${\cal P}$.
\end{theorem}
\begin{proof}
As we know from Theorem~\ref{thm:main} that the $i$-th ($i\leq k$) best policy is exactly one state different from one of $\pi_1,\ldots,\pi_{i-1}$, say, $\pi_j$, where $j<i$.  Therefore, it must have been generated when $\pi_{j+1}$ was computed. 
Since it is the $i$-th best policy, it would have been amongst the
$i-j$-th best of those policies that are one state different from
$\pi_j$, so it belongs to the $k-j$ best policies added to ${\cal P}$ at stage
$j+1$.

%So $\pi_i$ must be among a set of policies $\Pi_i$, which contains $i-j$ best policies that are one state different from $\pi_j$ for each $j=1,2,\ldots,i-1$. On the other hand, ${\cal P}$ contains all distance $k-j$ best policies that each differs from $\pi_{j}$ on exactly one state. Since $i\leq k$, $\Pi_i\subseteq {\cal P}$.
\end{proof}

%Using Theorem~\ref{the:ith}, 
Thus, we find the $i$-th best policy by picking the best policy in ${\cal P}$.
%
There are $(|{\cal A}|-1)\times|{\cal S}|$ policies that are exactly one state different from $\pi_i$. Finding the best $k-i$ of them has a complexity $|{\cal A}|\times|{\cal S}|\times O(policy\ evaluation)$, plus the complexity of keeping the list ${\cal P}$ in sorted order ($O(k^2\log k)$). \new computes these policies $k-1$ times, so its complexity is $(k-1)\times|{\cal A}|\times|{\cal S}|\times O(policy\ evaluation)$, a linear function of $k$.  (Note that the sorting term is dominated by $|{\cal A}|\times|{\cal S}|\times O(policy\ evaluation)$.)

\section{Experiments}

We address the following three questions in our experiments: (1) How does \new compare with \old on different problems and $k$ values? (2) Does \new scale well on large $k$ values? (3) How different are the $k$ best policies from the optimal policy?

We implemented \old and \new in C. We performed all experiments on a 2.2GHz Dual-Core Intel(R) Core(TM)2 Processor with 6GB memory. We picked problems from three domains, namely Racetrack~\cite{bbs95}, Single-arm pendulum (SAP) and Double-arm pendulum (DAP)~\cite{ws05}. We used a threshold value of $\epsilon=10^{-6}$.

\subsection{Comparing \new and \old}

\begin{table*}[tp!]
\begin{center}
\footnotesize{
\begin{tabular}{|c|r||r|r||r|r||r|r|}
\hline
Domain & States & \multicolumn{2}{|c||}{$k=2$} & \multicolumn{2}{c||}{$k=3$} & \multicolumn{2}{c|}{$k=4$} \\
& $|{\cal S}|$ & \old & \new & \old & \new & \old & \new \\
&  &  &  & (expected) &  & (expected) & \\
\hline
DAP 1 & 625 & 0.90 & 0.44 & $10^2$ & 0.87 & $10^5$ & 1.32 \\
\hline
Racetrack 1 & 1,847 & 0.56 & 0.07 & $10^3$ & 0.14 & $10^6$ & 0.21 \\
\hline
SAP 1 & 2,500 & 12.39 & 2.58 & $10^4$ & 4.93 & $10^7$ & 7.29 \\
\hline
SAP 2 & 10,000 & 461.87 & 66.15 & $10^6$ & 131.30 & $10^{10}$ & 196.46 \\
\hline
DAP 2 & 10,000 & 944.14 & 333.97 & $10^6$ & 665.89 & $10^{10}$ & 1001.23 \\
\hline
Racetrack 2 & 21,371 & 11.10 & 2.02 & $10^{5}$ & 4.03 & $10^{9}$ & 6.02 \\
\hline
\end{tabular}
\vspace{.3in}
\caption{
Running time (seconds) of \old and \new in various problems with different $k$ values. The running time of \old on $k>2$ are expectations. \new outperforms \old on most problems by an order of magnitude even when $k=2$.}
\label{tab:large}
}
\end{center}
\end{table*}


We compare \old and \new on a suite of six problems of various sizes. The running times of both algorithms when $k=2$ are listed in Table~\ref{tab:large}. We see that \new outperforms \old on all problems. In four problems, the speedup is an order of magnitude. According to our analysis in the Algorithm section, when $k$ increases by 1, the running time of \old increases by a factor of $|{\cal S}|$, so for cases $k=3$ and $k=4$ we take the expectations of its running time based on its performance on the same problem when $k=2$. Even for small $k$ values, the running times of \old are prohibitively high. For example, in SAP 2 problem, its expected running time is approximately one thousand hours for $k=3$ and tens of millions of hours for $k=4$. %This shows that \old is not even suitable for very small problems unless $k$ is very small.

\subsection{The scalability of \new}

\begin{figure*}[ht!]
\begin{center}
{\includegraphics[scale=0.48]{figures/dap5time.pdf}}
{\includegraphics[scale=0.48]{figures/smalltime.pdf}}
{\includegraphics[scale=0.48]{figures/sap50time.pdf}}
{\includegraphics[scale=0.48]{figures/sap100time.pdf}}
{\includegraphics[scale=0.48]{figures/dap10time.pdf}}
{\includegraphics[scale=0.48]{figures/bigtime.pdf}}
%\vspace*{-0.07in}
\caption{Running time (seconds) of \new when $k=2,\dots,100$ on DAP 1, Racetrack 1, SAP 1, SAP 2, DAP 2, Racetrack 2 problems (left to right, top to bottom). The running times increase linearly in $k$ for all problems.}
\label{fig:time}
\end{center}
\end{figure*}

In this experiment we investigate whether the \new algorithm scales to large $k$ values. We run \new for $k=100$ on the same set of problems, and record the elapsed times when it finishes generating the $i$-th best policy ($i=2,\ldots,k$) of each problem. Figure~\ref{fig:time} clearly shows that, for all problems \new spends times linear in $k$ when calculating $k$-th best policies. This experiment indicates that \new has good scalability.

\subsection{How $k$ best policies differ from the optimal}

\begin{figure*}[ht!]
\begin{center}
{\includegraphics[scale=0.48]{figures/dap5dist.pdf}}
{\includegraphics[scale=0.48]{figures/smalldist.pdf}}
{\includegraphics[scale=0.48]{figures/sap50dist.pdf}}
{\includegraphics[scale=0.48]{figures/sap100dist.pdf}}
{\includegraphics[scale=0.48]{figures/dap10dist.pdf}}
{\includegraphics[scale=0.48]{figures/bigdist.pdf}}
%\vspace*{-0.07in}
\caption{ the total number of different states between the $k$-th best policy and the optimal policy when $k=2,\dots,100$ on DAP 1, Racetrack 1, SAP 1, SAP 2, DAP 2, Racetrack 2 problems (left to right, top to bottom). All $k$ best policies are quite close to their $\pi_1$'s.}
\label{fig:dist}
\end{center}
\end{figure*}

We are also curious to know how the $k$ best policies differ from the optimal policy. We analyze the list of $k$ best policies calculated in the previous experiment, and compare the total number of different states, $d$, between each of these policies and the optimal policy $\pi_1$ for each problem. 
%We find $d$ interesting since it carries critical information for the problem. 
When $d$ is small for a problem, it means that the $k$ best policies are very similar to the optimal policy. This shows that z%the optimal policy is loosely coupled, \ie,  
many good policies can be generated by a few small changes to the optimal policy. In other words, changes to few states can have very little impact on the optimality of the rest of the policy. When $d$ is large, the optimal policy is more tightly coupled. 
%Intuitively this means w
When a sub-optimal action is chosen for a state, in order to get a good sub-optimal plan, changes to other states are usually also required.

We plot the $d$ values for the $k$ best policies on the same set of problems in Figure~\ref{fig:dist}. 
%Note, first, that all 
These problems have relatively low $d$ values ($<20$ for all $k$). This shows that the $k$ best policies are always quite close the the optimal policies. Some problems have relatively higher $d$ values than others, namely SAP 1, DAP 2, and Racetrack 2, which means they have relatively tightly coupled optimal policies. As these problems are from diverse domains and of different sizes, it seems that the tightness of coupling of the optimal policies is probably problem-dependent.


\section{Conclusions}

This paper makes several contributions.
First, we introduce the $k$ best policy problem, and argue for its importance.   
%
Second, we prove a strong and useful theorem that the $k$-th best policy differs from some $m(<k)$-th best policy on exactly one state. Without that result, the brute-force algorithm for solving the $k$ best policy problem (KBN) has time complexity exponential in $k$.
%
Third, we propose a new algorithm, named $k$ best policy improved (KBI), based on our theorem. We show that the time complexity of KBI is dominated by a computation linear in $k$.
%
Fourth, we demonstrate that \new outperforms \old by an order of magnitude when $k=2$ in most cases. The \old algorithm does not scale to larger $k$ values, as its running time increases exponentially in $k$. On the other hand, the running time of \new increases only linearly in $k$. This makes \new suitable for problems for which we want a long list of best policies.
%
Fifth, we notice that  the $k$ best policies for different MDPs  are quite similar to the optimal policies, though
some problems' optimal policies are more tightly coupled than others'.

This is just the beginning of work on $k$ best policies.  There is much to be done in improving the algorithms, and in looking at applications-driven variants.

\section*{Acknowledgments}

Dai was partially supported by Office of Naval Research grant N00014-06-1-0147. 
Goldsmith was partially supported by NSF grant ITR--0325063.
We thank Mausam for helpful discussions on the problem.

\footnotesize{
\bibliographystyle{splncs}
\bibliography{kbestdb}
}


\section*{Appendix}

%We prove that, if $\pi_1\prec \pi_k$, then there is some $j<k$ and some $s\in{\cal S}$ such that $\pi_j$ differs
%from $\pi_k$ only on $s$.   We observe, first, that there are several ways that $\pi_1\prec \pi_k$ can hold.
%Either $V_{\pi_1}(s_0) < V_{\pi_k}$, or  $V_{\pi_1}(s_0) = V_{\pi_k}(s_0)$ but $\pi_1 <_{lex} \pi_k$.  Remember
%that the ordering of policies, relative to some list $\Pi$ policies is first by initial value  ($V_{\pi}(s_0)$) and then on
%the minimum Hamming distance to elements of $\Pi$, and then on the lexicographic ordering within the distance equivalence classes.

%Thus, if $V_{\pi_1}(s_0) < V_{\pi_k}$, Theorem \ref{thm:main} follows immediately.

In order to prove Theorem \ref{thm:main}, we 
consider the effects of changing a policy one state at a time.

\begin{lemma}\label{lem:dec}
Let $M$ be an MDP, and $\pi$ and $\pi'$ be two policies for $M$ that differ only on state $s$.  Suppose that $V_{\pi}(s) \leq V_{\pi'}(s)$.  Then $V_{\pi}(s_0) \leq V_{\pi'}(s_0)$.
More strongly, if $s\in \pd{s_0}{\pi}$ (which implies $s\in \pd{s_0}{\pi'}$) and $V_{\pi}(s) < V_{\pi'(s)}$, then $V_{\pi}(s_0) < V_{\pi'(s_0)}$.
\end{lemma}

\begin{proof}
We know the values of $V_{\pi}(s)$ and $V_{\pi'}(s)$ are two unknown constants with $V_{\pi}(s) \leq V_{\pi'}(s)$. We write the two systems of linear equations with respect to $\pi$ and $\pi'$ by ignoring variables $V_{\pi}(s)$ and $V_{\pi'}(s)$ on the left hand side, and replacing them with their values whenever they are on the right hand side. We find the two systems of equations have the same set of coefficients, but the one given $\pi$ has smaller or equal constant values on the right hand sides. If we solve the equations by factoring out all the variables on the right hand side iteratively, the same process as replacing a variable by its corresponding state's \emph{influence}~\cite{mm99}, we finally get the same value for all states where $s$ is not a policy descendant given $\pi'$, since all states' influences are the same in $\pi$ and $\pi'$, and a better value in $\pi$ for all states where $s$ is a policy descendant given $\pi'$, since the influence of $s$ on them is decreased (due to a smaller value), where the influence of other states remain unchanged. We call this property \emph{monotonicity of influence}. This implies $V_{\pi}(s_0) \leq V_{\pi'}(s_0)$. Here, we actually proved a more general result, namely that $\forall s' \in {\cal S}[V_{\pi}(s') \leq V_{\pi'}(s')]$.
\end{proof}

\begin{lemma}\label{lem:better}
Let $M$ be an MDP, and $\pi$ and $\pi'$ be two policies for $M$ that differ only on state $s$.  Suppose that $V_{\pi}(s _0) < V_{\pi'}(s_0)$.  Then $V_{\pi}(s) < V_{\pi'}(s)$. More strongly, $\forall s'\in {\cal S}$, $[V_{\pi}(s') \leq V_{\pi'}(s')]$.
\end{lemma}

\begin{proof}[Sketch]
Suppose that $V_{\pi}(s) \geq V_{\pi'}(s)$.

%It is first clear that $\forall s'\notin \pd{s_0}{\pi'}$, $[V_{\pi}(s) = V_{\pi'}(s)]$.

We divide the states in $\pd{s_0}{\pi'}$ into two subsets: (1) \emph{policy ancestors of $s$ given $\pi'$}, the set of states where $s$ is a policy descendant given $\pi'$, and (2) \emph{non-policy ancestors of $s$ given $\pi'$}, the complement of (1).

We claim that the values of the non-policy ancestors of $s$ given $\pi'$ are the same as those given $\pi$. This is because the values of those states do not depend on $s$ or any policy ancestors of $s$ given $\pi'$, so their values are not influenced by any potential value changes caused by $s$. For policy ancestors of $s$ given $\pi'$, their values cannot be improved, by the monotonicity of influence. Because their coefficients remain unchanged while the constants (values of non-policy ancestors of $s$ given $\pi'$ and value of $s$) are equal or larger. This contradicts the assumption that $V_{\pi}(s_0) < V_{\pi'}(s_0)$.
%
Now, we know that $V_{\pi}(s) < V_{\pi'}(s)$. From Lemma~\ref{lem:dec} we have that $\forall s'\in {\pd{s_0}{\pi'}}$ $[V_{\pi}(s) \leq V_{\pi'}(s)]$.
\end{proof}


%XXXXX
\begin{lemma}\label{lem:two}
Let $M$ be an MDP, and $\pi$ and $\pi'$ be two policies for $M$ that differ only on two states $s^1$ and $s^2$.  Suppose that $V_{\pi}(s_0) \leq V_{\pi'}(s_0)$.  Consider the following two policies $\pi^1, \pi^2$ obtained from by starting with $\pi$ by replacing exactly one distinct action each from $\pi(s)$, $s\in\{s^1, s^2\}$, with the corresponding $\pi'(s)$. Without loss of generality, suppose $\pi^i(s^i)=\pi'(s^i)$.
Then $\pi^1$ and $\pi^2$ cannot  both have larger initial state values than $\pi'$ does.
\end{lemma}

%Lemma \ref{lem:two} can be proved using Lemma \ref{lem:dec} and \ref{lem:better}.

\begin{proof}[Sketch]
%We skip the case where both $s^1$ and $s^2$ are not policy descendants of $s_0$ given $\pi$ or $\pi'$, as it is a simpler case and can be proved similarly.
For either $s^i$, if $s^i$ is not a policy descendant of $s_0$ given $\pi$ or $\pi'$, then $V_{\pi'}(s_0) = V_{\pi^i}(s_0)$, and we're done.  
 
 Now suppose $V_{\pi'}(s_0)< V_{\pi^i}(s_0)$ for $i=1,2$.
 %Suppose the Lemma is wrong. 
 From Lemma \ref{lem:better}, we have
\begin{eqnarray}
\label{inequ:1} \forall s'\in {\cal S} [V_{\pi'}(s') \leq V_{\pi^1}(s')], \mbox{ and } V_{\pi'}(s^2) < V_{\pi^1}(s^2),\\
\label{inequ:2} \forall s'\in {\cal S} [V_{\pi'}(s') \leq V_{\pi^2}(s')], \mbox{ and } V_{\pi'}(s^1) < V_{\pi^2}(s^1).
%\label{inequ:3} \forall s'\in \pd{s_0}{\pi^1}, [V_{\pi'}(s) \leq V_{\pi^1}(s)],\ V_{\pi'}(s^1) < V_{\pi^1}(s^1)\\
%\label{inequ:4} \forall s'\in \pd{s_0}{\pi^2}, [V_{\pi'}(s) \leq V_{\pi^2}(s)].\ V_{\pi'}(s^2) < V_{\pi^2}(s^2)\\
\end{eqnarray}
There are three cases.
Case 1: Neither $s^1$ nor $s^2$ is a policy descendant of the other given $\pi$. From Equation \ref{inequ:1} we know $V_{\pi'}(s^2) < V_{\pi^1}(s^2) = V_{\pi}(s^2)$, as the values of all policy descendants of $s_2$ given $\pi^1$ and $\pi$ are the same, and $\pi^1(s^2)=\pi(s^2)$. From Equation \ref{inequ:2} we know $V_{\pi'}(s^1) < V_{\pi^2}(s^1) = V_{\pi}(s^1)$ for the same reason. Then from the monotonicity of influence together with all derived inequalities, we know $V_{\pi'}(s_0) < V_{\pi}(s_0)$. A contradiction.

Case 2: $s^2$ is a policy descendant of $s^1$ given $\pi$, but $s^1$ is not a policy descendant of $s^2$ given $\pi$ (or vice versa). From Equation \ref{inequ:1} we first know $V_{\pi'}(s^2) < V_{\pi^1}(s^2) = V_{\pi}(s^2)$. From Equation \ref{inequ:2}, and $V_{\pi'}(s^2) <  V_{\pi}(s^2)$, by the monotonicity of influence we know $V_{\pi'}(s^1) < V_{\pi}(s^1)$. Then, from the monotonicity of influence together with all derived inequalities, we know $V_{\pi'}(s_0) < V_{\pi}(s_0)$. A contradiction.

Case 3: $s^1$ and $s^2$ are both policy descendants of each other given $\pi'$. From both Equations \ref{inequ:1} and \ref{inequ:2} and the monotonicity of influence we can prove $V_{\pi'}(s^1) < V_{\pi}(s^1)$ and $V_{\pi'}(s^2) < V_{\pi}(s^2)$. Then from the monotonicity of influence together with all derived inequalities, we know $V_{\pi'}(s_0) < V_{\pi}(s_0)$. A contradiction.

\end{proof}
%XXXXX


\begin{lemma}\label{lem:m}
Let $M$ be an MDP, and $\pi$ and $\pi'$ be two policies for $M$ that differ only on $m$ states $s^1, s^2, \ldots, s^m$, 
$m>1$.  Suppose that $V_{\pi}(s_0) = V_{\pi'}(s_0)$.  Consider the $2^m$ distinct policies $\pi^T$, $ T\subseteq \{s^1, s^2, \ldots, s^m\}$ that agree with $\pi$ on all states not in $T$, and agree with $\pi'$ on $T$.   Then for at least one such $T$ of size $1$, $V_{\pi^T}(s_0) \leq V_{\pi'}(s_0)$.
%such policy cannot have a larger initial state values than $\pi$ does.
\end{lemma}

%\begin{proof}

%Suppose not.  Then for each $\pi^{\{s^i\}}$, we have that $V_{\pi^{\{s^i\}}}(s_0) > V_{\pi}(s_0)$. Let $\pi_{Tk}=\pi^{\{s^1,\ldots, s^k\}}$.  Then we claim that for each $s\in {\cal S}$, we have $V_{\pi_{T1}}(s)\leq V_{\pi_{T2}}(s)\leq \ldots \leq V_{\pi_{Tm}}(s)$ by induction on the argument given in Lemma \ref{lem:two}.  This gives us $V_{\pi}(s) < V_{\pi_{T1}}(s)\leq V_{\pi_{Tm}}(s) = V_{\pi'}(s).$ In particular, this implies that $V_{\pi}(s_0) < V_{\pi'}(s)$, contradicting our initial assumption.

%\end{proof}
This Lemma can be proved inductively from Lemma \ref{lem:m}.


Note that a fundamental assumption underlying dynamic programming algorithms for MDPs is:
If $M$ is a MDP and $\pi$ a non-optimal policy (in the sense of having a non-optimal value function), then there is some $s\in {\cal S}$ and $a \in {\cal A}$ such that
$v_{\pi}(s) > C(s,a) + \gamma \sum_{s'\in {\cal S}} T_a(s'|s)\cdot v_{\pi}(s').$
Bertsekas and Tsitsiklis showed that this holds for stochastic shortest path problems, when $\gamma = 1$ \cite{bertsekas:mor:91}.
Their proof can be extended.
\begin{lemma}\label{lem:BT}
If If $V_{\pi}(s_0)$ is not optimal, there must be an $s^+\in \pd{s_0}{\pi}$ and $a\in {\cal A}$ such that
$v_{\pi}(s^+) > C(s^+,a) +\sum_{s'\in {\cal S}} T_a(s'|s^+,)\cdot v_{\pi}(s')$.  If we let $\pi'(s)=\pi(s)$ for $s\neq s^+$, and let $\pi'(s^+)=a$, then $V_{\pi'}(s_0) < V_{\pi(s_0)}$.
\end{lemma}


%\begin{proof}
%If we have such an $a$ and  $s^+\in \pd{s_0}{\pi}$, this follows immediately from Lemma \ref{lem:dec}.  

%If $s\notin  \pd{s_0}{\pi}$,
%then $v_{\pi}(s_0)=v_{\pi'}(s_0)$.  By Bertsekas and Tsitsiklis' proof of the convergence of policy iteration on stochastic shortest path problems, there must be another $s$ such that changing $\pi(s)$ actually improves  the value of $s_0$.  That $s$ must therefore be in $\pd{s_0}{\pi}$.
%\end{proof}


\begin{proof}[Theorem \ref{thm:main}]
Let $M$ be an MDP, and $\Pi_i = \{\pi_1, \ldots, \pi_i\}$ be the list of $i$ best policies, for $i\leq k$.  We claim that,
for $k>1$, there is some $j<k$ and state $s$ such that $\pi_j$ differs from $\pi_k$ exactly on $s$.

If $V_{\pi_k}(s_0) =  V_{\pi_1}(s_0)$,  the theorem follows from Lemma \ref{lem:m}.

If $V_{\pi_k}(s_0) > V_{\pi_1}(s_0)$,  
 the theorem follows from  Lemma \ref{lem:BT}.

\end{proof}

\end{document}