nips nips2008 nips2008-131 knowledge-graph by maker-knowledge-mining

131 nips-2008-MDPs with Non-Deterministic Policies

Source: pdf

Author: Mahdi M. Fard, Joelle Pineau

Abstract: Markov Decision Processes (MDPs) have been extensively studied and used in the context of planning and decision-making, and many methods exist to ﬁnd the optimal policy for problems modelled as MDPs. Although ﬁnding the optimal policy is sufﬁcient in many domains, in certain applications such as decision support systems where the policy is executed by a human (rather than a machine), ﬁnding all possible near-optimal policies might be useful as it provides more ﬂexibility to the person executing the policy. In this paper we introduce the new concept of non-deterministic MDP policies, and address the question of ﬁnding near-optimal non-deterministic policies. We propose two solutions to this problem, one based on a Mixed Integer Program and the other one based on a search algorithm. We include experimental results obtained from applying this framework to optimize treatment choices in the context of a medical decision support system. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 ca Abstract Markov Decision Processes (MDPs) have been extensively studied and used in the context of planning and decision-making, and many methods exist to ﬁnd the optimal policy for problems modelled as MDPs. [sent-5, score-0.617]

2 We propose two solutions to this problem, one based on a Mixed Integer Program and the other one based on a search algorithm. [sent-8, score-0.114]

3 We include experimental results obtained from applying this framework to optimize treatment choices in the context of a medical decision support system. [sent-9, score-0.267]

4 In particular, MDPs have emerged as a useful framework for optimizing action choices in the context of medical decision support systems [1, 2, 3, 4]. [sent-11, score-0.356]

5 This policy is usually a deterministic or stochastic function [5]. [sent-13, score-0.59]

6 But policies of these types face a substantial barrier in terms of gaining acceptance from the medical community, because they are highly prescriptive and leave little room for the doctor’s input. [sent-14, score-0.42]

7 In such cases, where the actions are executed by a human, it may be preferable to instead provide several (near-)equivalently good action choices, so that the agent can pick among those according to his or her own heuristics and preferences. [sent-15, score-0.392]

8 1 To address this problem, this paper introduces the notion of a non-deterministic policy 2 , which is a function mapping each state to a set of actions, from which the acting agent can choose. [sent-16, score-0.698]

9 We aim for this set to be as large as possible, to provide freedom of choice to the agent, while excluding any action that is signiﬁcantly worse than optimal. [sent-17, score-0.161]

10 Unlike stochastic policies, here we make no assumptions regarding which action will be executed. [sent-18, score-0.134]

11 While working with non-deterministic policies, it is important to ensure that by adding some freedom of choice to the policy, the worst-case expected return of the policy is still close enough to the optimal value. [sent-20, score-0.68]

12 We deﬁne a set of optimization problems to ﬁnd such a policy and provide two algorithms to solve this problem. [sent-22, score-0.569]

13 The main contributions of this work are to introduce the concept of non-deterministic policies, provide solution methods to compute such policies, and demonstrate the usefulness of this new model for providing acceptable solutions in medical decision support systems. [sent-27, score-0.243]

14 2 Non-Deterministic Policies In this section, we formulate the concept of non-deterministic policies and provide some deﬁnitions that are used throughout the paper. [sent-29, score-0.338]

15 An MDP M = (S, A, T, R) is deﬁned by a set of states S, a function A(s) mapping each state to a set of action, a transition function T (s, a, s0 ) deﬁned as: T (s, a, s0 ) = p(st+1 = s0 |st = s, at = a), 8s, s0 2 S, a 2 A(s), (1) and a reward function R(s, a) : S ⇥ A ! [sent-30, score-0.209]

16 Throughout the paper we assume ﬁnite state, ﬁnite action, discounted reward MDPs, with the discount factor denoted by . [sent-32, score-0.127]

17 A deterministic policy is a function from states to actions. [sent-33, score-0.618]

18 The P optimal deterministic policy is the policy that maximizes the expected discounted sum of rewards ( t t rt ) if the agent acts according to that policy. [sent-34, score-1.353]

19 The value of a state-action pair (s, a) according to the optimal deterministic policy on an MDP M = (S, A, T, R) satisﬁes the Bellman optimality equation [6]: ◆ X✓ Q⇤ (s, a) = R(s, a) + T (s, a, s0 ) 0max 0 Q⇤ (s0 , a0 ) . [sent-35, score-0.701]

20 M A non-deterministic policy is a function that maps each state s to a non-empty set of actions denoted by ⇧(s) ✓ A(s). [sent-37, score-0.67]

21 The agent can choose to do any action a 2 ⇧(s) whenever the MDP is in state s. [sent-38, score-0.246]

22 Here we will provide a worst-case analysis, presuming that the agent may choose the worst action in each state. [sent-39, score-0.218]

23 We deﬁne the value of state ⇧ s according to a non-deterministic policy ⇧ denoted by VM (s) to be mina2⇧(s) Q⇧ (s, a). [sent-41, score-0.626]

