\documentclass{article}

\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage[ruled,linesnumbered]{algorithm2e}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amsfonts}

\usetikzlibrary{positioning,shapes,calc,through,intersections,fit}

\tikzset{
  flowchart/.style={
      process/.style={rounded rectangle, draw,align=center},
      decision/.style={diamond, aspect=2, draw,align=center},
      transition/.style={draw,->},
      dataflow/.style={->,dashed},
    },
    mnemonic/.style={
      label={[fill=blue!30]120:#1}
    }
}

\title{New stackelberg equilirbium mixed strategy method overview}

\begin{document}
\maketitle

\section{Introduction}
TODO

\section{Supported game model}%
\label{sec:game-model}

We consider a two-player game with the following properties: 
\begin{itemize}
\item perfect recall,
\item imperfect information,
\item deterministic,
\item multi-act.
\end{itemize}

Multi act game is modeled as a tree of successive states.  Imperfect
information is modeled by information sets: a player does not know the
exact state of the game. He knows only a that current state belongs to
some information set and cannot distinguish the exact
state. Information sets are presented in Figure~\ref{fig:is-game} If information sets
are singletons the game is of perfect
information. Perfect recall is a property that ensures that player
remembers all previous states and moves --- no successors of two
distinct information sets may belong to the same information set and
each player's own move leads to different information set. 

Figure~\ref{fig:circ-game} presents the game as seen from
players~$\circ$ perspective. Even if the game is deterministic, from
single player's point of view some moves may result in different
states (information sets). The exact result depends on moves played by
other players. 



\begin{figure}
  \centering
  \input{sem1/igame}
  \caption{Imperfect information two player game. Node shapes denote
    player who makes decision in given node. $i_k$ denote information
    sets of player $\circ$. Moves in each information set are
    indistinguishable.}%
  \label{fig:is-game}
\end{figure}

\begin{figure}
  \centering
  \input{sem1/ogame}
  \caption{A game from Figure~\ref{fig:is-game} seen from player
    $\circ$ perspective.}%
  \label{fig:circ-game}
\end{figure}

\subsection{Stackelberg equilibrium}

Stackelberg Game is an asymmetric, non-zero-sum game involving two
players: the \emph{Leader} and the \emph{Follower}.
Both players commit to a mixed strategy --- a probability distribution
over possible moves in every reachable state.
The \emph{Leader} commits to his strategy first and the follower
commits to the strategy already knowing opponent's strategy. 

Given the \emph{Leader's} strategy, finding the optimal strategy for the
\emph{Follower} is straightforward. Devising the optimal \emph{Leader's}
strategy defined by a game equilibrium state is much more challenging and requires huge computational resources for non-trivial games.

In latter sections the leader will be called defender and the follower
is called attacker. 

\section{Overview}\label{sec:overview}

The idea is to find the search attacker pure strategy space, evaluate
each strategy by finding the best defender mixed strategy that induced the
evaluated attacker, calculate the defender's payoff and use it as the
(attacker's) strategy quality evaluation.

The attacker strategy space search is done using Monte Carlo Tree
Search/Upper Confidence Bound applied to Trees method.  MCTS is
applied to a special game where the player defines attacker's pure
strategy, described in Section~\ref{sec:linearized-game}.
In a leaf (terminal) state of such game a history of
moves in defines the whole attacker's pure strategy. When MCTS reaches
a leaf
state it asks the oracle for a defender's mixed strategy that:
\begin{itemize}
\item induces requested attacker's pure strategy,
\item optimized defender's reward under the first constraint.
\end{itemize}
If no such defender strategy was found --- return some penalty else
defender's payoff is returned. This procedure is presented in Figure.

\begin{figure}
  \centering
  \input{mcts-evaluate-flowchart}
  \caption{Use of MCTS/UCT search policy to choose attacker's strategy to
    evaluate. Red node represents a procedure for search of defender's
  strategy that induces given attacker's strategy described in latter section.}%
  \label{fig:mcts-search-flowchart}
\end{figure}

Besides the tree, which is used only to direct attacker's strategy
space search, the best (in terms of defender's payoff) strategy across
all reached leaves is updated after each leaf evaluation Stored
strategy is returned as the best possible strategy.

The oracle providing exact or approximate defender's strategy can be
implemented in various ways, currently used method is presented in
Section~\ref{sec:def-strategy}

\subsection{Game defining attacker's pure strategy}%
\label{sec:linearized-game}


\section{Defender strategy search method}%
\label{sec:def-strategy}

This section describes a method for finding a defender's mixed
strategy inducing given attacker's pure strategy.
This attacker's pure strategy will be referred as desired attacker's
strategy (DAS) through the rest of this section.

In this section the term feasible defender's strategy will be used in
a meaning of a strategy inducing DAS.\@ The name comes from a feasible
solutions of an LP\ldots TODO.

Overview of the method if presented in
Figure~\ref{fig:mixed-method-overview}.  The method consists of the
following steps modifying defender strategy considered:
\begin{enumerate}
\item Initialize defender's strategy
\item Seek for attacker's strategy yielding better attacker's payoff
  against current defender's strategy, if such strategy exists call if
  BAS (better attacker strategy).\label{item:bas}
\item If BAS was found, then strategy feasibility pass and go to
  previous point, otherwise\footnote{It means that requested
    attacker's strategy is the best response to current defender}
  continue to next point.
\item Perform strategy adjustment that increases defender's payoff
  and go to~\ref{item:bas}.\label{item:di}
\item Return the best defender's strategy across all feasible
  strategies found
\end{enumerate}

The process of defender's payoff improvement (\ref{item:di}) is
repeated until stop conditions are met: either iteration-to-iteration
payoff increase is small enough or iteration number limit is reached. 

Strategy initialization is done by choosing the move sequence
maximizing attacker's payoff against DAS.\@
If BAS is found then break --- there is no feasible defender's strategy.


\begin{figure}
  \centering
  \input{mixed-strategy-flowchart}
  \caption{Overview of procedure for finding defender's mixed strategy
    iducing requested attacker's strategy. Procedures marked with red
    mutate current defender's strategy. Blue labels next to nodes
    are names of processes used in text.}%
  \label{fig:mixed-method-overview}
\end{figure}


The method mutates initially created defender's strategy to improve
defender's results. A single defender strategy is modified during the
whole method run. Any modifications to he defender's strategy are done
to the same, continuously mutated strategy.

The strategy mutated by this method is represented by a tree like
structure depicted in Figure~\ref{fig:mixed-tree}.
Technically the tree stores a behavioral strategy --- probabilities of
playing moves for in each state. Please note that there is bijection
between mixed and behavioral strategies in games with perfect
recall~\cite{XXX}.

\begin{figure}
  \input{mixed-strategy-tree}
  \caption{Mixed strategy tree. Edges are labeled with pair (move,
    probability). }%
  \label{fig:mixed-tree}
\end{figure}

\subsection{Strategy tree details}%
\label{sec:strategy-tree}

Each node of tree in Figure~\ref{fig:mixed-tree} is labeled with a
state projection visible to defender, i.e.\ defender's information
set. Root of the tree is labeled with game initial state.

Each edge going out of the node is labeled with a move allowed in the
given information set and a probability of playing the move in state
describing the node.

The edge is connected to a node labeled with a state that is achieved
after playing the move. As the tree is build only around defender's
moves and states, a resulting state can be ambiguous (it depends also
on attacker's move). In Figure~\ref{fig:mixed-tree} there are
three such situations. In the example states pointed by green edges
can be reached after playing against some attacker's strategy
$\pi_a^1$ while playing against different attackers may lead to other
states.

The tree does not contain all possible states. In the
resulting strategy probabilities of playing moves in states included
in the tree are equal to probabilities in tree edges. In case of
states not included in the tree uniform distribution over all possible
moves.

Any node representing non-terminal state contains at least one
outgoing move although not all possible moves must be included.
There can be also moves that are present in the tree, but have
assigned $0$ probability e.g.\ move $m6$ in
Figure~\ref{fig:mixed-tree}. 



\subsection{Strategy refinement procedure}%
\label{sec:refinement-procedure}

Both Feasibility pass and Positive pass use similar procedure to
adjust the defender's strategy In this section first we describe
an outline common for both passes and then we discuss details that are
different in each. Each pass defines its own move \emph{assessment function}
(returning a real number)
which is specific to its goal, e.g feasibility pass prefers moves
in which DAS has higher payoff than BAS. The function is then used in
Section~\ref{sec:adjustment} to guide probability adjustment
direction. 

Refinement pass starts from root node of strategy tree described in
Section~\ref{sec:strategy-tree}. 
\begin{enumerate}
\item With some probability descend to successor game state for each
  move being currently in mixed strategy choosing successor state
  against current attacker (BAS in Feasibility pass or DAS in Positive
  pass). Recursively apply this procedure to those nodes. 
\item With some probability add not yet present move to the tree.
  Add the whole single path to leaf after this move according to
  heuristic specific to particular pass type.\footnote{Not adding
    all moves to the tree at the beginning is a heuristic that can
    conserve some amount of memory.}
\item Calculate assessment of each move. Adjust mixed strategy
  probability values across moves present in tree. Adjustment method
  is described in Section~\ref{sec:adjustment}.
\end{enumerate}

In current implementation choice of path to add is done with UCT
heuristic instead of full game search. 

\subsubsection{Feasibility pass}%
\label{sec:feasibility-pass}
This pass uses payoffs for current strategy both against DAS and BAS.\@

\emph{Move assessment} to adjustment is done to make the strategy feasible:
reduce the difference attacker's payoff when playing DAS minus
attacker's payoff when playing BAS.\@ The exact value is calculated as
follows:
\begin{equation}
\left(\mathbb{E}U_a^{DAS}(s\oplus m) - \mathbb{E}U_a^{BAS}(s\oplus m)\right) + \left(\mathbb{E}U_a^{DAS}(s) - \mathbb{E}U_a^{BAS}(s)\right),
\label{eq:in-tree-assesment}
\end{equation}
where $U_a$ is attacker's utility when playing the strategy in upper
index $s$ is a current state and $s\oplus m$ is a state after playing
move $m$, $\mathbb{E}$ denotes expected value. 

Descending in the tree can result in two situations:
\begin{enumerate}
\item playing the move against both DAS and BAS leads to the same
  defender's information set (state) or
\item playing against BAS yields different information set than
  playing against DAS, e.g. $s6$ and $s7$ in Figure~\ref{fig:mixed-tree}.
\end{enumerate}

The first case is easier: we can apply the same procedure for the child node
directly.

In the second case we descend to adjustment of node that
came from playing against BAS.\@ Note that changing strategies in this
subtree does not influence playoff against DAS.\@ Therefore in this
subtree we choose assessment function to difference between 
attacker's payoff in current node and attacker's payoff after playing
move, i.e. we tend to minimize BAS payoff. The exact formula is
\begin{equation}
  U_a^{BAS}(s) - U_a^{BAS}(s\oplus m),
  \label{eq:out-of-tree-assesment}
\end{equation}
where meaning of symbols is like in~(\ref{eq:in-tree-assesment}).

\subsubsection{Positive pass}%
\label{sec:positive-pass}

Positive pass is performed after the full feasibility pass, i.e. no
attacker strategy exists that has better attacker's payoff than BAS.
The goal of the pass is to improve defender payoff. 

During strategy adjustment \emph{move assessment} is done by calculating
the difference
\begin{equation}
  \mathbb{E}(U_d(s\oplus m)) -\mathbb{E}(U_d(s)),
  \label{eq:positive-pass-adjustment}
\end{equation}
 where $\mathbb{E}(U_d)$ is
expected defender payoff in given node, $s$ is the current node and
$i\oplus m$ is a state after playing move $m$ against DAS. 

In case of tree expansion the expanded path is chosen so that it
maximizes defender's payoff. 

\subsection{Adjustment procedure with inhibitors}%
\label{sec:adjustment}

\textbf{This procedure is considered obsolete and is no longer used!!
  See Section~\ref{sec:adj-momentum} for current implementation.}

The most important part of the defender strategy search is adjustment
of probabilities in strategy nodes.

Each pass defines a method for assessing moves that go out of the
current node. Based on this assessment we divide moves into three
groups:
\begin{itemize}
\item positive, where assessment value is positive
\item neutral,
\item negative.
\end{itemize}

Each strategy tree node in addition to probabilities vector contains a
vector of nonnegative values of length equal to number of moves.
The vector values accumulate values about how often given move's
probability is \emph{reduced} during the training. Initially values in
the vector are $0$.

The procedure of updating of probabilities (and aforementioned
vectors) is presented in Algorithm~\ref{alg:adjustment}.
First, in lines~\ref{alg:adj:toas}---\ref{alg:adj:toae}, we check if it is possible to decrease probabilities negatively
assessed moves and increase positive ones. If it is not possible
(either sum of probabilities to decrease is $0$ or there is no moves
that can be increased we use neutral ones as fallback ones.
Then we move amount of probability mass proportional to $inh$
coefficients (exact value computed in line~\ref{alg:adj:coeff}) from
from negative (or neutral) moves to positive (or neutral) moves.
Finally we update $inh$ coefficients for all moves which probabilities
were decreased. 


\begin{algorithm}
  \SetAlgoLined
  \KwData{$prob\in {[0,1]}^M$ probabilities vector, $inh\in
    {(R^+\cup\{0\})}^M$ inhibitors vector, $as\in
    \mathbb{R}^M$ assessments vector. All vectors contain values for
    $i$-th move at $i$-th position. $pos,neg,neu\subseteq[M]$ indices
    of positive, negative and neutral moves respectively }

  \uIf{$|pos| > 0$\label{alg:adj:toas}}{
    $inc \gets pos$\;
    \lIf{$\sum_{i\in neg}prob_i > 0$}{$dec \gets neg$}
    \lElseIf{$\sum_{i\in neu}prob_i > 0 $}{$dec \gets neu$}
  }
  \uElseIf{$|neu| > 0$}{
    $inc \gets neu$\;
    \lIf{$\sum_{i\in neg}prob_i >0$}{$dec \gets neg$\label{alg:adj:toae}}
  }

  $coeff(i) \gets min\{1, inh_i/(\sum_{x \in inh} x)*M \}$\label{alg:adj:coeff}\;

  \If{$dec \neq nil \wedge inc \neq nil$}{
    $amount \gets 0$\;
    \For{$i \in dec$}{
      $change \gets min\{prob_i, rate/|dec|*0.5*coeff(i)\}$\;
      $prob_i \gets prob_i - change$\;
      $amount \gets change + amount$\;
    }

    $norm \gets \sum_{i \in inc} 1-coeff(i)$\;
    \For{$i \in inc$}{
      $prob_i \gets prob_i + amount * (1-coeff(i))/norm $\;
    }

    \For{$i \in dec$}{
      $inh_i \gets inh_i+rate$\;
    }
  }
  \caption{Node adjustment algorithm}
  \label{alg:adjustment}
\end{algorithm}

\subsection{Adjustment procedure with momentum}\label{sec:adj-momentum}

This method stores two variables within each node in strategy tree:
\begin{itemize}
\item a vector called \emph{momentum}. The vector length is equal to number of moves from the
node in strategy tree (and therefore equal to probabilities vector
length). 
\item a normalization coefficient $w$ for the above vector, initially
  $0$\footnote{Note that in algorithm we newer use the coefficient
    before it is increased, so we can assume that it is $\geq 0$ when
    performing division by $w$}.
\end{itemize}

The two above values are updated every time the node is adjusted and
the current value of momentum is used to adjust probabilities in
strategy. The procedure is described in
Algorithm~\ref{alg:momentum-adjustment}.
The algorithm uses node assessments values as defined in
Section~\ref{sec:refinement-procedure} (equations
(\ref{eq:in-tree-assesment}), (\ref{eq:out-of-tree-assesment}), (\ref{eq:positive-pass-adjustment})) and reads and mutates
probability and momentum values in current node.
The idea of the method is to accumulate in momentum vector preferred
update directions across all previous iterations. Normalization
coefficient $w$ accumulates $L_1$ norm of all updates. This guarantees
that norm of momentum divided by $w$ does not exceed 1 and it
decreases when subsequent iterations prefer adjustment in opposite
direst ions. After accumulating current preferences the algorithm
updates values in probabilities vector by current normalized
momentum values. This step may yield a vector which does not sum to
$1$ and therefore is not valid probabilities vector. The last step is
normalization of the vector so it is valid again.

\begin{algorithm}
  \SetAlgoLined

  \KwData{$prob\in {[0,1]}^M$ probabilities vector,
    $mom\in {(R^+\cup\{0\})}^M$ momentum vector, $w$ -- momentum
    normalization factor, $as\in \mathbb{R}^M$ assessments vector. All
    vectors contain values for $i$-th move at $i$-th position}

  $mom \gets mom + as$\;
  $w \gets w + L_1(as)$\;

  $prob \gets max\{prob+mom/w, 0\}$\tcp{independent max at each
    position}

  $prob \gets normalizeOrEqual{prob}$\tcp{Normalize vector values so
    their sum is 1 or as a fallback in case when all positions are 0 assign equal
    probability at each position}
  
  \caption{Node adjustment with momentum}%
  \label{alg:momentum-adjustment}
\end{algorithm}


\section{TODO}
\label{sec:todo}

Choose exact formulas for adjustment procedures so that they guarantee
convergence to the optimal strategy. 

\end{document}



%%%Local Variables:
%%% ispell-local-dictionary: "en_US"
%%%TeX-master: t
%%%End:
