Category: Reviews
-
Inverse Reinforcement Learning
A reinforcement learning problem is composed of a set of states, a set of actions, a state-action dependent transition function $p(sā | s, a)$, and a state- (or state-action-) dependent reward function $R(s)$. The objective of the agent in such a problem is to find a policy $\pi(s)$, determining the actions that it should take in any given state in order to optimize the expected future reward
-
Fitting Finite Automata
Finite state machines (finite automata) provide a simple model of computation: the machine starts from some initial state, observes a series of inputs, which cause it to transition to different states depending on the input and the current state, and then outputs a value, dependent on its final state. As a well-studied model of simple computations, it is not surprising that finite state machines are one of the earliest and best-studied computational inverse problems. They also provide one of the cleanest sample complexity results. Learning large (many state) state machines is not feasible for passive learners, which attempt to fit bulk-collected data: such learners require a number of data samples that is exponential in the size of the machine. Active learners, on the other hand, which can request information about specific points, are able to learn large state machines, with the number of samples growing quadratically with the number of states in the machine.
-
The sample complexity of computational inverse problems: introduction
The goal of a computational inverse problem is to describe the behavior of an observed system in terms of a computational problem that the system is solving. In other words, we assume that our observations about a system can be captured by some computational objective, and aim to describe the system in terms of that computation. This requires that we develop methods to fit specific features of computational models based on observations of how a system behaves. Motivations for this approach include imitation learning, adaptation, understanding economic behavior and animal behavior, machine learning interpretability, and functional or physiological modeling of biological systems.