ChronosPerseus: Randomized Point-based Value Iteration with Importance Sampling for POSMDPs
This addresses a gap in reinforcement learning for domains requiring continuous time modeling, though it appears to be an incremental extension of existing POMDP methods.
The paper tackles the problem of reinforcement learning in environments with both noisy observations and continuous random time delays by proposing ChronosPerseus, an algorithm for partially observable semi-Markov decision processes (POSMDPs) that extends existing point-based value iteration with importance sampling. The method reduces solver complexity and handles both episodic and non-episodic problems, as demonstrated in bus and maintenance examples.
In reinforcement learning, agents have successfully used environments modeled with Markov decision processes (MDPs). However, in many problem domains, an agent may suffer from noisy observations or random times until its subsequent decision. While partially observable Markov decision processes (POMDPs) have dealt with noisy observations, they have yet to deal with the unknown time aspect. Of course, one could discretize the time, but this leads to Bellman's Curse of Dimensionality. To incorporate continuous sojourn-time distributions in the agent's decision making, we propose that partially observable semi-Markov decision processes (POSMDPs) can be helpful in this regard. We extend \citet{Spaan2005a} randomized point-based value iteration (PBVI) \textsc{Perseus} algorithm used for POMDP to POSMDP by incorporating continuous sojourn time distributions and using importance sampling to reduce the solver complexity. We call this new PBVI algorithm with importance sampling for POSMDPs -- \textsc{ChronosPerseus}. This further allows for compressed complex POMDPs requiring temporal state information by moving this information into state sojourn time of a POMSDP. The second insight is that keeping a set of sampled times and weighting it by its likelihood can be used in a single backup; this helps further reduce the algorithm complexity. The solver also works on episodic and non-episodic problems. We conclude our paper with two examples, an episodic bus problem and a non-episodic maintenance problem.