Title: Theory / Important / CS / Algo / Artificial intelligence / Reinforcement Learning
Tags: fromMath kpath

Name: A \(k\)-path
Definition: A path of length \(k\).
Page: 4
006
Chapter: 1 Bondy Murty
Reinhard Diestel
Section: 1
3
Variables: \(k\in\mathbb N\)
Notation: \(P^k\)

Question: Where is Reinforcement learning better than supervised learning ?
Answer: When learning over unexplored territories
Page: 2
Chapter: 1

Question: Where is Reinforcement learning better than unsupervised learning ?
Answer: When the goal is to increase a reward and not to find a structure
Page: 2
Chapter: 1

Question: Example of problem occuring in reinforcement learning and not in (un)supervised task
Answer: Change between exploitation and exploration
Page: 3
Chapter: 1

Name: A policy
Definition: mapping from perceived states of the environment to actions to be taken when in those states
Page: 6
Chapter: 1
Section: 3
Context: Reinforcement learning
Intuition: in psychology would be called a set of stimulus–response rules or associations.

Name: A reward signal
Definition: representing the goal of a reinforcement learning problem
Page: 6
Chapter: 1
Section: 3
Context: Reinforcement learning
DefType: A (stochastic) function of the state of the environment and the actions taken to number

Name: A reward
Definition: A number received at a precise time during a run
Page: 6
Chapter: 1
Section: 3
Context: Reinforcement learning
Intuition: Pain/pleasure

Name: Value function
Definition: what is good in the long run
Page: 6, 9
Chapter: 1
Section: 3
Context: Reinforcement learning
Notation: \(V(s)\)

Name: Value of s
Definition: the total amount of reward an agent can expect to accumulate over the future, starting from that state s
Page: 6
Chapter: 1
Section: 3
Variables: s a state
Context: Reinforcement learning
Intuition: long term reward

Left: value
Right: long term goal
Left2: reward
Right2: immediate pain/pleasure
Page: 6
Chapter: 1
Section: 3

Name: Model of the environment
Definition: something that mimics the behavior of the environment, or more generally, that allows inferences to be made about how the environment will behave.
Page: 7
Chapter: 1
Section: 3
Context: Reinforcement learning
Intuition: Used to determine future actions without having to live them

Name: Model-based method
Definition: A method to solve RL problems that uses a model
Page: 7
Chapter: 1
Section: 3
Context: Reinforcement learning

Name: Model-free method
Definition: A method to solve RL problems that doesn't use a model
Page: 7
Chapter: 1
Section: 3
Context: Reinforcement learning
Intuition: Trial and error

Name: Elements of reinforcement learning
Definition: Policy
Page: 7
Chapter: 1
Section: 3
Context: Reinforcement learning
Definition2: Reward signal
Definition3: function value
Definition4: Model

Name: A greedy move
Definition: A move that maximise the next state's value
Page: 9
Chapter: 1
Section: 5

Name: An exploratory move
Definition: A move that is not greedy
Page: 9
Chapter: 1
Section: 5
Etymology: Allow to investigate moves that may have been omitted because assumed not to be optimal

Name: A temporal difference learning method
Definition: A method that update the value of a state depending on the difference between this step and next step's value
Page: 10
Chapter: 1
Section: 5

Name: A step-size parameter
Definition: A parameter indicating how strongly an update should be taken into account
Page: 10
Chapter: 1
Section: 5
Denoted by: \(\alpha\)

Name: A tabular solution method
Definition: A method such that the number of states and their values is small enough that it can fit in a table in memory
Page: 23
Chapter: I

Question: which tabular method should be used if we have a complete and accurate model ow the environment
Answer: dynamic programming
Page: 23
Chapter: I

Question: which tabular method should be used if we don't have a model and can't do step-by-step update
Answer: Monte Carlo
Page: 23
Chapter: I

Question: which tabular method should be used if you don't have a model and need step-by-step incremental computation
Answer: temporal-difference method
Page: 23
Chapter: I

Definition: The action selected at time \(t\)
Page: 26
Chapter: 2
Variables: \(t\in\mathbb N\)
Context: The \(k\)-armed bandit problem
Notation: \(A_t\)

Definition: The reward from the action at time \(t\)
Page: 26
Chapter: 2
Variables: \(t\in\mathbb N\)
Context: The \(k\)-armed bandit problem
Notation: \(R_t\)

Name: The value of the action \(a\)
Definition: \(\mathbb E[R_t\mid A_t=a]\)
Page: 26
Chapter: 2
Variables: \(t\in\mathbb N\)
\(a\) an action
Context: The \(k\)-armed bandit problem
Notation: \(q_*(a)\)

Name: The estimated value of action \(a\) at time \(t\)
Page: 26
Chapter: 2
Variables: \(t\in\mathbb N\)
\(a\) an action
Context: The \(k\)-armed bandit problem
Notation: \(Q_t(a)\)

Name: The \(k\)-armed bandit problem
Definition: A game with fixed \(n\) turn. Unknown reward variables \((R_i)_{0\le i<k}\in\mathbb R\).
At each turn \(t\), select an action \(0\le A_t<k\).
Maximize \(\sum_{0\le t<n}q_*(A_t)\)
Page: 25
Chapter: 2
Extra: \(q_*(a)=\mathbb E[R_t\mid A_t=a]\)

Definition: A random variable that is 1 if \(\mathtt{predicate}\) holds and 0 otherwise
Page: 25
Chapter: 2
Notation: \( \mathbb 1_{\mathtt{predicate}}\)

Name: The sample-average method
Definition: Associating to an action the average values it led to in the past
Page: 27
Chapter: 2

Name: The \(\varepsilon\)-method
Definition: An algorithm that is exploratory \(\varepsilon\) of the time and greedy the remaining of the time
Page: 27
Chapter: 2
Variables: \(0\le\varepsilon\le 1\)

Name: The 10-armed testbed
Definition: A \(10\)-armed bandit problem, where the \(i\)-th distributions is Gaussian, with variance 1, mean \(e_i\), where the \((e_i)\)'s are selected from a Gaussian with variance 1 and mean 0.
Page: 29
Chapter: 2

Page: 31
Implementation: def running_average(stream):
  average = 0
  for (pos, elt) in enumerate(stream):
    average += (pos+1) * (elt - average)
    yield average
Section: 4
Chapter: 2
Effect: yeld the running average of all elements seen in the stream up to a certain point
Language: python
Time complexity: Linear
Space complexity: Constant
Input: a sequence of float

Question: \[(1-x)^n+\sum_{i=0}^{n-1}x(1-x)^{i}=\]
Answer: 1
Page: 33
Chapter: 2
Section: 5

Definition: the step-size parameter used to process the reward received after the \(n\)th selection of action \(a\)
Page: 33
Chapter: 2
Section: 5
Notation: \(\alpha_n(a)\)

Name: An exponential-weighted average
Definition: An average where, at the \(n\)-th step, the \(i\)-th step result is taken into account in \(O(e^{n-i})\)
Page: 33
Chapter: 2
Section: 5

Smaller0: \(\sum x_i=\infty\)
Greater0: \((u_i)_{i\in\mathbb N}\) converges with probability 1.
Page: 33
Chapter: 2
Section: 5
Assuming: \((x_i)_{i\in\mathbb N}\in[0,1]\)
\((r_i)_{i\in\mathbb N}\in\mathbb R\) generated by a random distribution
\((u_i)_{i\in\mathbb N}\) with \(u_{i+1}=u_i+x_i(r_i-u_i)\)
Smaller1: \(\sum x_i^2<\infty\)

Name: A biased decision
Definition: A decision that is taken due to initial assumption that were hard-coded and not checked
Page: 34
Chapter: 2
Section: 6
Context: Reinforcement learning
Assuming: \((x_i)_{i\in\mathbb N}\in[0,1]\)
\((r_i)_{i\in\mathbb N}\in\mathbb R\) generated by a random distribution
\((u_i)_{i\in\mathbb N}\) with \(u_{i+1}=u_i+x_i(r_i-u_i)\)

Page: 34
Implementation: give an overly optimistic initial value to all actions
Section: 6
Chapter: 2
Effect: Ensure that (\(\epsilon-)\)greedy algorithm start by testing all actions without having to encode a special case for start of the method
Context: Reinforcement learning
Assuming: stationnary distribution