24 M (4) A non-deterministic policy ⇧ is said to be augmented with state-action pair (s, a) denoted by ⇧0 = ⇧ + (s, a), if it satisﬁes: ⇢ ⇧(s0 ), s0 6= s ⇧0 (s0 ) = (5) 0 ⇧(s ) [ {a}, s0 = s If a policy ⇧ can be achieved by a number of augmentations from a policy ⇧0 , we say that ⇧ includes ⇧0 . [sent-44, score-1.774]

25 P size of a policy ⇧, denoted by |⇧|, is the sum of the cardinality of the action sets The in ⇧: |⇧| = s |⇧(s)|. [sent-45, score-0.699]

26 A non-deterministic policy ⇧ is said to be non-augmentable according to a constraint if and only if ⇧ satisﬁes , and for any state-action pair (s, a), ⇧ + (s, a) does not satisfy . [sent-46, score-0.68]

27 In this paper we will be working with constraints that have this particular property: if a policy ⇧ does not satisfy , any policy that includes ⇧ does not satisfy . [sent-47, score-1.131]

28 A non-deterministic policy ⇧ on an MDP M is said to be ✏-optimal (✏ 2 [0, 1]) if we have:3 ⇧ ⇤ VM (s) (1 ✏)VM (s), 8s 2 S. [sent-49, score-0.566]

29 (6) This can be thought of as a constraint on the space of non-deterministic policies which makes sure that the worst-case expected return is within some range of the optimal value. [sent-50, score-0.492]

30 A conservative ✏-optimal non-deterministic policy ⇧ on an MDP M is a policy that is nonaugmentable according to this constraint: X ⇤ ⇤ R(s, a) + (T (s, a, s0 )(1 ✏)VM (s0 )) (1 ✏)VM (s), 8a 2 ⇧(s). [sent-52, score-1.281]

31 (7) s0 This constraint indicates that we only add those actions to the policy whose reward plus (1 ✏) of the future optimal return is within the sub-optimal margin. [sent-53, score-0.863]

32 This ensures that non-deterministic policy is ✏-optimal by using the inequality: X ⇤ Q⇧ (s, a) R(s, a) + (T (s, a, s0 )(1 ✏)VM (s0 )) , (8) M s0 instead of solving Eqn 3 and using the inequality constraint in Eqn 6. [sent-54, score-0.588]

33 Applying Eqn 7 guarantees that the non-deterministic policy is ✏-optimal while it may still be augmentable according to Eqn 6, hence the name conservative. [sent-55, score-0.614]

34 It can also be shown that the conservative policy is unique. [sent-56, score-0.644]

35 A non-augmentable ✏-optimal non-deterministic policy ⇧ on an MDP M is a policy that is not augmentable according to the constraint in Eqn 6. [sent-57, score-1.202]

36 It is easy to show that any non-augmentable ✏-optimal policy includes the conservative policy. [sent-58, score-0.677]

37 In this paper we will focus on a search problem in the space of nonaugmentable ✏-optimal policies, trying to maximize some criteria. [sent-60, score-0.208]

38 Speciﬁcally, we will be trying to ﬁnd non-deterministic policies that give the acting agent more options while staying within an acceptable sub-optimal margin. [sent-61, score-0.548]

39 The labels on the arcs show action names and the corresponding rewards are shown in the parentheses. [sent-66, score-0.163]

40 The conservative ✏-optimal non-deterministic policy of this MDP is shown in Fig 3. [sent-70, score-0.644]

41 Although both policies in Fig 4 are ✏-optimal, the union of these is not ✏-optimal. [sent-72, score-0.315]

42 This is due to the fact that adding an option to one of the states removes the possibility of adding options to other states, which illustrates why local changes are not always appropriate when searching in the space of ✏-optimal policies. [sent-73, score-0.151]

43 Notice that the last two problems can be deﬁned both in the space of all ✏-optimal policies or only the non-augmentable ones. [sent-78, score-0.315]

44 • Maximizing the size of the policy: According to this criterion, we seek non-augmentable ✏-optimal policies that have the biggest overall size. [sent-79, score-0.349]

45 This provides more options to the agent while still keeping the ✏-optimal guarantees. [sent-80, score-0.119]

46 Notice that the solution to this optimization problem is nonaugmentable according to the ✏-optimal constraint, because it maximizes the overall size of the policy. [sent-82, score-0.166]

47 • Maximizing the margin: We aim to maximize margin of a non-deterministic policy ⇧: ✓ ◆ (⇧) = min min (Q(s, a) Q(s, a0 )) . [sent-83, score-0.589]

48 (9) M 0 s a2⇧(s),a 2⇧(s) / This optimization criterion is useful when one wants to ﬁnd a clear separation between the good and bad actions in each state. [sent-84, score-0.17]

49 • Minimizing the uncertainly: If we learn the models from data we will have some uncertainly about the optimal action in each state. [sent-85, score-0.251]

50 We aim to minimize the uncertainly of a non-deterministic policy ⇧: ✓ ◆ (⇧) = max max p (Q(s, a) < Q(s, a0 )|D) . [sent-88, score-0.631]

51 We focus on this criterion as it seems most appropriate for medical decision support systems, where it is desirable for the acceptability of the system to ﬁnd policies that provide as much choice as possible for the acting agent. [sent-90, score-0.614]

52 We ﬁrst present a Mixed Integer Program formulation of the problem, and then present a search algorithm that uses the monotonic property of the ✏-optimal constraint. [sent-91, score-0.166]

53 While the MIP method is useful as a general formulation of the problem, the search algorithm has potential for further extensions with heuristics. [sent-92, score-0.146]

54 The second set of constraints ensures that at least one action is selected per state. [sent-102, score-0.16]

55 The third set ensures that for those state-action pairs that are chosen in any policy, the Bellman constraint holds, and otherwise, the constant Vmax makes the constraint trivial. [sent-103, score-0.132]

56 A general purpose MIP solver could end up searching in the space of all the possible non-deterministic policies, which would require exponential running time. [sent-109, score-0.115]

57 2 Search Algorithm We can make use of the monotonic property of the ✏-optimal policies to narrow down the search. [sent-111, score-0.395]

58 We make use of the fact that if a policy is not ✏-optimal, neither is any other policy that includes it, and thus we can cut the search tree at this point. [sent-114, score-1.249]

59 The following algorithm is a one-sided recursive depth-ﬁrst-search-like algorithm that searches in the space of plausible non-deterministic policies to maximize a function g(⇧). [sent-115, score-0.365]

60 This ordering can be chosen according to some heuristic along with a mechanism to cut down some parts of the search space. [sent-117, score-0.202]

61 V ⇤ is the optimal value function and the function V returns the value of the non-deterministic policy that can be calculated by minimizing Equation 3. [sent-118, score-0.585]

62 The asymptotic running time of the above algorithm is O((|S||A|)d (tm + tg )), where d is the maximum size of an ✏-optimal policy minus the size of the conservative policy, tm is the time to solve the original MDP and tg is the time to calculate the function g. [sent-120, score-0.896]

63 Although the worst-case running time is still exponential in the number of state-action pairs, the run-time is much less when the search space is sufﬁciently small. [sent-121, score-0.184]

64 Note that this algorithm searches in the space of all ✏-optimal policies rather than only the non-augmentable ones. [sent-124, score-0.339]

65 This search can be further improved by using heuristics to order the state-action pairs and prune the search. [sent-126, score-0.21]

66 One can also start the search from any other policy rather than the conservative policy. [sent-127, score-0.758]

67 One way to narrow down the search is to only add the action that has the maximum value for any state s: ✓ ◆ ⇧0 = ⇧ + s, arg max , (13) Q(s,a) This leads to a running time of O(|S|d (tm + tg )). [sent-129, score-0.442]

68 If the transition structure of the MDP contains no loop with non-zero probability (transition graph is directed acyclic, DAG), then this heuristic will produce the optimal result while cutting down the search time. [sent-132, score-0.243]

69 In other cases, one might do a partial evaluation of the augmented policy to approximate the value after adding the actions, possibly by doing a few backups rather than using the original Q values. [sent-133, score-0.58]

70 5 Empirical Evaluation To evaluate our proposed algorithms, we ﬁrst test the both the MIP and search formulations on MDPs created randomly, and then test the search algorithm on a real-world treatment design scenario. [sent-135, score-0.305]

71 The transitions are deterministic (chosen uniformly random) and the rewards are random values between 0 and 1, except for one of the states with reward 10 for one of the actions; was set to 0. [sent-137, score-0.209]

72 We see that the size of non-deterministic policy increases as the performance threshold is relaxed. [sent-141, score-0.536]

73 The labels on the edges are action indices, followed by the corresponding immediate rewards. [sent-172, score-0.134]

74 To compare the running time of the MIP solver and the search algorithm, we constructed random MDPs as described above with more state-action pairs. [sent-173, score-0.229]

75 The running time of the search algorithm has a bigger constant factor, but has a smaller exponent base which results in a faster asymptotic running time. [sent-179, score-0.281]

76 To study how stable non-deterministic policies are to potential noise in the models, we check to see how much the policy changes when Gaussian noise is added to the reward function. [sent-180, score-0.949]

77 Fig 6 Right shows the percentage of the total state-action pairs that were either added or removed from the resulting policy by adding noise to the reward model (we assume a constant ✏ = 0. [sent-181, score-0.706]

78 We see that the resulting non-deterministic policy changes somewhat, but not drastically, even with noise level of similar magnitude as the reward function. [sent-183, score-0.634]

79 Next, we implemented the full search algorithm on an MDP constructed for a medical decisionmaking task involving real patient data. [sent-184, score-0.273]

80 The data was collected as part of a large (4000+ patients) multi-step randomized clinical trial, designed to investigate the comparative effectiveness of different treatments provided sequentially for patients suffering from depression [9]. [sent-185, score-0.14]

81 A reward of 1 is given if the patient achieves remission (at any step) and a reward of 0 is given otherwise. [sent-192, score-0.295]

82 The transition and reward models were generated empirically from the data using a frequentist approach. [sent-193, score-0.153]

83 Table 1: Policy and running time of the full search algorithm on the medical problem ✏ = 0. [sent-194, score-0.289]

84 Although this problem is not tractable with the MIP formulation (304 state-action pairs), a full search in the space of ✏-optimal policies is still possible. [sent-203, score-0.429]

85 However, as the underlying transition graph is a DAG, we could use the heuristic discussed in the previous section (Eqn 13) to get the same policies even faster. [sent-206, score-0.395]

86 In practice, a doctor may use the full table as a guideline, using smaller values of ✏ when s/he wants to rely more on the decision support system, and larger values when relying more on his/her own assessments. [sent-208, score-0.172]

87 6 Discussion This paper introduces a framework for computing non-deterministic policies for MDPs. [sent-209, score-0.315]

88 We believe this framework can be especially useful in the context of decision support systems to provide more choice and ﬂexibility to the acting agent. [sent-210, score-0.167]

89 This should improve acceptability of decision support systems in ﬁelds where the policy is used to guide (or advise) a human expert, notably for the optimization of medical treatments. [sent-211, score-0.818]

90 We present two algorithms that can solve such an optimization problem: a MIP formulation that can be solved by any general MIP solver, and a search algorithm that uses the monotonic property of the studied constraints to cut down on the running time. [sent-214, score-0.325]

91 The search algorithm is particularly useful when we have good heuristics to further prune the search space. [sent-215, score-0.328]

92 Future work will consider different optimizing criteria, such as those outlined in Section 3, which may be more appropriate for some domains with very large action sets. [sent-216, score-0.172]

93 A limitation of our current approach is that the algorithms presented so far are limited to relatively small domains, and scale well only for domains with special properties, such as a DAG structure in the transition model or good heuristics for pruning the search. [sent-217, score-0.133]

94 Finally, it is worth noting that non-deterministic policies can also be useful in cases where the MDP transition and reward models are imperfectly speciﬁed or learned from data, though we have not explored this case in detail yet. [sent-220, score-0.5]

95 In such a setting, the difference between the optimal and a near optimal policy may not be computed accurately. [sent-221, score-0.634]

96 Thus, it is useful to ﬁnd all actions that are close to optimal so that the real optimal action is not missed. [sent-222, score-0.341]

97 An interesting question here is whether we can ﬁnd the smallest non-deterministic policy that will include the optimal policy with some probability 1 . [sent-223, score-1.121]

98 This is similar to the framework in [7], and could be useful in cases where there is not enough data to compare policies with good statistical signiﬁcance. [sent-224, score-0.347]

99 Planning treatment of ischemic heart disease with partially observable Markov decision processes. [sent-239, score-0.137]

100 Background and rationale for the sequenced treatment alternatives to relieve depression (STAR*D) study. [sent-288, score-0.125]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('policy', 0.536), ('policies', 0.315), ('mip', 0.293), ('mdp', 0.248), ('cit', 0.236), ('ct', 0.153), ('eqn', 0.144), ('qids', 0.135), ('action', 0.134), ('fig', 0.128), ('mdps', 0.124), ('search', 0.114), ('bup', 0.113), ('vm', 0.112), ('conservative', 0.108), ('medical', 0.105), ('reward', 0.098), ('ven', 0.09), ('vmax', 0.084), ('agent', 0.084), ('actions', 0.077), ('treatment', 0.077), ('running', 0.07), ('getoptimal', 0.068), ('nonaugmentable', 0.068), ('tg', 0.068), ('uncertainly', 0.068), ('vmin', 0.068), ('dag', 0.061), ('decision', 0.06), ('doctor', 0.059), ('acceptability', 0.059), ('transition', 0.055), ('patient', 0.054), ('bus', 0.054), ('deterministic', 0.054), ('monotonic', 0.052), ('constraint', 0.052), ('return', 0.051), ('acting', 0.05), ('optimal', 0.049), ('mixed', 0.049), ('depression', 0.048), ('tm', 0.046), ('augmentable', 0.045), ('augmentations', 0.045), ('remission', 0.045), ('rmin', 0.045), ('startindex', 0.045), ('solver', 0.045), ('adding', 0.044), ('heuristics', 0.04), ('integer', 0.04), ('ser', 0.039), ('rush', 0.039), ('program', 0.039), ('domains', 0.038), ('patients', 0.038), ('options', 0.035), ('staying', 0.034), ('montreal', 0.034), ('biggest', 0.034), ('rmax', 0.034), ('according', 0.033), ('optimization', 0.033), ('includes', 0.033), ('useful', 0.032), ('maximizes', 0.032), ('planning', 0.032), ('bellman', 0.03), ('acceptable', 0.03), ('mcgill', 0.03), ('said', 0.03), ('cut', 0.03), ('denoted', 0.029), ('rewards', 0.029), ('treatments', 0.029), ('pair', 0.029), ('states', 0.028), ('wants', 0.028), ('prune', 0.028), ('narrow', 0.028), ('pairs', 0.028), ('state', 0.028), ('bigger', 0.027), ('health', 0.027), ('aim', 0.027), ('maximize', 0.026), ('constraints', 0.026), ('sure', 0.025), ('reinforcement', 0.025), ('heuristic', 0.025), ('support', 0.025), ('clinical', 0.025), ('searches', 0.024), ('preferences', 0.024), ('executed', 0.024), ('concept', 0.023), ('notice', 0.022), ('markov', 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999928 131 nips-2008-MDPs with Non-Deterministic Policies

Author: Mahdi M. Fard, Joelle Pineau

2 0.34797654 195 nips-2008-Regularized Policy Iteration

Author: Amir M. Farahmand, Mohammad Ghavamzadeh, Shie Mannor, Csaba Szepesvári

Abstract: In this paper we consider approximate policy-iteration-based reinforcement learning algorithms. In order to implement a ﬂexible function approximation scheme we propose the use of non-parametric methods with regularization, providing a convenient way to control the complexity of the function approximator. We propose two novel regularized policy iteration algorithms by adding L2 -regularization to two widely-used policy evaluation methods: Bellman residual minimization (BRM) and least-squares temporal difference learning (LSTD). We derive efﬁcient implementation for our algorithms when the approximate value-functions belong to a reproducing kernel Hilbert space. We also provide ﬁnite-sample performance bounds for our algorithms and show that they are able to achieve optimal rates of convergence under the studied conditions. 1

3 0.32759708 181 nips-2008-Policy Search for Motor Primitives in Robotics

Author: Jens Kober, Jan R. Peters

Abstract: Many motor skills in humanoid robotics can be learned using parametrized motor primitives as done in imitation learning. However, most interesting motor learning problems are high-dimensional reinforcement learning problems often beyond the reach of current methods. In this paper, we extend previous work on policy learning from the immediate reward case to episodic reinforcement learning. We show that this results in a general, common framework also connected to policy gradient methods and yielding a novel algorithm for policy learning that is particularly well-suited for dynamic motor primitives. The resulting algorithm is an EM-inspired algorithm applicable to complex motor learning tasks. We compare this algorithm to several well-known parametrized policy search methods and show that it outperforms them. We apply it in the context of motor learning and show that it can learn a complex Ball-in-a-Cup task using a real Barrett WAMTM robot arm. 1

4 0.31933296 150 nips-2008-Near-optimal Regret Bounds for Reinforcement Learning

Author: Peter Auer, Thomas Jaksch, Ronald Ortner

Abstract: For undiscounted reinforcement learning in Markov decision processes (MDPs) we consider the total regret of a learning algorithm with respect to an optimal policy. In order to describe the transition structure of an MDP we propose a new parameter: An MDP has diameter D if for any pair of states s, s there is a policy which moves from s to s in at most D steps (on average). We present a rein√ ˜ forcement learning algorithm with total regret O(DS AT ) after T steps for any unknown MDP with S states, A actions per state, and diameter D. This bound holds with high probability. We also present a corresponding lower bound of √ Ω( DSAT ) on the total regret of any learning algorithm. 1

5 0.23851019 1 nips-2008-A Convergent $O(n)$ Temporal-difference Algorithm for Off-policy Learning with Linear Function Approximation

Author: Richard S. Sutton, Hamid R. Maei, Csaba Szepesvári

Abstract: We introduce the ﬁrst temporal-difference learning algorithm that is stable with linear function approximation and off-policy training, for any ﬁnite Markov decision process, behavior policy, and target policy, and whose complexity scales linearly in the number of parameters. We consider an i.i.d. policy-evaluation setting in which the data need not come from on-policy experience. The gradient temporal-difference (GTD) algorithm estimates the expected update vector of the TD(0) algorithm and performs stochastic gradient descent on its L2 norm. We prove that this algorithm is stable and convergent under the usual stochastic approximation conditions to the same least-squares solution as found by the LSTD, but without LSTD’s quadratic computational complexity. GTD is online and incremental, and does not involve multiplying by products of likelihood ratios as in importance-sampling methods. 1 Off-policy learning methods Off-policy methods have an important role to play in the larger ambitions of modern reinforcement learning. In general, updates to a statistic of a dynamical process are said to be “off-policy” if their distribution does not match the dynamics of the process, particularly if the mismatch is due to the way actions are chosen. The prototypical example in reinforcement learning is the learning of the value function for one policy, the target policy, using data obtained while following another policy, the behavior policy. For example, the popular Q-learning algorithm (Watkins 1989) is an offpolicy temporal-difference algorithm in which the target policy is greedy with respect to estimated action values, and the behavior policy is something more exploratory, such as a corresponding greedy policy. Off-policy methods are also critical to reinforcement-learning-based efforts to model human-level world knowledge and state representations as predictions of option outcomes (e.g., Sutton, Precup & Singh 1999; Sutton, Rafols & Koop 2006). Unfortunately, off-policy methods such as Q-learning are not sound when used with approximations that are linear in the learned parameters—the most popular form of function approximation in reinforcement learning. Counterexamples have been known for many years (e.g., Baird 1995) in which Q-learning’s parameters diverge to inﬁnity for any positive step size. This is a severe problem in so far as function approximation is widely viewed as necessary for large-scale applications of reinforcement learning. The need is so great that practitioners have often simply ignored the problem and continued to use Q-learning with linear function approximation anyway. Although no instances ∗ Csaba Szepesv´ ri is on leave from MTA SZTAKI. a 1 of absolute divergence in applications have been reported in the literature, the potential for instability is disturbing and probably belies real but less obvious problems. The stability problem is not speciﬁc to reinforcement learning. Classical dynamic programming methods such as value and policy iteration are also off-policy methods and also diverge on some problems when used with linear function approximation. Reinforcement learning methods are actually an improvement over conventional dynamic programming methods in that at least they can be used stably with linear function approximation in their on-policy form. The stability problem is also not due to the interaction of control and prediction, or to stochastic approximation effects; the simplest counterexamples are for deterministic, expected-value-style, synchronous policy evaluation (see Baird 1995; Sutton & Barto 1998). Prior to the current work, the possibility of instability could not be avoided whenever four individually desirable algorithmic features were combined: 1) off-policy updates, 2) temporal-difference learning, 3) linear function approximation, and 4) linear complexity in memory and per-time-step computation. If any one of these four is abandoned, then stable methods can be obtained relatively easily. But each feature brings value and practitioners are loath to give any of them up, as we discuss later in a penultimate related-work section. In this paper we present the ﬁrst algorithm to achieve all four desirable features and be stable and convergent for all ﬁnite Markov decision processes, all target and behavior policies, and all feature representations for the linear approximator. Moreover, our algorithm does not use importance sampling and can be expected to be much better conditioned and of lower variance than importance sampling methods. Our algorithm can be viewed as performing stochastic gradient-descent in a novel objective function whose optimum is the least-squares TD solution. Our algorithm is also incremental and suitable for online use just as are simple temporaldifference learning algorithms such as Q-learning and TD(λ) (Sutton 1988). Our algorithm can be broadly characterized as a gradient-descent version of TD(0), and accordingly we call it GTD(0). 2 Sub-sampling and i.i.d. formulations of temporal-difference learning In this section we formulate the off-policy policy-evaluation problem for one-step temporaldifference learning such that the data consists of independent, identically-distributed (i.i.d.) samples. We start by considering the standard reinforcement learning framework, in which a learning agent interacts with an environment consisting of a ﬁnite Markov decision process (MDP). At each of a sequence of discrete time steps, t = 1, 2, . . ., the environment is in a state st ∈ S, the agent chooses an action at ∈ A, and then the environment emits a reward rt ∈ R, and transitions to its next state st+1 ∈ S. The state and action sets are ﬁnite. State transitions are stochastic and dependent on the immediately preceding state and action. Rewards are stochastic and dependent on the preceding state and action, and on the next state. The agent process generating the actions is termed the behavior policy. To start, we assume a deterministic target policy π : S → A. The objective is to learn an approximation to its state-value function: ∞ V π (s) = Eπ γ t−1 rt |s1 = s , (1) t=1 where γ ∈ [0, 1) is the discount rate. The learning is to be done without knowledge of the process dynamics and from observations of a single continuous trajectory with no resets. In many problems of interest the state set is too large for it to be practical to approximate the value of each state individually. Here we consider linear function approximation, in which states are mapped to feature vectors with fewer components than the number of states. That is, for each state s ∈ S there is a corresponding feature vector φ(s) ∈ Rn , with n |S|. The approximation to the value function is then required to be linear in the feature vectors and a corresponding parameter vector θ ∈ Rn : V π (s) ≈ θ φ(s). (2) Further, we assume that the states st are not visible to the learning agent in any way other than through the feature vectors. Thus this function approximation formulation can include partialobservability formulations such as POMDPs as a special case. The environment and the behavior policy together generate a stream of states, actions and rewards, s1 , a1 , r1 , s2 , a2 , r2 , . . ., which we can break into causally related 4-tuples, (s1 , a1 , r1 , s1 ), 2 (s2 , a2 , r2 , s2 ), . . . , where st = st+1 . For some tuples, the action will match what the target policy would do in that state, and for others it will not. We can discard all of the latter as not relevant to the target policy. For the former, we can discard the action because it can be determined from the state via the target policy. With a slight abuse of notation, let sk denote the kth state in which an on-policy action was taken, and let rk and sk denote the associated reward and next state. The kth on-policy transition, denoted (sk , rk , sk ), is a triple consisting of the starting state of the transition, the reward on the transition, and the ending state of the transition. The corresponding data available to the learning algorithm is the triple (φ(sk ), rk , φ(sk )). The MDP under the behavior policy is assumed to be ergodic, so that it determines a stationary state-occupancy distribution µ(s) = limk→∞ P r{sk = s}. For any state s, the MDP and target policy together determine an N × N state-transition-probability matrix P , where pss = P r{sk = s |sk = s}, and an N × 1 expected-reward vector R, where Rs = E[rk |sk = s]. These two together completely characterize the statistics of on-policy transitions, and all the samples in the sequence of (φ(sk ), rk , φ(sk )) respect these statistics. The problem still has a Markov structure in that there are temporal dependencies between the sample transitions. In our analysis we ﬁrst consider a formulation without such dependencies, the i.i.d. case, and then prove that our results extend to the original case. In the i.i.d. formulation, the states sk are generated independently and identically distributed according to an arbitrary probability distribution µ. From each sk , a corresponding sk is generated according to the on-policy state-transition matrix, P , and a corresponding rk is generated according to an arbitrary bounded distribution with expected value Rsk . The ﬁnal i.i.d. data sequence, from which an approximate value function is to be learned, is then the sequence (φ(sk ), rk , φ(sk )), for k = 1, 2, . . . Further, because each sample is i.i.d., we can remove the indices and talk about a single tuple of random variables (φ, r, φ ) drawn from µ. It remains to deﬁne the objective of learning. The TD error for the linear setting is δ = r + γθ φ − θ φ. (3) Given this, we deﬁne the one-step linear TD solution as any value of θ at which 0 = E[δφ] = −Aθ + b, (4) where A = E φ(φ − γφ ) and b = E[rφ]. This is the parameter value to which the linear TD(0) algorithm (Sutton 1988) converges under on-policy training, as well as the value found by LSTD(0) (Bradtke & Barto 1996) under both on-policy and off-policy training. The TD solution is always a ﬁxed-point of the linear TD(0) algorithm, but under off-policy training it may not be stable; if θ does not exactly satisfy (4), then the TD(0) algorithm may cause it to move away in expected value and eventually diverge to inﬁnity. 3 The GTD(0) algorithm We next present the idea and gradient-descent derivation leading to the GTD(0) algorithm. As discussed above, the vector E[δφ] can be viewed as an error in the current solution θ. The vector should be zero, so its norm is a measure of how far we are away from the TD solution. A distinctive feature of our gradient-descent analysis of temporal-difference learning is that we use as our objective function the L2 norm of this vector: J(θ) = E[δφ] E[δφ] . (5) This objective function is quadratic and unimodal; it’s minimum value of 0 is achieved when E[δφ] = 0, which can always be achieved. The gradient of this objective function is θ J(θ) = 2( = 2E φ( θ E[δφ])E[δφ] θ δ) E[δφ] = −2E φ(φ − γφ ) E[δφ] . (6) This last equation is key to our analysis. We would like to take a stochastic gradient-descent approach, in which a small change is made on each sample in such a way that the expected update 3 is the direction opposite to the gradient. This is straightforward if the gradient can be written as a single expected value, but here we have a product of two expected values. One cannot sample both of them because the sample product will be biased by their correlation. However, one could store a long-term, quasi-stationary estimate of either of the expectations and then sample the other. The question is, which expectation should be estimated and stored, and which should be sampled? Both ways seem to lead to interesting learning algorithms. First let us consider the algorithm obtained by forming and storing a separate estimate of the ﬁrst expectation, that is, of the matrix A = E φ(φ − γφ ) . This matrix is straightforward to estimate from experience as a simple arithmetic average of all previously observed sample outer products φ(φ − γφ ) . Note that A is a stationary statistic in any ﬁxed-policy policy-evaluation problem; it does not depend on θ and would not need to be re-estimated if θ were to change. Let Ak be the estimate of A after observing the ﬁrst k samples, (φ1 , r1 , φ1 ), . . . , (φk , rk , φk ). Then this algorithm is deﬁned by k 1 Ak = φi (φi − γφi ) (7) k i=1 along with the gradient descent rule: θk+1 = θk + αk Ak δk φk , k ≥ 1, (8) where θ1 is arbitrary, δk = rk + γθk φk − θk φk , and αk > 0 is a series of step-size parameters, possibly decreasing over time. We call this algorithm A TD(0) because it is essentially conventional TD(0) preﬁxed by an estimate of the matrix A . Although we ﬁnd this algorithm interesting, we do not consider it further here because it requires O(n2 ) memory and computation per time step. The second path to a stochastic-approximation algorithm for estimating the gradient (6) is to form and store an estimate of the second expectation, the vector E[δφ], and to sample the ﬁrst expectation, E φ(φ − γφ ) . Let uk denote the estimate of E[δφ] after observing the ﬁrst k − 1 samples, with u1 = 0. The GTD(0) algorithm is deﬁned by uk+1 = uk + βk (δk φk − uk ) (9) and θk+1 = θk + αk (φk − γφk )φk uk , (10) where θ1 is arbitrary, δk is as in (3) using θk , and αk > 0 and βk > 0 are step-size parameters, possibly decreasing over time. Notice that if the product is formed right-to-left, then the entire computation is O(n) per time step. 4 Convergence The purpose of this section is to establish that GTD(0) converges with probability one to the TD solution in the i.i.d. problem formulation under standard assumptions. In particular, we have the following result: Theorem 4.1 (Convergence of GTD(0)). Consider the GTD(0) iteration (9,10) with step-size se∞ ∞ 2 quences αk and βk satisfying βk = ηαk , η > 0, αk , βk ∈ (0, 1], k=0 αk = ∞, k=0 αk < ∞. Further assume that (φk , rk , φk ) is an i.i.d. sequence with uniformly bounded second moments. Let A = E φk (φk − γφk ) and b = E[rk φk ] (note that A and b are well-deﬁned because the distribution of (φk , rk , φk ) does not depend on the sequence index k). Assume that A is non-singular. Then the parameter vector θk converges with probability one to the TD solution (4). Proof. We use the ordinary-differential-equation (ODE) approach (Borkar & Meyn 2000). First, we rewrite the algorithm’s two iterations as a single iteration in a combined parameter vector with √ 2n components ρk = (vk , θk ), where vk = uk / η, and a new reward-related vector with 2n components gk+1 = (rk φk , 0 ): √ ρk+1 = ρk + αk η (Gk+1 ρk + gk+1 ) , where Gk+1 = √ − ηI (φk − γφk )φk 4 φk (γφk − φk ) 0 . Let G = E[Gk ] and g = E[gk ]. Note that G and g are well-deﬁned as by the assumption the process {φk , rk , φk }k is i.i.d. In particular, √ − η I −A b G= , g= . 0 A 0 Further, note that (4) follows from Gρ + g = 0, (11) where ρ = (v , θ ). Now we apply Theorem 2.2 of Borkar & Meyn (2000). For this purpose we write ρk+1 = ρk + √ √ αk η(Gρk +g+(Gk+1 −G)ρk +(gk+1 −g)) = ρk +αk (h(ρk )+Mk+1 ), where αk = αk η, h(ρ) = g + Gρ and Mk+1 = (Gk+1 − G)ρk + gk+1 − g. Let Fk = σ(ρ1 , M1 , . . . , ρk−1 , Mk ). Theorem 2.2 requires the veriﬁcation of the following conditions: (i) The function h is Lipschitz and h∞ (ρ) = limr→∞ h(rρ)/r is well-deﬁned for every ρ ∈ R2n ; (ii-a) The sequence (Mk , Fk ) is a martingale difference sequence, and (ii-b) for some C0 > 0, E Mk+1 2 | Fk ≤ C0 (1 + ρk 2 ) holds for ∞ any initial parameter vector ρ1 ; (iii) The sequence αk satisﬁes 0 < αk ≤ 1, k=1 αk = ∞, ∞ 2 ˙ k=1 (αk ) < +∞; and (iv) The ODE ρ = h(ρ) has a globally asymptotically stable equilibrium. Clearly, h(ρ) is Lipschitz with coefﬁcient G and h∞ (ρ) = Gρ. By construction, (Mk , Fk ) satisﬁes E[Mk+1 |Fk ] = 0 and Mk ∈ Fk , i.e., it is a martingale difference sequence. Condition (ii-b) can be shown to hold by a simple application of the triangle inequality and the boundedness of the the second moments of (φk , rk , φk ). Condition (iii) is satisﬁed by our conditions on the step-size sequences αk , βk . Finally, the last condition (iv) will follow from the elementary theory of linear differential equations if we can show that the real parts of all the eigenvalues of G are negative. First, let us show that G is non-singular. Using the determinant rule for partitioned matrices1 we get det(G) = det(A A) = 0. This indicates that all the eigenvalues of G are non-zero. Now, let λ ∈ C, λ = 0 be an eigenvalue of G with corresponding normalized eigenvector x ∈ C2n ; 2 that is, x = x∗ x = 1, where x∗ is the complex conjugate of x. Hence x∗ Gx = λ. Let √ 2 x = (x1 , x2 ), where x1 , x2 ∈ Cn . Using the deﬁnition of G, λ = x∗ Gx = − η x1 + x∗ Ax2 − x∗ A x1 . Because A is real, A∗ = A , and it follows that (x∗ Ax2 )∗ = x∗ A x1 . Thus, 1 2 1 2 √ 2 Re(λ) = Re(x∗ Gx) = − η x1 ≤ 0. We are now done if we show that x1 cannot be zero. If x1 = 0, then from λ = x∗ Gx we get that λ = 0, which contradicts with λ = 0. The next result concerns the convergence of GTD(0) when (φk , rk , φk ) is obtained by the off-policy sub-sampling process described originally in Section 2. We make the following assumption: Assumption A1 The behavior policy πb (generator of the actions at ) selects all actions of the target policy π with positive probability in every state, and the target policy is deterministic. This assumption is needed to ensure that the sub-sampled process sk is well-deﬁned and that the obtained sample is of “high quality”. Under this assumption it holds that sk is again a Markov chain by the strong Markov property of Markov processes (as the times selected when actions correspond to those of the behavior policy form Markov times with respect to the ﬁltration deﬁned by the original process st ). The following theorem shows that the conclusion of the previous result continues to hold in this case: Theorem 4.2 (Convergence of GTD(0) with a sub-sampled process.). Assume A1. Let the parameters θk , uk be updated by (9,10). Further assume that (φk , rk , φk ) is such that E φk 2 |sk−1 , 2 E rk |sk−1 , E φk 2 |sk−1 are uniformly bounded. Assume that the Markov chain (sk ) is aperiodic and irreducible, so that limk→∞ P(sk = s |s0 = s) = µ(s ) exists and is unique. Let s be a state randomly drawn from µ, and let s be a state obtained by following π for one time step in the MDP from s. Further, let r(s, s ) be the reward incurred. Let A = E φ(s)(φ(s) − γφ(s )) and b = E[r(s, s )φ(s)]. Assume that A is non-singular. Then the parameter vector θk converges with probability one to the TD solution (4), provided that s1 ∼ µ. Proof. The proof of Theorem 4.1 goes through without any changes once we observe that G = E[Gk+1 |Fk ] and g = E[gk+1 | Fk ]. 1 R According to this rule, if A ∈ Rn×n , B ∈ Rn×m , C ∈ Rm×n , D ∈ Rm×m then for F = [A B; C D] ∈ , det(F ) = det(A) det(D − CA−1 B). (n+m)×(n+m) 5 The condition that (sk ) is aperiodic and irreducible guarantees the existence of the steady state distribution µ. Further, the aperiodicity and irreducibility of (sk ) follows from the same property of the original process (st ). For further discussion of these conditions cf. Section 6.3 of Bertsekas and Tsitsiklis (1996). With considerable more work the result can be extended to the case when s1 follows an arbitrary distribution. This requires an extension of Theorem 2.2 of Borkar and Meyn (2000) to processes of the form ρk+1 + ρk (h(ρk ) + Mk+1 + ek+1 ), where ek+1 is a fast decaying perturbation (see, e.g., the proof of Proposition 4.8 of Bertsekas and Tsitsiklis (1996)). 5 Extensions to action values, stochastic target policies, and other sample weightings The GTD algorithm extends immediately to the case of off-policy learning of action-value functions. For this assume that a behavior policy πb is followed that samples all actions in every state with positive probability. Let the target policy to be evaluated be π. In this case the basis functions are dependent on both the states and actions: φ : S × A → Rn . The learning equations are unchanged, except that φt and φt are redeﬁned as follows: φt = φ(st , at ), (12) φt = (13) π(st+1 , a)φ(st+1 , a). a (We use time indices t denoting physical time.) Here π(s, a) is the probability of selecting action a in state s under the target policy π. Let us call the resulting algorithm “one-step gradient-based Q-evaluation,” or GQE(0). Theorem 5.1 (Convergence of GQE(0)). Assume that st is a state sequence generated by following some stationary policy πb in a ﬁnite MDP. Let rt be the corresponding sequence of rewards and let φt , φt be given by the respective equations (12) and (13), and assume that E φt 2 |st−1 , 2 E rt |st−1 , E φt 2 |st−1 are uniformly bounded. Let the parameters θt , ut be updated by Equations (9) and (10). Assume that the Markov chain (st ) is aperiodic and irreducible, so that limt→∞ P(st = s |s0 = s) = µ(s ) exists and is unique. Let s be a state randomly drawn from µ, a be an action chosen by πb in s, let s be the next state obtained and let a = π(s ) be the action chosen by the target policy in state s . Further, let r(s, a, s ) be the reward incurred in this transition. Let A = E φ(s, a)(φ(s, a) − γφ(s , a )) and b = E[r(s, a, s )φ(s, a)]. Assume that A is non-singular. Then the parameter vector θt converges with probability one to a TD solution (4), provided that s1 is selected from the steady-state distribution µ. The proof is almost identical to that of Theorem 4.2, and hence it is omitted. Our main convergence results are also readily generalized to stochastic target policies by replacing the sub-sampling process described in Section 2 with a sample-weighting process. That is, instead of including or excluding transitions depending upon whether the action taken matches a deterministic policy, we include all transitions but give each a weight. For example, we might let the weight wt for time step t be equal to the probability π(st , at ) of taking the action actually taken under the target policy. We can consider the i.i.d. samples now to have four components (φk , rk , φk , wk ), with the update rules (9) and (10) replaced by uk+1 = uk + βk (δk φk − uk )wk , (14) θk+1 = θk + αk (φk − γφk )φk uk wk . (15) and Each sample is also weighted by wk in the expected values, such as that deﬁning the TD solution (4). With these changes, Theorems 4.1 and 4.2 go through immediately for stochastic policies. The reweighting is, in effect, an adjustment to the i.i.d. sampling distribution, µ, and thus our results hold because they hold for all µ. The choice wt = π(st , at ) is only one possibility, notable for its equivalence to our original case if the target policy is deterministic. Another natural weighting is wt = π(st , at )/πb (st , at ), where πb is the behavior policy. This weighting may result in the TD solution (4) better matching the target policy’s value function (1). 6 6 Related work There have been several prior attempts to attain the four desirable algorithmic features mentioned at the beginning this paper (off-policy stability, temporal-difference learning, linear function approximation, and O(n) complexity) but none has been completely successful. One idea for retaining all four desirable features is to use importance sampling techniques to reweight off-policy updates so that they are in the same direction as on-policy updates in expected value (Precup, Sutton & Dasgupta 2001; Precup, Sutton & Singh 2000). Convergence can sometimes then be assured by existing results on the convergence of on-policy methods (Tsitsiklis & Van Roy 1997; Tadic 2001). However, the importance sampling weights are cumulative products of (possibly many) target-to-behavior-policy likelihood ratios, and consequently they and the corresponding updates may be of very high variance. The use of “recognizers” to construct the target policy directly from the behavior policy (Precup, Sutton, Paduraru, Koop & Singh 2006) is one strategy for limiting the variance; another is careful choice of the target policies (see Precup, Sutton & Dasgupta 2001). However, it remains the case that for all of such methods to date there are always choices of problem, behavior policy, and target policy for which the variance is inﬁnite, and thus for which there is no guarantee of convergence. Residual gradient algorithms (Baird 1995) have also been proposed as a way of obtaining all four desirable features. These methods can be viewed as gradient descent in the expected squared TD error, E δ 2 ; thus they converge stably to the solution that minimizes this objective for arbitrary differentiable function approximators. However, this solution has always been found to be much inferior to the TD solution (exempliﬁed by (4) for the one-step linear case). In the literature (Baird 1995; Sutton & Barto 1998), it is often claimed that residual-gradient methods are guaranteed to ﬁnd the TD solution in two special cases: 1) systems with deterministic transitions and 2) systems in which two samples can be drawn for each next state (e.g., for which a simulation model is available). Our own analysis indicates that even these two special requirements are insufﬁcient to guarantee convergence to the TD solution.2 Gordon (1995) and others have questioned the need for linear function approximation. He has proposed replacing linear function approximation with a more restricted class of approximators, known as averagers, that never extrapolate outside the range of the observed data and thus cannot diverge. Rightly or wrongly, averagers have been seen as being too constraining and have not been used on large applications involving online learning. Linear methods, on the other hand, have been widely used (e.g., Baxter, Tridgell & Weaver 1998; Sturtevant & White 2006; Schaeffer, Hlynka & Jussila 2001). The need for linear complexity has also been questioned. Second-order methods for linear approximators, such as LSTD (Bradtke & Barto 1996; Boyan 2002) and LSPI (Lagoudakis & Parr 2003; see also Peters, Vijayakumar & Schaal 2005), can be effective on moderately sized problems. If the number of features in the linear approximator is n, then these methods require memory and per-timestep computation that is O(n2 ). Newer incremental methods such as iLSTD (Geramifard, Bowling & Sutton 2006) have reduced the per-time-complexity to O(n), but are still O(n2 ) in memory. Sparsiﬁcation methods may reduce the complexity further, they do not help in the general case, and may apply to O(n) methods as well to further reduce their complexity. Linear function approximation is most powerful when very large numbers of features are used, perhaps millions of features (e.g., as in Silver, Sutton & M¨ ller 2007). In such cases, O(n2 ) methods are not feasible. u 7 Conclusion GTD(0) is the ﬁrst off-policy TD algorithm to converge under general conditions with linear function approximation and linear complexity. As such, it breaks new ground in terms of important, 2 For a counterexample, consider that given in Dayan’s (1992) Figure 2, except now consider that state A is actually two states, A and A’, which share the same feature vector. The two states occur with 50-50 probability, and when one occurs the transition is always deterministically to B followed by the outcome 1, whereas when the other occurs the transition is always deterministically to the outcome 0. In this case V (A) and V (B) will converge under the residual-gradient algorithm to the wrong answers, 1/3 and 2/3, even though the system is deterministic, and even if multiple samples are drawn from each state (they will all be the same). 7 absolute abilities not previous available in existing algorithms. We have conducted empirical studies with the GTD(0) algorithm and have conﬁrmed that it converges reliably on standard off-policy counterexamples such as Baird’s (1995) “star” problem. On on-policy problems such as the n-state random walk (Sutton 1988; Sutton & Barto 1998), GTD(0) does not seem to learn as efﬁciently as classic TD(0), although we are still exploring different ways of setting the step-size parameters, and other variations on the algorithm. It is not clear that the GTD(0) algorithm in its current form will be a fully satisfactory solution to the off-policy learning problem, but it is clear that is breaks new ground and achieves important abilities that were previously unattainable. Acknowledgments The authors gratefully acknowledge insights and assistance they have received from David Silver, Eric Wiewiora, Mark Ring, Michael Bowling, and Alborz Geramifard. This research was supported by iCORE, NSERC and the Alberta Ingenuity Fund. References Baird, L. C. (1995). Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the Twelfth International Conference on Machine Learning, pp. 30–37. Morgan Kaufmann. Baxter, J., Tridgell, A., Weaver, L. (1998). Experiments in parameter learning using temporal differences. International Computer Chess Association Journal, 21, 84–99. Bertsekas, D. P., Tsitsiklis. J. (1996). Neuro-Dynamic Programming. Athena Scientiﬁc, 1996. Borkar, V. S. and Meyn, S. P. (2000). The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control And Optimization , 38(2):447–469. Boyan, J. (2002). Technical update: Least-squares temporal difference learning. Machine Learning, 49:233– 246. Bradtke, S., Barto, A. G. (1996). Linear least-squares algorithms for temporal difference learning. Machine Learning, 22:33–57. Dayan, P. (1992). The convergence of TD(λ) for general λ. Machine Learning, 8:341–362. Geramifard, A., Bowling, M., Sutton, R. S. (2006). Incremental least-square temporal difference learning. Proceedings of the National Conference on Artiﬁcial Intelligence, pp. 356–361. Gordon, G. J. (1995). Stable function approximation in dynamic programming. Proceedings of the Twelfth International Conference on Machine Learning, pp. 261–268. Morgan Kaufmann, San Francisco. Lagoudakis, M., Parr, R. (2003). Least squares policy iteration. Journal of Machine Learning Research, 4:1107-1149. Peters, J., Vijayakumar, S. and Schaal, S. (2005). Natural Actor-Critic. Proceedings of the 16th European Conference on Machine Learning, pp. 280–291. Precup, D., Sutton, R. S. and Dasgupta, S. (2001). Off-policy temporal-difference learning with function approximation. Proceedings of the 18th International Conference on Machine Learning, pp. 417–424. Precup, D., Sutton, R. S., Paduraru, C., Koop, A., Singh, S. (2006). Off-policy Learning with Recognizers. Advances in Neural Information Processing Systems 18. Precup, D., Sutton, R. S., Singh, S. (2000). Eligibility traces for off-policy policy evaluation. Proceedings of the 17th International Conference on Machine Learning, pp. 759–766. Morgan Kaufmann. Schaeffer, J., Hlynka, M., Jussila, V. (2001). Temporal difference learning applied to a high-performance gameplaying program. Proceedings of the International Joint Conference on Artiﬁcial Intelligence, pp. 529–534. Silver, D., Sutton, R. S., M¨ ller, M. (2007). Reinforcement learning of local shape in the game of Go. u Proceedings of the 20th International Joint Conference on Artiﬁcial Intelligence, pp. 1053–1058. Sturtevant, N. R., White, A. M. (2006). Feature construction for reinforcement learning in hearts. In Proceedings of the 5th International Conference on Computers and Games. Sutton, R. S. (1988). Learning to predict by the method of temporal differences. Machine Learning, 3:9–44. Sutton, R. S., Barto, A. G. (1998). Reinforcement Learning: An Introduction. MIT Press. Sutton, R.S., Precup D. and Singh, S (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artiﬁcial Intelligence, 112:181–211. Sutton, R. S., Rafols, E.J., and Koop, A. 2006. Temporal abstraction in temporal-difference networks. Advances in Neural Information Processing Systems 18. Tadic, V. (2001). On the convergence of temporal-difference learning with linear function approximation. In Machine Learning 42:241–267 Tsitsiklis, J. N., and Van Roy, B. (1997). An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42:674–690. Watkins, C. J. C. H. (1989). Learning from Delayed Rewards. Ph.D. thesis, Cambridge University. 8

6 0.20602989 177 nips-2008-Particle Filter-based Policy Gradient in POMDPs

7 0.17710494 87 nips-2008-Fitted Q-iteration by Advantage Weighted Regression

8 0.1622711 37 nips-2008-Biasing Approximate Dynamic Programming with a Lower Discount Factor

9 0.15043983 39 nips-2008-Bounding Performance Loss in Approximate MDP Homomorphisms

10 0.14871043 173 nips-2008-Optimization on a Budget: A Reinforcement Learning Approach

11 0.13139099 144 nips-2008-Multi-resolution Exploration in Continuous Spaces

12 0.12961996 121 nips-2008-Learning to Use Working Memory in Partially Observable Environments through Dopaminergic Reinforcement

13 0.12150624 230 nips-2008-Temporal Difference Based Actor Critic Learning - Convergence and Neural Implementation

14 0.11647124 94 nips-2008-Goal-directed decision making in prefrontal cortex: a computational framework

15 0.11493686 223 nips-2008-Structure Learning in Human Sequential Decision-Making

16 0.11156663 210 nips-2008-Signal-to-Noise Ratio Analysis of Policy Gradient Algorithms

17 0.10714529 141 nips-2008-Multi-Agent Filtering with Infinitely Nested Beliefs

18 0.073626041 212 nips-2008-Skill Characterization Based on Betweenness

19 0.06319274 231 nips-2008-Temporal Dynamics of Cognitive Control

20 0.062772006 96 nips-2008-Hebbian Learning of Bayes Optimal Decisions

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.184), (1, 0.446), (2, -0.041), (3, -0.193), (4, 0.199), (5, 0.128), (6, 0.164), (7, -0.138), (8, -0.201), (9, -0.033), (10, 0.045), (11, -0.04), (12, 0.016), (13, -0.027), (14, 0.004), (15, -0.037), (16, -0.024), (17, -0.023), (18, 0.012), (19, 0.001), (20, 0.013), (21, 0.08), (22, 0.096), (23, -0.07), (24, -0.014), (25, -0.054), (26, -0.012), (27, 0.053), (28, -0.026), (29, 0.046), (30, 0.016), (31, -0.042), (32, 0.012), (33, 0.001), (34, 0.039), (35, 0.004), (36, -0.125), (37, 0.035), (38, -0.026), (39, 0.007), (40, -0.112), (41, 0.044), (42, -0.009), (43, 0.012), (44, 0.078), (45, -0.016), (46, -0.024), (47, 0.034), (48, 0.054), (49, 0.006)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.98115951 131 nips-2008-MDPs with Non-Deterministic Policies

