Detailed Instructions: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Problem:We consider the problem of efficient exploration in finite horizon MDPs. We show that an optimistic modification to modelbased value iteration, can achieve a regret bound O( HSAT+HSA+H T )whereH is the time horizon, S the number of states, A the number of actions and T the time elapsed. This result improves over the best previous known bound O(HS AT ) achieved by the UCRL2 algorithm Jaksch et al. (2010a). The key significance of our new results is that when T HSA and SA H , it leads to a regret of O( HSAT ) that matches the established lower bounds of ( HSAT ) up to a logarithmic factor. Our analysis contain two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in S), and we use "exploration bonuses" based on Bernstein's inequality, together with using a recursive -Bellman-typeLaw of Total Variance (to improve scaling in H).
Solution:
Minimax Regret Bounds for Reinforcement Learning