A Learning Procedure for Sampling Semantically Different Valid Expressions

E-print/Working paper (2013)

Généralisation min max pour l'apprentissage par renforcement batch et déterministe : schémas de relaxation

in Septièmes Journées Francophones de Planification, Décision et Apprentissage pour la conduite de systèmes (JFPDA 2012) (2012, May)

On s’intéresse au problème de généralisation min max dans le cadre de l’apprentissage par renforcement batch et déterministe. Le problème a été originellement introduit par Fonteneau et al. (2011). Dans ... [more ▼]

On s’intéresse au problème de généralisation min max dans le cadre de l’apprentissage par renforcement batch et déterministe. Le problème a été originellement introduit par Fonteneau et al. (2011). Dans un premier temps, on montre que le problème est NP-dur. Dans le cas où l’horizon d’optimisation vaut 2, on développe deux schémas de relaxation. Le premier schéma fonctionne en éliminant des contraintes de telle sorte qu’on obtienne un problème soluble en temps polynomial. Le deuxième schéma est une relaxation Lagrangienne conduisant à un problème conique-quadratique. On montre théoriquement et empiriquement que ces deux schémas permettent d’obtenir de meilleurs résultats que ceux proposés par Fonteneau et al. (2011). [less ▲]

Relaxation schemes for min max generalization in deterministic batch mode reinforcement learning

Conference (2011, December)

We study the min max optimization problem introduced in [Fonteneau, 2011] for computing policies for batch mode reinforcement learning in a deterministic setting. This problem is NP-hard. We focus on the ... [more ▼]

We study the min max optimization problem introduced in [Fonteneau, 2011] for computing policies for batch mode reinforcement learning in a deterministic setting. This problem is NP-hard. We focus on the two-stage case for which 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. Both relaxation schemes are shown to provide better results than those given in [Fonteneau, 2011]. [less ▲]

Online Sparse Bandit for Card Games

in Advance in Computer Games (2011)

Finding an approximation of a Nash equilibria in matrix games is an important topic that reaches beyond the strict application to matrix games. A bandit algorithm commonly used to approximate a Nash ... [more ▼]

Finding an approximation of a Nash equilibria in matrix games is an important topic that reaches beyond the strict application to matrix games. A bandit algorithm commonly used to approximate a Nash equilibrium is EXP3. However, the solution to many problems is often sparse, yet EXP3 inherently fails to exploit this property. To the knowledge of the authors, there exist only an offline truncation to tackle such issue. In this paper, we propose a variation of EXP3 to exploit the fact that solution is sparse by dynamically removing arms; the resulting algorithm empirically performs better than previous versions. We apply the resulting algorithm to a MCTS program for the Urban Rivals card game. [less ▲]

Sparse Two-Row Cuts and an Algorithm for the Separation Problem

Conference (2010, July)

We propose a systematic way to generate sparse cuts from multiple rows of the simplex tableau. We also discuss the question of separation for a multi-row model. To this end, we consideer the polar system ... [more ▼]

We propose a systematic way to generate sparse cuts from multiple rows of the simplex tableau. We also discuss the question of separation for a multi-row model. To this end, we consideer the polar system allowing to generate valid inequalities. In order to avoid generating the large number of constraints of the polar, we consider a reduced version of it that we dynamically extend. Checking the validity of an inequality is done geometrically. Computational results showing the efficiency of the algorithm are presented. This is a joint work with Laurent Poirrier. [less ▲]

An analysis of mixed integer linear sets based on lattice point free convex sets

in Mathematics of Operations Research (2010), 35(1), 233-256

The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the w th split closure. We show the w th split closure is a ... [more ▼]

The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the w th split closure. We show the w th split closure is a polyhedron. This generalizes a previous result showing this to be true when w = 1. We also consider the design of finite cutting plane proofs for the validity of an inequality. Given a measure of “size” of a maximal lattice free polyhedron, a natural question is how large a size s of a maximal lattice free polyhedron is required to design a finite cutting plane proof for the validity of an inequality. We characterize s based on the faces of the linear relaxation of the mixed integer linear set. [less ▲]

Split rank of two-row cuts

Conference (2009, December)

A simple relaxation consisting of two rows of a simplex tableau is a mixed-integer set with two equations, two free integer variables, and nonnegative continuous variables. Recently, Andersen et al. and ... [more ▼]

A simple relaxation consisting of two rows of a simplex tableau is a mixed-integer set with two equations, two free integer variables, and nonnegative continuous variables. Recently, Andersen et al. and Cornuéjols and Margot showed that the facet- defining inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. From an example given by Cook et al. it is known that one particular class of facet-defining triangle inequality does not have finite split rank. In this paper we show that all other facet-defining triangle and quadrilateral inequalities have finite split rank. [less ▲]

Split rank of triange and quadrilateral inequalities

Conference (2009, January)

A simple relaxation consisting of two rows of a simplex tableau is a mixed-integer set with two equations, two free integer variables, and nonnegative continuous variables. Recently, Andersen et al. and ... [more ▼]

A simple relaxation consisting of two rows of a simplex tableau is a mixed-integer set with two equations, two free integer variables, and nonnegative continuous variables. Recently, Andersen et al. and Cornuéjols and Margot showed that the facet- defining inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. From an example given by Cook, Kannan and Schrijver it is known that one particular class of facet-defining triangle inequality does not have finite split rank. In this talk we show that all other facet-defining triangle and quadrilateral inequalities have finite split rank. [less ▲]

Certificates of linear mixed integer infeasibility

in Operations Research Letters (2008), 36(6), 734-738

We derive a certificate of integral infeasibility for linear systems with equations and inequalities by generating algebraically an outer description of a lattice point free polyhedron that contains the ... [more ▼]

We derive a certificate of integral infeasibility for linear systems with equations and inequalities by generating algebraically an outer description of a lattice point free polyhedron that contains the given integer infeasible system. The extension to the mixed integer setting is also derived. [less ▲]

Polyhedral properties for the intersection of two knapsacks

in Mathematical Programming (2008), 113(1), 15-37

We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out ... [more ▼]

We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out that the sign patterns of the weight vectors are responsible for the types of combinatorial valid inequalities appearing in the description of the convex hull of the intersection. In partic- ular, we introduce the notion of an incomplete set inequality which is based on a combinatorial principle for the intersection of two knapsacks. We outline schemes to compute nontrivial bounds for the strength of such inequalities w.r.t. the intersection of the convex hulls of the initial knapsacks. An extension of the inequalities to the mixed case is also given. This opens up the possibility to use the inequalities in an arbitrary simplex tableau. [less ▲]