## Contributed Session Fri.3.H 0107

#### Friday, 15:15 - 16:45 h, Room: H 0107

**Cluster 16: Nonlinear programming** [...]

### Decomposition and relaxation methods

**Chair: Oleg Burdakov**

**Friday, 15:15 - 15:40 h, Room: H 0107, Talk 1**

**Quentin Louveaux**

Relaxation schemes for the evaluation of a policy in batch mode reinforcement learning

**Coauthors: Bernard Boigelot, Damien Ernst, RaphaĆ«l Fonteneau**

**Abstract:**

We study the min max optimization problem introduced for computing policies for batch mode reinforcement learning in a deterministic setting. First, we show that this problem is NP-hard. In the two-stage case, we provide two relaxation schemes. The first relaxation scheme works by dropping some constraints in order to obtain a problem that is solvable in polynomial time. The second relaxation scheme, based on a Lagrangian relaxation where all constraints are dualized, leads to a conic quadratic programming problem. We also theoretically prove and empirically illustrate that both relaxation schemes provide better results than those given previously for the same problem.

**Friday, 15:45 - 16:10 h, Room: H 0107, Talk 2**

**Oleg Burdakov**

An approach to solving decomposable optimization problems with coupling constraints

**Coauthors: John C. Dunn, Mike Kalish**

**Abstract:**

We consider a problem of minimizing *f*_{1}(x)+f_{2}(y) over

*x ∈ X ⊆ R*^{n} and *y ∈ Y ⊆ R*^{m} subject to

a number of extra coupling constraints of the form *g*_{1}(x)g_{2}(y) ≥ 0.

Due to these constraints, the problem may have a large number

of local minima.

For any feasible combination of signs of *g*_{1}(x) and *g*_{2}(y),

the coupled problem is decomposable, and the resulting two problems

are assumed to be easily solved.

An approach to solving the coupled problem is presented. We apply

it to solving coupled monotonic regression problems arising in

experimental psychology.