  In recent years, content recommendation systems in large websites (or
\emph{content providers}) capture an increased focus. While the type of content
varies, e.g.\ movies, articles, music, advertisements, etc., the high level
problem remains the same. Based on knowledge obtained so far on the user,
recommend the most desired content. In this paper we present a method to handle
the well known user-cold-start problem in recommendation systems. In this
scenario, a recommendation system encounters a new user and the objective is to
present items as relevant as possible with the hope of keeping the user's
session as long as possible. We formulate an optimization problem aimed to
maximize the length of this initial session, as this is believed to be the key
to have the user come back and perhaps register to the system. In particular,
our model captures the fact that a single round with low quality recommendation
is likely to terminate the session. In such a case, we do not proceed to the
next round as the user leaves the system, possibly never to seen again. We
denote this phenomenon a \emph{One-Shot Session}. Our optimization problem is
formulated as an MDP where the action space is of a combinatorial nature as we
recommend in each round, multiple items. This huge action space presents a
computational challenge making the straightforward solution intractable. We
analyze the structure of the MDP to prove monotone and submodular like
properties that allow a computationally efficient solution via a method denoted
by \emph{Greedy Value Iteration} (G-VI).
