Seminar Details
2015-09-22 (11.00) : Two talks on mathematical programming
At Euler building (A002)
Organized by Mathematical Engineering
Speakers :
Bruno Scherrer (Université de Lorraine and Aarhus University)
,
and
Thomas Dueholm Hansen (Université de Lorraine and Aarhus University)
Abstract :
The talk by Bruno Scherrer is entitled "On the use of Non-stationary policies for infinite-horizon Markov Decision Processes", with the following abstract:
I shall consider infinite-horizon $\gamma$discounted Markov Decision Processes, for which it is known that there exists a stationary optimal policy. I will focus on the situation where the problem is so large that only an approximate form of dynamic programming can be implemented. Approximate versions of Value and Policy Iteration, that make an error $\epsilon$ at each iteration, are known to have an asymptotic performance guarantee of $2\gamma\epsilon/(1-\gamma)^2$. After arguing that this bound is tight, I will describe modifications of these algorithms generating non-stationary policies, that allow to improve the performance guarantee by a factor $(1-\gamma)$, which is particularly significant in the typical situation where $\gamma$ is close to 1. A surprising consequence of this result is that the problem of ''computing an approximately optimal non-stationary policy'' is much simpler than that of ''computing an approximately optimal stationary policy''.
Thomas D Hansen will talk about "An improved version of the Random-Facet pivoting rule for the simplex algorithm"
The Random-Facet pivoting rule of Kalai and of Matousek, Sharir, and Welzl is an elegant, randomized pivoting rule for the simplex algorithm, the classical combinatorial algorithm for solving linear programs. The expected running time of the simplex algorithm when using this rule is subexponential in the combinatorial size--the number of variables and inequalities--of the linear program. This is currently the best known combinatorial bound for solving general linear programs. Other polynomial time algorithms are known, but their running time depends also on the number of bits in the representation of the linear program.
We present a slightly improved version of the Random-Facet pivoting rule, thus obtaining the fastest known combinatorial algorithm for solving linear programs, the first improvement in over 20 years. Our results apply not only to linear programs, but also to more general, abstract LP-type problems. In particular we also obtain the fastest known algorithm for solving two-player turn-based stochastic games.
Joint work with Uri Zwick. End of the seminar around noon.