Author: Mahdi M. Fard, Joelle Pineau

2 0.84543091 181 nips-2008-Policy Search for Motor Primitives in Robotics

Author: Jens Kober, Jan R. Peters

3 0.83176601 195 nips-2008-Regularized Policy Iteration

Author: Amir M. Farahmand, Mohammad Ghavamzadeh, Shie Mannor, Csaba Szepesvári

4 0.82517081 150 nips-2008-Near-optimal Regret Bounds for Reinforcement Learning

Author: Peter Auer, Thomas Jaksch, Ronald Ortner

5 0.80494738 1 nips-2008-A Convergent $O(n)$ Temporal-difference Algorithm for Off-policy Learning with Linear Function Approximation

Author: Richard S. Sutton, Hamid R. Maei, Csaba Szepesvári

6 0.77574033 39 nips-2008-Bounding Performance Loss in Approximate MDP Homomorphisms

7 0.73222405 94 nips-2008-Goal-directed decision making in prefrontal cortex: a computational framework

8 0.69857746 87 nips-2008-Fitted Q-iteration by Advantage Weighted Regression

9 0.64055914 37 nips-2008-Biasing Approximate Dynamic Programming with a Lower Discount Factor

10 0.6375342 173 nips-2008-Optimization on a Budget: A Reinforcement Learning Approach

