BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Memento EPFL// BEGIN:VEVENT SUMMARY:Seminar by Prof. Selva Nadarajah\, University of Illinois at Chica go DTSTART:20180709T150000 DTEND:20180709T163000 DTSTAMP:20260919T215333Z UID:20ecac7220cc6b0faeca8e4285899161530e8c6308983c44c1a709fd CATEGORIES:Conferences - Seminars DESCRIPTION:Prof. Selva Nadarajah\, University of Illinois at Chicago\n"Re visiting approximate linear programming using a saddle point approach"\n\n \nAbstract:\nApproximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) for intractable Markov deci sion processes (MDPs) arising in applications. VFAs from ALPs have desirab le theoretical properties\, define an operating policy\, and provide a low er bound on the optimal policy cost\, which can be used to assess the subo ptimality of heuristic policies. However\, solving ALPs near-optimally rem ains challenging\, for example\, in applications where the MDP includes co st functions or transition dynamics that are nonlinear or when rich basis functions are required to obtain a good VFA. We address this tension betwe en ALP theory and solvability by proposing a convex saddle-point reformula tion of an ALP that includes as primal and dual variables\, respectively\, a vector of basis function weights and a constraint violation density fun ction over the state-action space. To solve this reformulation\, we develo p a proximal stochastic mirror descent (PSMD) method. We establish that PS MD returns a near-optimal ALP solution and a lower bound on the optimal po licy cost in a finite number of iterations with high probability. We compa re PSMD with the commonly used constraint sampling approach to solve ALPs and benchmark heuristics on inventory control and energy storage applicati ons\, where using row generation is not a viable option. We find that PSMD provides reliable and high-quality lower bounds that are tighter than low er bounds based on a perfect information relaxation\, while using constrai nt sampling to solve ALPs may not provide a valid lower bound. PSMD polici es outperform benchmark heuristics and are comparable or better than the o nes obtained using constraint sampling. Our ALP reformulation and solution approach broadens the applicability of approximate linear programming.\n   LOCATION:ODY 4 03 https://plan.epfl.ch/?room==ODY%204%2003 STATUS:CONFIRMED END:VEVENT END:VCALENDAR