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.
--------
Question: Optimal probabilistic approach in reinforcement learning is computationally infeasible. Its simplification consisting in neglecting difference between true environment and its model estimated using limited number of observations causes exploration vs exploitation problem. Uncertainty can be expressed in terms of a probability distribution over the space of environment models, and this uncertainty can be propagated to the action-value function via Bellman iterations, which are computationally insufficiently efficient though. We consider possibility of directly measuring uncertainty of the action-value function, and analyze sufficiency of this facilitated approach.

Answer: Direct Uncertainty Estimation in Reinforcement Learning


Question: We present a method for solving implicit (factored) Markov decision processes (MDPs) with very large state spaces. We intro­ duce a property of state space partitions which we call f-homogeneity. Intuitively, an f-homogeneous partition groups together states that behave approximately the same under all or some subset of policies. Borrow­ ing from recent work on model minimization in computer-aided software verification, we present an algorithm that takes a factored representation of an MDP and an 0 � f � I and computes a factored f-homogeneous par­ tition of the state space. This partition defines a family of related MOPs-those MOP's with state space equal to the blocks of the partition, and transition probabilities "appro:X:imately" like those of any (original MDP) state in the source block. To formally study such families of MDPs, we introduce the new notion of a "bounded parameter MDP" (BMDP), which is a fam­ ily of (traditional) MOPs defined by speci­ fying upper and lower bounds on the transi­ tion probabilities and rewards. We describe algorithms that operate on BMDPs to find policies that are approximately optimal with respect to the original MDP. In combination, our method for reducing a large implicit MDP to a possibly much smaller BMDP using an f-homogeneous par­ tition, and our methods for selecting actions in BMDP's constitute a new approach for an­ alyzing large implicit MOP's. Among its ad­ vantages, this new approach provides insight into existing algorithms to solving implicit MDPs, provides useful connections to work in automata theory and model minimization, and suggests methods, which involve vary­ ing f, to trade time and space (specifically in terms of the size of the corresponding state space) for solution quality.

Answer: Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes


Question: Matrix-parametrized models, including multiclass logistic regression and sparse coding, are used in machine learning (ML) applications ranging from computer vision to computational biology. When these models are applied to large-scale ML problems starting at millions of samples and tens of thousands of classes, their parameter matrix can grow at an unexpected rate, resulting in high parameter synchronization costs that greatly slow down distributed learning. To address this issue, we propose a Sufficient Factor Broadcasting (SFB) computation model for efficient distributed learning of a large family of matrix-parameterized models, which share the following property: the parameter update computed on each data sample is a rank-1 matrix, i.e. the outer product of two “sufficient factors” (SFs). By broadcasting the SFs among worker machines and reconstructing the update matrices locally at each worker, SFB improves communication efficiency — communication costs are linear in the parameter matrix’s dimensions, rather than quadratic — without affecting computational correctness. We present a theoretical convergence analysis of SFB, and empirically corroborate its efficiency on four different matrix-parametrized ML models.

Answer:
Distributed Machine Learning via Sufficient Factor Broadcasting