11 0.63459206 144 nips-2008-Multi-resolution Exploration in Continuous Spaces

12 0.52825487 177 nips-2008-Particle Filter-based Policy Gradient in POMDPs

13 0.43726847 121 nips-2008-Learning to Use Working Memory in Partially Observable Environments through Dopaminergic Reinforcement

14 0.42971629 212 nips-2008-Skill Characterization Based on Betweenness

15 0.42713821 230 nips-2008-Temporal Difference Based Actor Critic Learning - Convergence and Neural Implementation

16 0.33095604 222 nips-2008-Stress, noradrenaline, and realistic prediction of mouse behaviour using reinforcement learning

17 0.32554749 210 nips-2008-Signal-to-Noise Ratio Analysis of Policy Gradient Algorithms

18 0.30589464 13 nips-2008-Adapting to a Market Shock: Optimal Sequential Market-Making

19 0.29857433 223 nips-2008-Structure Learning in Human Sequential Decision-Making

20 0.27287799 141 nips-2008-Multi-Agent Filtering with Infinitely Nested Beliefs

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(4, 0.064), (6, 0.036), (7, 0.048), (12, 0.023), (15, 0.013), (28, 0.134), (57, 0.04), (59, 0.019), (63, 0.03), (71, 0.416), (77, 0.058), (83, 0.038)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.88401288 220 nips-2008-Spike Feature Extraction Using Informative Samples

