BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Sebastian Junges (UC Berkeley)
DTSTART:20201028T140000Z
DTEND:20201028T150000Z
DTSTAMP:20260423T052548Z
UID:OWLS/10
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/OWLS/10/">Fi
 nding Memoryless Policies in Partially Observable MDPs is ETR-complete (YR
 -OWLS)</a>\nby Sebastian Junges (UC Berkeley) as part of Online Worldwide 
 Seminar on Logic and Semantics (OWLS)\n\n\nAbstract\nPartially observable 
 Markov Decision Processes (POMDPs) are a prime model in sequential decisio
 n making. They are heavily studied in operations research\, artificial int
 elligence and verification\, to name a few. For POMDPs\, a good policy rea
 ches the target with probability at some threshold\, and makes its decisio
 ns solely based on the previously made observations. Deciding whether a go
 od policy exists is undecidable. One of the methods to solve instances of 
 this reachability problem is to restrict the memory that the strategy may 
 use. This approach is commonly taking\, e.g.\, in reinforcement learning f
 or POMDPs. In the first part of the talk\, we consider memoryless strategi
 es in POMDPs. and show that this problem is as hard as the feasibility pro
 blem in parametric Markov Chain (pMC) analysis.\n\nIn the second part of t
 he talk\, we consider this feasibility problem for pMCs. Roughly\, a pMC i
 s a Markov chain with symbolic transitions. The feasibility problem asks: 
 Do values for the symbols exist such that in the induced parameter-free Ma
 rkov chain\, a target state is reached with probability at least a half. W
 e discuss the complexity landscape for variants of this decision problem. 
 In particular\, we establish that feasibility in pMCs is complete for the 
 complexity class "existential theory of the reals” (ETR). Another exampl
 e of an ETR-complete problem is deciding whether a multivariate polynomial
  has a real root. Together with the results of the first half of the talk\
 , this establishes that deciding whether there exists a good memoryless po
 licy in a POMDP is ETR-complete.\n
LOCATION:https://researchseminars.org/talk/OWLS/10/
END:VEVENT
END:VCALENDAR