Research map / Learning theory and algorithms / Combinatorial and search optimization
Beyond Worst-case: A Probabilistic Analysis of Affine Policies in Dynamic Optimization
Omar El Housni, Vineet Goyal
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use affine policy instead of optimal adjustable policy | Affine policy · Uniform and Gaussian distributions | optimality gap: at most 4% | Mixed |
| use affine policy instead of MIP adjustable policy for m=30 (uniform) | Affine policy · Uniform, m=30 | running time (s): 761.21 -> 1.29 | Improved |
| use affine policy instead of MIP adjustable policy for m=20 (folded normal) | Affine policy · Folded Normal, m=20 | running time (s): 217.08 -> 0.39 | Improved |
| increase m to 50 | Adjustable policy MIP · Uniform and Folded Normal | solvability | Hurt |
| increase m to 50 | Affine policy · Uniform | running time (s): 1.29 -> 14.92 | Mixed |
| compare empirical ratio to theoretical bound | Affine policy · Uniform | approximation ratio: 2 -> 1.04 | Improved |
Closest papers by meaning
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.86)
- Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form (ICLR 2025 · similarity 0.86)
- Revisiting Subgradient Dominance in Robust MDPs: Counterexamples, Hardness, and Sufficient Conditions (NeurIPS 2026 · similarity 0.85)
- Distributionally Robust Performative Optimization (NeurIPS 2025 · similarity 0.85)
- Policy Optimization for Robust Average Reward MDPs (NeurIPS 2024 · similarity 0.85)
- Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
