5 papers
On-line Learning in Tree MDPs by Treating Policies as Bandit Arms
Anvay Shah, Ramsundar Anandanarayanan, Sharayu Moharir +1
A Tree Markov Decision Problem (T-MDP) is a finite-horizon MDP with a starting state , in which every state is reachable from through exactly one state-action trajec…
Using Common Random Numbers for Simulation-based Planning with Rollouts
Sandarbh Yadav, Frederic J Maliakkal, Harshad Khadilkar +1
Simulation-based planning with rollouts is a widely-deployed technique for decision making in stochastic environments. The primary instrument of simulation-based planning is a samp…
Efficient Computation of Blackwell Optimal Policies using Rational Functions
Dibyangshu Mukherjee, Shivaram Kalyanakrishnan
Markov Decision Problems (MDPs) provide a foundational framework for modelling sequential decision-making across diverse domains, guided by optimality criteria such as discounted a…
Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor
Dibyangshu Mukherjee, Shivaram Kalyanakrishnan
Howard's Policy Iteration (HPI) is a classic algorithm for solving Markov Decision Problems (MDPs). HPI uses a "greedy" switching rule to update from any non-optimal policy to a do…
A View of the Certainty-Equivalence Method for PAC RL as an Application of the Trajectory Tree Method
Shivaram Kalyanakrishnan, Sheel Shah, Santhosh Kumar Guguloth
Reinforcement learning (RL) enables an agent interacting with an unknown MDP to optimise its behaviour by observing transitions sampled from . A natural entity that emerges…