A unified analysis of value-function-based reinforcement- learning algorithms.

Reinforcement learning is the problem of generating optimal behavior in a sequential decision-making environment given the opportunity of interacting with it. Many algorithms for solving reinforcement-learning problems work by computing improved estimates of the optimal value function. We extend prior analyses of reinforcement-learning algorithms and present a powerful new theorem that can provide a unified analysis of such value-function-based reinforcement-learning algorithms. The usefulness of the theorem lies in how it allows the convergence of a complex asynchronous reinforcement-learning algorithm to be proved by verifying that a simpler synchronous algorithm converges. We illustrate the application of the theorem by analyzing the convergence of Q-learning, model-based reinforcement learning, Q-learning with multistate updates, Q-learning for Markov games, and risk-sensitive reinforcement learning.

Disambiguation by community membership.

To interpret utterances in conversations, listeners must often make reference to the common ground they share with speakers. For example, when faced with an utterance such as "That game was a disaster," listeners must decide whether they share common assumptions about what outcome would be disastrous. In our experiments, we examine how common ground, as encoded in community membership, is used to constrain judgments about the interpretations of ambiguous utterances. In Experiment 1, subjects were sensitive to community membership when they were asked to evaluate the interpretations at a leisurely pace. Experiment 2 replicated this result with greater time pressure. Experiment 3 demonstrated that judgments based on assessments of community membership were equivalent to those based on certain knowledge, except when the judgements were challenged. The results suggest that models of memory retrieval during language comprehension should make mention of access to common ground.