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.

Input: Consider Input: 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.

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

Input: Consider Input: We present a probabilistic generative model for inferring a description of coordinated, recursively structured group activities at multiple levels of temporal granularity based on observations of individuals' trajectories. The model accommodates: (1) hierarchically structured groups, (2) activities that are temporally and compositionally recursive, (3) component roles assigning different subactivity dynamics to subgroups of participants, and (4) a nonparametric Gaussian Process model of trajectories. We present an MCMC sampling framework for performing joint inference over recursive activity descriptions and assignment of trajectories to groups, integrating out continuous parameters. We demonstrate the model's expressive power in several simulated and complex real-world scenarios from the VIRAT and UCLA Aerial Event video data sets.

Output: Bayesian Inference of Recursive Sequences of Group Activities from Tracks

Input: Consider Input: We introduce a globally-convergent algorithm for optimizing the tree-reweighted (TRW) variational objective over the marginal polytope. The algorithm is based on the conditional gradient method (Frank-Wolfe) and moves pseudomarginals within the marginal polytope through repeated maximum a posteriori (MAP) calls. This modular structure enables us to leverage black-box MAP solvers (both exact and approximate) for variational inference, and obtains more accurate results than tree-reweighted algorithms that optimize over the local consistency relaxation. Theoretically, we bound the sub-optimality for the proposed algorithm despite the TRW objective having unbounded gradients at the boundary of the marginal polytope. Empirically, we demonstrate the increased quality of results found by tightening the relaxation over the marginal polytope as well as the spanning tree polytope on synthetic and real-world instances.
Output: Barrier Frank-Wolfe for Marginal Inference