Author: Zhi Yang, Qi Zhao, Wentai Liu

Abstract: This paper presents a spike feature extraction algorithm that targets real-time spike sorting and facilitates miniaturized microchip implementation. The proposed algorithm has been evaluated on synthesized waveforms and experimentally recorded sequences. When compared with many spike sorting approaches our algorithm demonstrates improved speed, accuracy and allows unsupervised execution. A preliminary hardware implementation has been realized using an integrated microchip interfaced with a personal computer. 1

2 0.82938856 161 nips-2008-On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization

Author: Sham M. Kakade, Karthik Sridharan, Ambuj Tewari

Abstract: This work characterizes the generalization ability of algorithms whose predictions are linear in the input vector. To this end, we provide sharp bounds for Rademacher and Gaussian complexities of (constrained) linear classes, which directly lead to a number of generalization bounds. This derivation provides simpliﬁed proofs of a number of corollaries including: risk bounds for linear prediction (including settings where the weight vectors are constrained by either L2 or L1 constraints), margin bounds (including both L2 and L1 margins, along with more general notions based on relative entropy), a proof of the PAC-Bayes theorem, and upper bounds on L2 covering numbers (with Lp norm constraints and relative entropy constraints). In addition to providing a uniﬁed analysis, the results herein provide some of the sharpest risk and margin bounds. Interestingly, our results show that the uniform convergence rates of empirical risk minimization algorithms tightly match the regret bounds of online learning algorithms for linear prediction, up to a constant factor of 2. 1

