Advances in Sample-Based Prophet Inequalities and Optimization

The field of optimization and online learning is moving towards developing more efficient and robust algorithms that can handle limited information and uncertainty. Recent research has focused on improving the sample complexity of online contention resolution schemes, which has led to nearly optimal results for matroid constraints. Additionally, there has been progress in understanding the convergence properties of gradient-based optimization methods, including the development of generalized Polyak-Łojasiewicz Inequality-like conditions. Another area of interest is the development of novel algorithms for solving partially observable Markov decision processes (POMDPs) without numerical optimization. Noteworthy papers include: Nearly Tight Sample Complexity for Matroid Online Contention Resolution, which presents a nearly optimal sample-based OCRS for matroid constraints. Partially Observable Reference Policy Programming, which proposes a novel anytime online approximate POMDP solver with theoretical guarantees and empirical evaluations. Some remarks on gradient dominance and LQR policy optimization, which describes an input to state stability analysis of gradient descent and its applications to policy iteration for the continuous-time LQR problem.

Sources

Nearly Tight Sample Complexity for Matroid Online Contention Resolution

Some remarks on gradient dominance and LQR policy optimization

Partially Observable Reference Policy Programming: Solving POMDPs Sans Numerical Optimisation

Online Block Packing

Built with on top of