{"id":6910,"date":"2025-10-06T15:55:26","date_gmt":"2025-10-06T13:55:26","guid":{"rendered":"https:\/\/samovar.telecom-sudparis.eu\/?p=6910"},"modified":"2025-10-10T10:13:55","modified_gmt":"2025-10-10T08:13:55","slug":"seminaire-ness-robust-deterministic-policies-for-mdps-under-budgeted-uncertainty-presente-par-dr-fei-wu-univeriste-de-louvain-en-belgique-le-10-10-a-11h-salle-4a205-palaiseau","status":"publish","type":"post","link":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/2025\/10\/06\/seminaire-ness-robust-deterministic-policies-for-mdps-under-budgeted-uncertainty-presente-par-dr-fei-wu-univeriste-de-louvain-en-belgique-le-10-10-a-11h-salle-4a205-palaiseau\/","title":{"rendered":"S\u00e9minaire Ness: Robust Deterministic Policies for MDPs under Budgeted Uncertainty, pr\u00e9sent\u00e9 par Dr. Fei WU, Universite de Louvain en Belgique, le 10\/10 \u00e0 11h, salle 4A205 \u00e0 Palaiseau"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

When:<\/strong> Vendredi 10 octobre 2025, 11h00<\/p>\n\n

Where<\/strong>: Salle 4A205, \u00e0 Telecom SudParis, Palaiseau, et lien Teams: Fei Wu Seminar | R\u00e9union-Joindre | Microsoft Teams<\/a><\/span><\/span><\/span><\/span><\/p>\n\n

Title:<\/strong> Robust Deterministic Policies for MDPs under Budgeted Uncertainty<\/p>\n\n


Abstract<\/strong>
We study the computation of robust deterministic policies for Markov Decision Processes (MDPs)
in the Lightning Does Not Strike Twice (LDST) model of Mannor, Mebel, and Xu. In this model,
designed to provide robustness in the face of uncertain input data while not being overly conservative,
transition probabilities and rewards are uncertain and the uncertainty set is constrained by a budget
that limits the number of states whose parameters can deviate from their nominal values. Mannor
et al. showed that optimal randomized policies for MDPs in the LDST regime can be efficiently
computed when only the rewards are affected by uncertainty. In contrast to these findings, we
observe that the computation of optimal deterministic policies is NP-hard even when only a single
terminal reward may deviate from its nominal value and the MDP consists of 2 time periods. For
this hard special case, we then derive a constant-factor approximation algorithm by combining two
relaxations based on the Knapsack Cover and Generalized Assignment problem, respectively. For
the general problem with possibly large number of deviations and a longer time horizon, we derive
strong inapproximability results for computing robust deterministic policies as well as \u03a3p
2-hardness, indicating that the general problem does not even admit a compact mixed integer programming
formulation.
Joint work with Jannik Matuschke and Erik Demeulemeester.<\/p>\n\n

Biography:<\/strong>
I received my Ph.D. in Operations Management from KU Leuven, where my work focused on
optimization under adversarial robustness. My research interests include combinatorial optimization,
algorithm design and analysis, and robust optimization, with applications to logistics and production.
I was invited to the Hausdorff Institute for Mathematics (University of Bonn) for a discrete
optimization program, where I presented preliminary results on robust MDPs.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

When: Vendredi 10 octobre 2025, 11h00 Where: Salle 4A205, \u00e0 Telecom SudParis, Palaiseau, et lien Teams: Fei Wu Seminar | R\u00e9union-Joindre | Microsoft Teams Title: Robust Deterministic Policies for MDPs under Budgeted Uncertainty AbstractWe study the computation of robust deterministic policies for Markov Decision Processes (MDPs)in the Lightning Does Not Strike Twice (LDST) model of […]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ocean_post_layout":"","ocean_both_sidebars_style":"","ocean_both_sidebars_content_width":0,"ocean_both_sidebars_sidebars_width":0,"ocean_sidebar":"","ocean_second_sidebar":"","ocean_disable_margins":"enable","ocean_add_body_class":"","ocean_shortcode_before_top_bar":"","ocean_shortcode_after_top_bar":"","ocean_shortcode_before_header":"","ocean_shortcode_after_header":"","ocean_has_shortcode":"","ocean_shortcode_after_title":"","ocean_shortcode_before_footer_widgets":"","ocean_shortcode_after_footer_widgets":"","ocean_shortcode_before_footer_bottom":"","ocean_shortcode_after_footer_bottom":"","ocean_display_top_bar":"default","ocean_display_header":"default","ocean_header_style":"","ocean_center_header_left_menu":"","ocean_custom_header_template":"","ocean_custom_logo":0,"ocean_custom_retina_logo":0,"ocean_custom_logo_max_width":0,"ocean_custom_logo_tablet_max_width":0,"ocean_custom_logo_mobile_max_width":0,"ocean_custom_logo_max_height":0,"ocean_custom_logo_tablet_max_height":0,"ocean_custom_logo_mobile_max_height":0,"ocean_header_custom_menu":"","ocean_menu_typo_font_family":"","ocean_menu_typo_font_subset":"","ocean_menu_typo_font_size":0,"ocean_menu_typo_font_size_tablet":0,"ocean_menu_typo_font_size_mobile":0,"ocean_menu_typo_font_size_unit":"px","ocean_menu_typo_font_weight":"","ocean_menu_typo_font_weight_tablet":"","ocean_menu_typo_font_weight_mobile":"","ocean_menu_typo_transform":"","ocean_menu_typo_transform_tablet":"","ocean_menu_typo_transform_mobile":"","ocean_menu_typo_line_height":0,"ocean_menu_typo_line_height_tablet":0,"ocean_menu_typo_line_height_mobile":0,"ocean_menu_typo_line_height_unit":"","ocean_menu_typo_spacing":0,"ocean_menu_typo_spacing_tablet":0,"ocean_menu_typo_spacing_mobile":0,"ocean_menu_typo_spacing_unit":"","ocean_menu_link_color":"","ocean_menu_link_color_hover":"","ocean_menu_link_color_active":"","ocean_menu_link_background":"","ocean_menu_link_hover_background":"","ocean_menu_link_active_background":"","ocean_menu_social_links_bg":"","ocean_menu_social_hover_links_bg":"","ocean_menu_social_links_color":"","ocean_menu_social_hover_links_color":"","ocean_disable_title":"default","ocean_disable_heading":"default","ocean_post_title":"","ocean_post_subheading":"","ocean_post_title_style":"","ocean_post_title_background_color":"","ocean_post_title_background":0,"ocean_post_title_bg_image_position":"","ocean_post_title_bg_image_attachment":"","ocean_post_title_bg_image_repeat":"","ocean_post_title_bg_image_size":"","ocean_post_title_height":0,"ocean_post_title_bg_overlay":0.5,"ocean_post_title_bg_overlay_color":"","ocean_disable_breadcrumbs":"default","ocean_breadcrumbs_color":"","ocean_breadcrumbs_separator_color":"","ocean_breadcrumbs_links_color":"","ocean_breadcrumbs_links_hover_color":"","ocean_display_footer_widgets":"default","ocean_display_footer_bottom":"default","ocean_custom_footer_template":"","ocean_post_oembed":"","ocean_post_self_hosted_media":"","ocean_post_video_embed":"","ocean_link_format":"","ocean_link_format_target":"self","ocean_quote_format":"","ocean_quote_format_link":"post","ocean_gallery_link_images":"on","ocean_gallery_id":[],"footnotes":""},"categories":[286,402,7],"tags":[],"class_list":["post-6910","post","type-post","status-publish","format-standard","hentry","category-fractualites-ennews-fr","category-seminaires-ness-2013-fr","category-uncategorized-fr","entry"],"_links":{"self":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/6910","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/comments?post=6910"}],"version-history":[{"count":12,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/6910\/revisions"}],"predecessor-version":[{"id":6922,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/6910\/revisions\/6922"}],"wp:attachment":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/media?parent=6910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/categories?post=6910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/tags?post=6910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}