3 0.80764538 11 nips-2008-A spatially varying two-sample recombinant coalescent, with applications to HIV escape response

Author: Alexander Braunstein, Zhi Wei, Shane T. Jensen, Jon D. Mcauliffe

Abstract: Statistical evolutionary models provide an important mechanism for describing and understanding the escape response of a viral population under a particular therapy. We present a new hierarchical model that incorporates spatially varying mutation and recombination rates at the nucleotide level. It also maintains separate parameters for treatment and control groups, which allows us to estimate treatment effects explicitly. We use the model to investigate the sequence evolution of HIV populations exposed to a recently developed antisense gene therapy, as well as a more conventional drug therapy. The detection of biologically relevant and plausible signals in both therapy studies demonstrates the effectiveness of the method. 1

same-paper 4 0.80480814 131 nips-2008-MDPs with Non-Deterministic Policies

Author: Mahdi M. Fard, Joelle Pineau

5 0.51558071 189 nips-2008-Rademacher Complexity Bounds for Non-I.I.D. Processes

Author: Mehryar Mohri, Afshin Rostamizadeh

Abstract: This paper presents the ﬁrst Rademacher complexity-based error bounds for noni.i.d. settings, a generalization of similar existing bounds derived for the i.i.d. case. Our bounds hold in the scenario of dependent samples generated by a stationary β-mixing process, which is commonly adopted in many previous studies of noni.i.d. settings. They beneﬁt from the crucial advantages of Rademacher complexity over other measures of the complexity of hypothesis classes. In particular, they are data-dependent and measure the complexity of a class of hypotheses based on the training sample. The empirical Rademacher complexity can be estimated from such ﬁnite samples and lead to tighter generalization bounds. We also present the ﬁrst margin bounds for kernel-based classiﬁcation in this non-i.i.d. setting and brieﬂy study their convergence.

