Timezone: »

 
Poster
Safe Learning in Tree-Form Sequential Decision Making: Handling Hard and Soft Constraints
Martino Bernasconi · Federico Cacciamani · Matteo Castiglioni · Alberto Marchesi · Nicola Gatti · Francesco Trovò

Thu Jul 21 03:00 PM -- 05:00 PM (PDT) @ Hall E #1222
in Poster Session 3 »

We study decision making problems in which an agent sequentially interacts with a stochastic environment defined by means of a tree structure. The agent repeatedly faces the environment over time, and, after each round, it perceives a utility and a cost, which are both stochastic. The goal of the agent is to learn an optimal strategy in an online fashion, while, at the same time, keeping costs below a given safety threshold. Our model naturally fits many real-world scenarios, such as, e.g., opponent exploitation in games and web link selection. We study the hard-threshold problem of achieving sublinear regret while guaranteeing that the threshold constraint is satisfied at every iteration with high probability. First, we show that, in general, any algorithm with such a guarantee incurs in a linear regret. This motivates the introduction of a relaxed problem, namely the soft-threshold problem, in which we only require that the cumulative violation of the threshold constraint grows sublinearly, and, thus, we can provide an algorithm with sublinear regret. Next, we show how, in the hard-threshold problem, a sublinear regret algorithm can be designed under the additional assumption that there exists a known strategy strictly satisfying the threshold constraint. We also show that our regret bounds are tight. Finally, we cast the opponent exploitation problem to our model, and we experimentally evaluate our algorithms on a standard testbed of games.

Keywords: T: Game Theory · T: Online Learning and Bandits

Author Information

Martino Bernasconi (Politecnico di Milano)
Federico Cacciamani (Politecnico di Milano)
Matteo Castiglioni (Politecnico di Milano)
Alberto Marchesi (Politecnico di Milano)
Nicola Gatti (Politecnico di Milano)
Francesco Trovò (Politecnico di Milano)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors