Answers.Body: <p>The concepts of on-policy vs off-policy and online vs offline are separate, but do interact to make certain combinations more feasible. When looking at this, it is worth also considering the difference between <em>prediction</em> and <em>control</em> in Reinforcement Learning (RL).</p>
  
  <h2>Online vs Offline</h2>
  
  <p>These concepts are not specific to RL, many learning systems can be categorised as online or offline (or somewhere in-between).</p>
  
  <ul>
  <li><p><strong>Online</strong> learning algorithms work with data as it is made available. Strictly online algorithms improve incrementally from each piece of new data as it arrives, then discard that data and do not use it again. It is not a requirement, but it is commonly desirable for an online algorithm to forget older examples over time, so that it can adapt to non-stationary populations. Stochastic gradient descent with back-propagation - as used in neural networks - is an example.</p></li>
  <li><p><strong>Offline</strong> learning algorithms work with data in bulk, from a dataset. Strictly offline learning algorithms need to be re-run from scratch in order to learn from changed data. Support vector machines and random forests are strictly offline algorithms (although researchers have constructed online variants of them).</p></li>
  </ul>
  
  <p>Of the two types, <em>online</em> algorithms are more general in that you can easily construct an offline algorithm from a strictly online one plus a stored dataset, but the opposite is not true for a strictly offline algorithm. However, this does not necessarily make them superior - often compromises are made in terms of sample efficiency, CPU cost or accuracy when using an online algorithm. Approaches such as mini-batches in neural network training can be viewed as attempts to find a middle ground between online and offline algorithms.</p>
  
  <p>Experience replay, a common RL technique, used in Deep Q Networks amongst others, is another in-between approach. Although you <em>could</em> store all the experience necessary to fully train an agent in theory, typically you store a rolling history and sample from it. It's possible to argue semantics about this, but I view the approach as being a kind of "buffered online", as it requires low-level components that can work online (e.g. neural networks for DQN).</p>
  
  <h2>On-policy vs Off-Policy</h2>
  
  <p>These are more specific to control systems and RL. Despite the similarities in name between these concepts and online/offline, they refer to a different part of the problem.</p>
  
  <ul>
  <li><p><strong>On-policy</strong> algorithms work with a single policy, often symbolised as <span class="math-container">$\pi$</span>, and require any observations (state, action, reward, next state) to have been generated using that policy. </p></li>
  <li><p><strong>Off-policy</strong> algorithms work with two policies (sometimes effectively more, though never more than two per step). These are a policy being learned, called the target policy (usually shown as <span class="math-container">$\pi$</span>), and the policy being followed that generates the observations, called the behaviour policy (called various things in the literature - <span class="math-container">$\mu$</span>, <span class="math-container">$\beta$</span>, Sutton and Barto call it <span class="math-container">$b$</span> in the latest edition).</p>
  
  <ul>
  <li>A very common scenario for off-policy learning is to learn about best guess at optimal policy from an exploring policy, but that is not the definition of off-policy.</li>
  <li>The primary difference between observations generated by <span class="math-container">$b$</span> and the target policy <span class="math-container">$\pi$</span> is which actions are selected on each time step. There is also a secondary difference which can be important: The population distribution of both states and actions in the observations can be different between <span class="math-container">$b$</span> and <span class="math-container">$\pi$</span> - this can have an impact for function approximation, as cost functions (for e.g. NNs) are usually optimised over a population of data.</li>
  </ul></li>
  </ul>
  
  <p>In both cases, there is no requirement for the observations to be processed strictly online or offline.</p>
  
  <p>In contrast to the relationship between online and offline learning, off-policy is always a strict generalisation of on-policy. You can make any off-policy algorithm into an equivalent on-policy one by setting <span class="math-container">$\pi = b$</span>. There is a sense in which you can do this by degrees, by making <span class="math-container">$b$</span> closer to <span class="math-container">$\pi$</span> (for instance, reducing <span class="math-container">$\epsilon$</span> in an <span class="math-container">$\epsilon$</span>-greedy behaviour policy for <span class="math-container">$b$</span> where <span class="math-container">$\pi$</span> is the fully greedy policy). This can be desirable, as off-policy agents do still need to observe states and actions that occur under the target policy - if that happens rarely because of differences between <span class="math-container">$b$</span> and <span class="math-container">$\pi$</span>, then learning about the target policy will happen slowly.</p>
  
  <h2>Prediction vs Control</h2>
  
  <p>This can get forgotten due to the focus on search for optimal policies.</p>
  
  <ul>
  <li><p>The <strong>prediction</strong> problem in RL is to estimate the value of a particular state or state/action pair, given an environment and a policy.</p></li>
  <li><p>The (optimal) <strong>control</strong> problem in RL is to find the best policy given an environment. </p></li>
  </ul>
  
  <p>Solving the control problem when using value-based methods involves both estimating the value of being in a certain state (i.e. solving the prediction problem), and adjusting the policy to make higher value choices based on those estimates. This is called <a href="http://www.incompleteideas.net/book/ebook/node46.html" rel="noreferrer">generalised policy iteration</a>.</p>
  
  <p>The main thing to note here is that the prediction problem is stationary (all long-term expected distributions are the same over time), whilst the control problem adds non-stationary target for the prediction component (the policy changes, so does the expected return, distribution of states etc) </p>
  
  <h2>Combinations That Work</h2>
  
  <p>Note this is not about choice of algorithms. The strongest driver for algorithm choice is on-policy (e.g. SARSA) vs off-policy (e.g. Q-learning). The same core learning algorithms can often be used online or offline, for prediction or for control.</p>
  
  <ul>
  <li><p>Online, on-policy prediction. A learning agent is set the task of evaluating certain states (or state/action pairs), and learns from observation data as it arrives. It should always act the same way (it may be observing some other control system with a fixed, and maybe unknown policy).</p></li>
  <li><p>Online, off-policy prediction. A learning agent is set the task of evaluating certain states (or state/action pairs) from the perspective of an arbitrary fixed target policy <span class="math-container">$\pi$</span> (which must be defined to the agent), and learns from observation data as it arrives. The observations can be from any behaviour policy <span class="math-container">$b$</span> - depending on the algorithm being used, it may be necessary to have <span class="math-container">$b$</span> defined as well as <span class="math-container">$\pi$</span>.</p></li>
  <li><p>Offline, on-policy prediction. A learning agent is set the task of evaluating certain states (or state/action pairs), and is given a dataset of observations from the environment of an agent acting using some fixed policy.</p></li>
  <li><p>Offline, off-policy prediction. A learning agent is set the task of evaluating certain states (or state/action pairs) from the perspective of an arbitrary fixed target policy <span class="math-container">$\pi$</span> (which must be defined to the agent), and is given a dataset of observations from the environment of an agent acting using some other policy <span class="math-container">$b$</span>. </p></li>
  <li><p>Online, on-policy control. A learning agent is set the task of behaving optimally in an environment, and learns from each observations as it arrives. It will adapt its own policy as it learns, making this a non-stationary problem, and also importantly <em>making its own history of observations off-policy</em> data. </p></li>
  <li><p>Online, off-policy control. A learning agent is set the task of behaving optimally in an environment. It may behave and gain observations from a behaviour policy <span class="math-container">$b$</span>, but learns a separate optimal target policy <span class="math-container">$\pi$</span>. It is common to link <span class="math-container">$b$</span> and <span class="math-container">$\pi$</span> - e.g. for <span class="math-container">$\pi$</span> to be deterministic greedy policy with respect to estimated action values, and for <span class="math-container">$b$</span> to be <span class="math-container">$\epsilon$</span>-greedy policy with respect to the same action values.</p></li>
  <li><p>Offline, on-policy control. This not really possible in general, as an on-policy agent needs to be able to observe data about its current policy. As soon as it has learned a policy different to that in the stored dataset, then all the data becomes off-policy to it, and the agent has no valid source data. In some cases you might still be able to get something to work.</p></li>
  <li><p>Offline, off-policy control. A learning agent is set the task of learning an optimal policy from a store dataset of observations. The observations can be from any behaviour policy <span class="math-container">$b$</span> - depending on the algorithm being used, it may be necessary to have <span class="math-container">$b$</span> defined as well as <span class="math-container">$\pi$</span>.</p></li>
  </ul>
  
  <p>As you can see above, only one combination <em>offline, on-policy control</em>, causes a clash.</p>
  
  <p>There is a strong skew towards online learning in RL. Approaches that buffer some data, such as Monte Carlo control, experience replay or Dyna-Q do mix-in some of the traits of offline learning, but still require a constant supply of new observations plus forget older ones. Control algorithms imply non-stationary data, and these require online forgetting behaviour from the estimators - another online learning trait.</p>
  
  <p>However, mixing in a little "offline" data in experience replay can cause some complications for on-policy control algorithms. The experience buffer can contain things that are technically off-policy to the latest iteration of the agent. How much of a problem this is in practice will vary.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T20:34:58.533Z
Answers.Text: I understand your sentence "the policy changes, so does the expected return, distribution of states etc" (because I associate it with the [generalized policy iteration](http://www.incompleteideas.net/book/ebook/node46.html)). However, I can't really understand what you mean by "the prediction problem is stationary (all long-term expected distributions are the same over time)". Which distributions are you talking about?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T21:06:43.887Z
Answers.Text: @nbro: I was thinking of two main distributions: (1) Distribution of returns from any given state or state/action pair. (2) Distribution of states over multiple episodes (or steady-state distribution of states for continuous problems).
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T21:37:38.077Z
Answers.Text: The distribution of rewards or states may be stationary (i.e. the MDP may not change over time), but the sequence of rewards or states may be different (from episode to episode). So, I am not sure if denoting the prediction problem "stationary" is appropriate. It is at least ambiguous and confusing. Also, saying "he control problem adds non-stationary target for the prediction component" may be a little bit an abuse of terminology? Maybe you could have said "changing target"?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-11T07:33:23.940Z
Answers.Text: @nbro: No, I mean the term as I wrote it. Solving the prediction problem when policy and dynamics are fixed leads to collecting data from a stationary distribution - i.e. collected data from the first 100 episodes and last set of 100 episodes (out of some larger set e.g. 1000 episodes) should have same expected returns, expected state distributions etc
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T16:15:46.090Z
Answers.Text: Would it be possible to have an example of a real algorithm for each of your possible combinations? Also, when you mention the difference between "online" and "offline" algorithms, you mention ML algorithms (stochastic gradient descent, etc). I think it would be more useful to mention algorithms which are online or offline in the context of RL. I am quite familiar with the concept of "online" and "offline" algorithms in ML, but, in the context of RL, when I think about online or offline algorithms, no algorithm comes to my mind.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T17:21:46.027Z
Answers.Text: The algorithms are not necessarily different between online and offline. E.g. Q-learning could be a valid choice for all four off-policy examples. The reason you cannot think of online vs offline examples is likely because everything you are thinking of is more online than offline. Training *purely* offline is more niche, or might be used to pre-train an agent for real-world use if a simulated environment is not available.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T14:49:11.147Z
Answers.LastActivityDate: 2019-02-10T17:27:19.910Z
Answers.LastEditDate: 2019-02-10T17:27:19.910Z
Answers.UserDisplayName: Neil Slater
Body: <p>In the context of RL, there is the notion of <strong>on-policy</strong> and <strong>off-policy</strong> algorithms. I understand the difference between on-policy and off-policy algorithms. Moreover, in RL, there's also the notion of <strong>online</strong> and <strong>offline</strong> learning.</p>
  <p>What is the relation (including the differences) between online learning and on-policy algorithms? Similarly, what is the relation between offline learning and off-policy algorithms?</p>
  <p>Finally, is there any relation between online (or offline) learning and off-policy (or on-policy) algorithms? For example, can an on-policy algorithm perform offline learning? If yes, can you explain why?</p>
  
Tags: <reinforcement-learning><off-policy-methods><on-policy-methods><online-learning><offline-reinforcement-learning>
Title: What is the relation between online (or offline) learning and on-policy (or off-policy) algorithms?
UserDisplayName: nbro
ThreadText: # What is the relation between online (or offline) learning and on-policy (or off-policy) algorithms?
  
  (Asked by: username_0 on 2019-02-09)
  
  In the context of RL, there is the notion of **on-policy** and **off-policy** algorithms. I understand the difference between on-policy and off-policy algorithms. Moreover, in RL, there's also the notion of **online** and **offline** learning.
  
  What is the relation (including the differences) between online learning and on-policy algorithms? Similarly, what is the relation between offline learning and off-policy algorithms?
  
  Finally, is there any relation between online (or offline) learning and off-policy (or on-policy) algorithms? For example, can an on-policy algorithm perform offline learning? If yes, can you explain why?
  
  **Tags:** reinforcement-learning, off-policy-methods, on-policy-methods, online-learning, offline-reinforcement-learning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-02-10. Score: 21
  
  The concepts of on-policy vs off-policy and online vs offline are separate, but do interact to make certain combinations more feasible. When looking at this, it is worth also considering the difference between *prediction* and *control* in Reinforcement Learning (RL).
  
  ## Online vs Offline
  
  These concepts are not specific to RL, many learning systems can be categorised as online or offline (or somewhere in-between).
  
  * **Online** learning algorithms work with data as it is made available. Strictly online algorithms improve incrementally from each piece of new data as it arrives, then discard that data and do not use it again. It is not a requirement, but it is commonly desirable for an online algorithm to forget older examples over time, so that it can adapt to non-stationary populations. Stochastic gradient descent with back-propagation - as used in neural networks - is an example.
  * **Offline** learning algorithms work with data in bulk, from a dataset. Strictly offline learning algorithms need to be re-run from scratch in order to learn from changed data. Support vector machines and random forests are strictly offline algorithms (although researchers have constructed online variants of them).
  
  Of the two types, *online* algorithms are more general in that you can easily construct an offline algorithm from a strictly online one plus a stored dataset, but the opposite is not true for a strictly offline algorithm. However, this does not necessarily make them superior - often compromises are made in terms of sample efficiency, CPU cost or accuracy when using an online algorithm. Approaches such as mini-batches in neural network training can be viewed as attempts to find a middle ground between online and offline algorithms.
  
  Experience replay, a common RL technique, used in Deep Q Networks amongst others, is another in-between approach. Although you *could* store all the experience necessary to fully train an agent in theory, typically you store a rolling history and sample from it. It's possible to argue semantics about this, but I view the approach as being a kind of "buffered online", as it requires low-level components that can work online (e.g. neural networks for DQN).
  
  ## On-policy vs Off-Policy
  
  These are more specific to control systems and RL. Despite the similarities in name between these concepts and online/offline, they refer to a different part of the problem.
  
  * **On-policy** algorithms work with a single policy, often symbolised as $\pi$, and require any observations (state, action, reward, next state) to have been generated using that policy.
  * **Off-policy** algorithms work with two policies (sometimes effectively more, though never more than two per step). These are a policy being learned, called the target policy (usually shown as $\pi$), and the policy being followed that generates the observations, called the behaviour policy (called various things in the literature - $\mu$, $\beta$, Sutton and Barto call it $b$ in the latest edition).
  
    + A very common scenario for off-policy learning is to learn about best guess at optimal policy from an exploring policy, but that is not the definition of off-policy.
    + The primary difference between observations generated by $b$ and the target policy $\pi$ is which actions are selected on each time step. There is also a secondary difference which can be important: The population distribution of both states and actions in the observations can be different between $b$ and $\pi$ - this can have an impact for function approximation, as cost functions (for e.g. NNs) are usually optimised over a population of data.
  
  In both cases, there is no requirement for the observations to be processed strictly online or offline.
  
  In contrast to the relationship between online and offline learning, off-policy is always a strict generalisation of on-policy. You can make any off-policy algorithm into an equivalent on-policy one by setting $\pi = b$. There is a sense in which you can do this by degrees, by making $b$ closer to $\pi$ (for instance, reducing $\epsilon$ in an $\epsilon$-greedy behaviour policy for $b$ where $\pi$ is the fully greedy policy). This can be desirable, as off-policy agents do still need to observe states and actions that occur under the target policy - if that happens rarely because of differences between $b$ and $\pi$, then learning about the target policy will happen slowly.
  
  ## Prediction vs Control
  
  This can get forgotten due to the focus on search for optimal policies.
  
  * The **prediction** problem in RL is to estimate the value of a particular state or state/action pair, given an environment and a policy.
  * The (optimal) **control** problem in RL is to find the best policy given an environment.
  
  Solving the control problem when using value-based methods involves both estimating the value of being in a certain state (i.e. solving the prediction problem), and adjusting the policy to make higher value choices based on those estimates. This is called [generalised policy iteration](http://www.incompleteideas.net/book/ebook/node46.html).
  
  The main thing to note here is that the prediction problem is stationary (all long-term expected distributions are the same over time), whilst the control problem adds non-stationary target for the prediction component (the policy changes, so does the expected return, distribution of states etc)
  
  ## Combinations That Work
  
  Note this is not about choice of algorithms. The strongest driver for algorithm choice is on-policy (e.g. SARSA) vs off-policy (e.g. Q-learning). The same core learning algorithms can often be used online or offline, for prediction or for control.
  
  * Online, on-policy prediction. A learning agent is set the task of evaluating certain states (or state/action pairs), and learns from observation data as it arrives. It should always act the same way (it may be observing some other control system with a fixed, and maybe unknown policy).
  * Online, off-policy prediction. A learning agent is set the task of evaluating certain states (or state/action pairs) from the perspective of an arbitrary fixed target policy $\pi$ (which must be defined to the agent), and learns from observation data as it arrives. The observations can be from any behaviour policy $b$ - depending on the algorithm being used, it may be necessary to have $b$ defined as well as $\pi$.
  * Offline, on-policy prediction. A learning agent is set the task of evaluating certain states (or state/action pairs), and is given a dataset of observations from the environment of an agent acting using some fixed policy.
  * Offline, off-policy prediction. A learning agent is set the task of evaluating certain states (or state/action pairs) from the perspective of an arbitrary fixed target policy $\pi$ (which must be defined to the agent), and is given a dataset of observations from the environment of an agent acting using some other policy $b$.
  * Online, on-policy control. A learning agent is set the task of behaving optimally in an environment, and learns from each observations as it arrives. It will adapt its own policy as it learns, making this a non-stationary problem, and also importantly *making its own history of observations off-policy* data.
  * Online, off-policy control. A learning agent is set the task of behaving optimally in an environment. It may behave and gain observations from a behaviour policy $b$, but learns a separate optimal target policy $\pi$. It is common to link $b$ and $\pi$ - e.g. for $\pi$ to be deterministic greedy policy with respect to estimated action values, and for $b$ to be $\epsilon$-greedy policy with respect to the same action values.
  * Offline, on-policy control. This not really possible in general, as an on-policy agent needs to be able to observe data about its current policy. As soon as it has learned a policy different to that in the stored dataset, then all the data becomes off-policy to it, and the agent has no valid source data. In some cases you might still be able to get something to work.
  * Offline, off-policy control. A learning agent is set the task of learning an optimal policy from a store dataset of observations. The observations can be from any behaviour policy $b$ - depending on the algorithm being used, it may be necessary to have $b$ defined as well as $\pi$.
  
  As you can see above, only one combination *offline, on-policy control*, causes a clash.
  
  There is a strong skew towards online learning in RL. Approaches that buffer some data, such as Monte Carlo control, experience replay or Dyna-Q do mix-in some of the traits of offline learning, but still require a constant supply of new observations plus forget older ones. Control algorithms imply non-stationary data, and these require online forgetting behaviour from the estimators - another online learning trait.
  
  However, mixing in a little "offline" data in experience replay can cause some complications for on-policy control algorithms. The experience buffer can contain things that are technically off-policy to the latest iteration of the agent. How much of a problem this is in practice will vary.
  
  > **Comments:**
  > **username_0**: Would it be possible to have an example of a real algorithm for each of your possible combinations? Also, when you mention the difference between "online" and "offline" algorithms, you mention ML algorithms (stochastic gradient descent, etc). I think it would be more useful to mention algorithms which are online or offline in the context of RL. I am quite familiar with the concept of "online" and "offline" algorithms in ML, but, in the context of RL, when I think about online or offline algorithms, no algorithm comes to my mind.  
  > **username_1**: The algorithms are not necessarily different between online and offline. E.g. Q-learning could be a valid choice for all four off-policy examples. The reason you cannot think of online vs offline examples is likely because everything you are thinking of is more online than offline. Training *purely* offline is more niche, or might be used to pre-train an agent for real-world use if a simulated environment is not available.  
  > **username_0**: I understand your sentence "the policy changes, so does the expected return, distribution of states etc" (because I associate it with the [generalized policy iteration](http://www.incompleteideas.net/book/ebook/node46.html)). However, I can't really understand what you mean by "the prediction problem is stationary (all long-term expected distributions are the same over time)". Which distributions are you talking about?  
  > **username_1**: @nbro: I was thinking of two main distributions: (1) Distribution of returns from any given state or state/action pair. (2) Distribution of states over multiple episodes (or steady-state distribution of states for continuous problems).  
  > **username_0**: The distribution of rewards or states may be stationary (i.e. the MDP may not change over time), but the sequence of rewards or states may be different (from episode to episode). So, I am not sure if denoting the prediction problem "stationary" is appropriate. It is at least ambiguous and confusing. Also, saying "he control problem adds non-stationary target for the prediction component" may be a little bit an abuse of terminology? Maybe you could have said "changing target"?  
  > **username_1**: @nbro: No, I mean the term as I wrote it. Solving the prediction problem when policy and dynamics are fixed leads to collecting data from a stationary distribution - i.e. collected data from the first 100 episodes and last set of 100 episodes (out of some larger set e.g. 1000 episodes) should have same expected returns, expected state distributions etc  
  
  ---
  
  