6 0.50793439 96 nips-2008-Hebbian Learning of Bayes Optimal Decisions

7 0.49817425 59 nips-2008-Dependent Dirichlet Process Spike Sorting

8 0.49666774 85 nips-2008-Fast Rates for Regularized Objectives

9 0.48339844 150 nips-2008-Near-optimal Regret Bounds for Reinforcement Learning

10 0.47677353 5 nips-2008-A Transductive Bound for the Voted Classifier with an Application to Semi-supervised Learning

11 0.46606624 16 nips-2008-Adaptive Template Matching with Shift-Invariant Semi-NMF

12 0.45471632 37 nips-2008-Biasing Approximate Dynamic Programming with a Lower Discount Factor

13 0.45367187 133 nips-2008-Mind the Duality Gap: Logarithmic regret algorithms for online optimization

14 0.44940421 195 nips-2008-Regularized Policy Iteration

15 0.44875172 104 nips-2008-Improved Moves for Truncated Convex Models

16 0.4477205 40 nips-2008-Bounds on marginal probability distributions

17 0.44512767 179 nips-2008-Phase transitions for high-dimensional joint support recovery

18 0.44449928 94 nips-2008-Goal-directed decision making in prefrontal cortex: a computational framework

19 0.44343445 29 nips-2008-Automatic online tuning for fast Gaussian summation

20 0.43775424 245 nips-2008-Unlabeled data: Now it helps, now it doesn't