  Motivated by concerns about making online decisions that incur undue amount
of risk at each time step, in this paper, we formulate the probably
anytime-safe stochastic combinatorial semi-bandits problem. In this problem,
the agent is given the option to select a subset of size at most $K$ from a set
of $L$ ground items. Each item is associated to a certain mean reward as well
as a variance that represents its risk. To mitigate the risk that the agent
incurs, we require that with probability at least $1-\delta$, over the entire
horizon of time $T$, each of the choices that the agent makes should contain
items whose sum of variances does not exceed a certain variance budget. We call
this probably anytime-safe constraint. Under this constraint, we design and
analyze an algorithm {\sc PASCombUCB} that minimizes the regret over the
horizon of time $T$. By developing accompanying information-theoretic lower
bounds, we show that under both the problem-dependent and problem-independent
paradigms, {\sc PASCombUCB} is almost asymptotically optimal. Experiments are
conducted to corroborate our theoretical findings. Our problem setup, the
proposed {\sc PASCombUCB} algorithm, and novel analyses are applicable to
domains such as recommendation systems and transportation in which an agent is
allowed to choose multiple items at a single time step and wishes to control
the risk over the whole time horizon.
