Summary of Provably Efficient Infinite-horizon Average-reward Reinforcement Learning with Linear Function Approximation, by Woojin Chae et al.
Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
by Woojin Chae, Dabeen Lee
First submitted to arxiv on: 16 Sep 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary A computationally efficient algorithm for learning infinite-horizon average-reward linear Markov decision processes (MDPs) and linear mixture MDPs under the Bellman optimality condition is proposed. The algorithm achieves a regret upper bound of (d{3/2}(v)) over T time steps for linear MDPs, where (v^) is the span of the optimal bias function v^* and d is the dimension of the feature mapping. For linear mixture MDPs, a regret bound of (d(v^*)) is attained. Novel techniques are applied to control the covering number of the value function class and the span of optimistic estimators of the value function. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary A new algorithm helps computers learn from experience and make good decisions in situations with many possible choices. It’s designed for a specific type of problem, where the goal is to find the best way to act over time. The algorithm is efficient and can handle large problems. It also has interesting techniques that could be used in other areas. |
