text:
Why does using a higher representation space lead to performance increase on the training data but not on the test data?
I read the following from a book:

You can intuitively understand the dimensionality of your representation space as “how much freedom you’re allowing the model to have when learning internal representations.” Having more units (a higher-dimensional representation space) allows your model to learn more-complex representations, but it makes the model more computationally expensive and may lead to learning unwanted patterns (patterns that will improve performance on the training data but not on the test data).

Why does using a higher representation space lead to performance increase on the training data but not on the test data?
Surely the representations/patterns learnt in the training data will be found too in the test data.

Which book did you read that from?

I read it from "Deep Learning with Python" by François Chollet. You can also read it here:
https://rpubs.com/kennyboy/503107

The answer to your question is that the capacity of your model (i.e. the number and type of function that your model can compute) generally increases with the number of parameters. So, a bigger model can potentially approximate better the function represented by your training data, but, at the same time, it may not take into account the test data, a phenomenon known as over-fitting the training data (i.e. fitting "too much" the training data).
In theory, you want to fit the training data perfectly, so over-fitting should not make sense, right? The problem is that, if we just fit all the (training) data, there is no way of empirically checking that our model will perform well on unseen data, i.e. will it generalize to data not seen during training?
We split our data into training and test data because of this: we want to understand whether our model will perform well also on unseen data or not.
There are also some theoretical bounds that ensure you that, probabilistically and approximately, you can generalize: if you have more training data than a certain threshold, the probability that you perform badly is small. However, these theoretical bounds are often not taken into account in practice because, for example, we may not be able to collect more data to ensure that the bounds are satisfied.

Surely the representations/patterns learnt in the training data will be found too in the test data.

This is possibly the wrong assumption and the reason why you are confused. You may assume that both your training data and test data come from the same distribution $p(x, y)$, but it does not necessarily mean that they have the same patterns. For example, I can sample e.g. 13 numbers from a Gaussian $N(0, 1)$, the first 10 numbers could be very close to $0$ and the last $3$ could be close to $1$. If you split this data so that your training data contains different patterns than the test data, then it is not guaranteed that you will perform well also on the test data.
Finally, note that, in supervised learning, our ultimate goal when we fit models to labeled data is to learn a function (or a probability distribution over functions), where we often assume that both the training and test data are input-output pairs from our unknown target function, i.e. $y_i = f(x_i)$, where $(x_i, y_i) \in D$ (where $D$ is your labelled dataset), and $f$ is the unknown target function (i.e. the function we want to compute with our model), so, if our model performs well on the training data but not on the test data and we assume that both training and test data come from the same function $f$, there is no way that our model is computing our target function $f$ if it performs badly on the test data.


text:
Bellman optimality equation in semi Markov decision process
I wrote a Python program for a simple inventory control problem where decision epochs are equally divided (every morning) and there is no lead time for orders (the time between submitting an order until receiving the order). I use the Bellman equations, and solve them by policy iteration (Dynamic Programming).
Now I want to consider lead time (between 1 to 3 days with equal probabilities). As I understand, the problem is defined by Semi Markov Decision Process for considering sojourn time in each state. I am confused about the Bellman equations in this scenario because we don't know exactly when the order will be received and is it necessary to discount the reward for day two or three?

The core problem here is state representation, not estimating return due to delayed response to actions on the original state representation (which is no longer complete for the new problem). If you fix that, then you can solve your problem as a normal MDP, and base calculations on single timesteps. This allows you to continue using dynamic programming to solve it, provided the state space remains small enough.
What needs to change is the state representation and state transitions. Instead of orders resulting in immediate change of stock levels, they become pending changes, and for each item you will have state representation for the amount of current stock, plus amount of stock in each lead time category. State transitions will modify expected lead time for each amount of pending stock as well as amount of current stock.
Your lead time categories will depend on whether the agent knows the lead time immediately after making an order:

If lead times are known, track remaining time until items arrive 1,2 or 3 days. These categories will be assigned by the enviroment following the order, then lead time will transition down on each day deterministically. A 1 day lead time will transition to in stock, 2 day lead will transition to 1 day etc.

If lead times are not known, but probabilities of them are, track time since the order was made. This will be 0, 1 or 2 days. Although you don't know when an order will arrive, you know the probabilities for state transition - e.g. items in 0 days have a 1 in 3 chance of transitioning to "in stock" and a 2 in 3 chance of transitioning to 1 days.

This makes the state space larger, but is less complex than moving to the Semi MDP representation. For instance, doing it this way means that you can still work with single time step transitions and apply dynamic programming in a standard way.
In general, if the environment has a delayed response to actions, then the  best way to maintain Markov trait is to add relevant history of actions taken to the state. The added state variables can either be a direct list of the relevant actions, or something that tracks the logical consequence of those actions.

Dear Neil Slater
Thank you for the answer. As I understand it, I must calc the return for 0 to 2 days lead time with equal probability (1 to 3 chance) and demand with Poisson distribution with lambda parameter as follows:
( if the items arrive on day 0 with probability 0.33 * the return value) + (if the items arrive on day 1 with probability 0.33 * (the return value that calculate based on combination of demand size for day 0 and 1 (e.g.the probability of 0 demand in day 0 and 1 demand in day 1 and so on) * the return) + ...
Is it correct?
Thank you in advance.

@mnbobo: No that should not be necessary. You can stick with single time step evaluations. It is the state representation that needs to change, to properly represent the in progress orders. You will still need to model the transition probabilities on a time step by time step basis.

@mnbobo I have tried to clarify that in the answer. There is no need to calculate return across multiple time steps. That is a separate approach that you could consider for e.g. TD($\lambda$). But you cannot realistically do that directly based on the current action alone, because the agent is free to take other actions during those other days and those actions will further affect expected return. The core problem here is state representation, not estimating return due to delayed response.

Dear @Neil Slater Thanks for your reply. If we have holding cost and shortage cost, then we have some mini rewards between time epochs due to the demand arrival. For example if the lead times will be 2 days, we have holding cost or shortage cost with some probabilities on day 0 and 1. In this case, is it still unnecessary to consider these mini rewards?

@mnbobo The rewards will be as you define them for the problem. If there's a shortage based on current inventory, then there's a still shortage if an order is on the way. The default for extending your problem would be to have same rewards and costs as before. However you are in control and if you also want to have a more sophisticated model for customer behaviour you can. Typically in a toy stock model you just treat requests as random and short term, so apply rewards/costs purely on ability to immediately service them. In which case there would be no need to model extra "mini" rewards

@mnbobo: Your question did not mention any change to goals (presumably of maintaining sufficient stock to furnish requests but not too much due to costs of holding it). Nor did it mention that you wanted to make handling item requests more sophisticated. So I would suggest not changing rewards at all. Just change state (and state progression rules) to model the order delay process.

I really appreciate your help and your quick response. I will do as you said. But just out of curiosity, If the problem has holding cost and shortage cost, then expected return is calculated by following expression and considering reward and mini rewards: ( if the items arrive on day 0 with probability 0.33 * the return value) + (if the items arrive on day 1 with probability 0.33 * (the return value that calculate based on combination of demand size for day 0 and 1 (e.g.the probability of 0 demand in day 0 and 1 demand in day 1 and so on) * the return) + ... Is it true?

@mnbobo: That might be reasonable (I would need to understand your problem better to say for sure), but expected return could be more complicated than that. The point of using dynamic programming is that you don't need to figure out an analytical expected return.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Is it feasible using today's technology to use an AI training algorithm to custom teach a robot to do common household cores?
Like making a bed, washing dishes, taking out the garbage, etc., by training it on the video of specific individuals doing those cores in their own unique environments?
I have researched what machine learning is capable of doing at this point in time, and it seems this may be now feasible when done on a customer-specific basis and enable by an A.I. enhanced, full articulated, robot along the lines of an enhanced InMoov. https://en.wikipedia.org/wiki/InMoov
If it's feasible, what are the AI algorithms I should be considering to train my robot to do these tasks? Isn't deep learning the most promising of these selections:  https://www.ubuntupit.com/machine-learning-algorithms-for-both-newbies-and-professionals/?

I would suggest using a neural network with back propagation. From what I know, they can be applied to many different circumstances and work well. For your more simpler and repetitive tasks like moving an object, you can just use simpler regression methods.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
How to apply Q-learning when rewards is only available at the last state?
I have a scheduling problem in which there are $n$ slots and $m$ clients. I am trying to solve the problem using Q-learning so I have made the following state-action model.
A state $s_t$ is given by the current slot $t=1,2,\ldots,n$ and an action $a_t$ at slot $t$ is given by one client, $a_t\in\{1,2,\ldots,m\}$. In my situation, I do not have any reward associated with a state-action pair $(s_t,a_t)$ until the terminal state which is the last slot. In other words, for all $s_t\in\{1,2,\ldots,n-1\}$, the reward is $0$ and for $s_t=n$ I can compute the reward given $(a_1,a_2,\ldots,a_n)$.
In this situation, the Q table, $Q(s_t,a_t)$, will contain only zeros except for the last row in which it will contain the updated reward.
Can I still apply Q-learning in this situation? Why do I need a Q table if I only use the last row?

Your question is very similar to this one. Given that you provide an example of a specific problem, I will not close it as an exact duplicate.

Having only a non-zero reward at the very end is not uncommon. When rewards are sparse, it becomes a bit harder to learn compared to having lots of different rewards along the way, but for your problem, the goal state is always reached, so that should not be a problem. (The real problem with sparse rewards is that, if an agent can do a lot of exploration without every finding the goal, it essentially receives no feedback and will behave randomly, until it happens to stumble upon the very rare reward state.)
What concerns me more about your problem is that the final reward depends not just on the last state visited, but also on the chain of actions taken so far. That means that, to make this a proper MDP, you need to keep the chain of action in the state. So, your state would be something of the type $(s_k, [a_1, a_2, \ldots, a_{k-1}])$.
This kind of combinatorial problem is not what RL is really great at. RL is really good when the state and action together give a lot of information about the next state. Here it seems that, in your formulation, the next state is independent of the previous action.
Instead of seeing this as a RL problem, you might want to express this as sequences of actions with an associated reward, and look at it as a combinatorial optimization problem.

What OP is describing is, in fact, a combinatorial optimisation problem. Scheduling is a classic CO problem -- I think that it should be solvable using RL, OP would just have to be careful with how he defines an MDP. It is likely that vanilla DQN would be unable to solve his problem though, given all the variables. I think a good approach would be to view it as a POMDP and represent each machine as an agent.

Yeah, that's why I mentioned combinatorial optimization in the last line of my answer.

If by,

I can compute the reward given $(a_1, a_2, \dots, a_n)$

you simply mean that your game is deterministic, this is absolutely fine. I feel another answer had assumed you were implying your terminal reward is a matter of some sequence. RL does, however, struggle more greatly in games with indeterminable reward until the terminal state, however, it is perfectly normal, but a significant challenge.
In terms of implementation, simply record the reward at the end of each match, and perform a train step only after each terminal state, assigning this reward to each transition recorded in that game. Instead of updating your target network after a given number of steps, update it after some number of terminal states. I suggest 20 games as a starter for the frequency of updating your target network.


text:
Why does the output shape of a Dense layer contain a batch size?
I understand that the batch size is the number of examples you pass into the neural network (NN). If the batch size is 10, it means you feed the NN 10 examples at once.
Assuming I have an NN with a single Dense layer. This Dense layer of 20 units has an input shape (10, 3). This means that I am feeding the NN 10 examples at once, with every example being represented by 3 values. This Dense layer will have an output shape of (10, 20).
I understand that the 20 in the 2nd dimension comes from the number of units in the Dense layer. However, what does the 10 (Batch Size) in the first dimension mean? Does this mean that the NN learns 10 separate sets of weights (with each set of weights corresponding to one example, and one set of weights being a matrix of 60 values:3 features x 20 units)?

Note that, in general, implementation-related questions (including questions about software libraries) are off-topic here. Please, have a look at https://ai.stackexchange.com/help/on-topic for more info.

The Dense layers outputs 20 values per example. And since you have 10 examples in the batch the output is (10, 20) (one set of 20 values per example in the batch).
The nn doesn't learn 10 separate sets of weights. Each set of 20 values is computed with the same weight (and bias if you have any). So if say example 2 and 5 had the same input values, they'll always have the same output values.

Yes I understand where you are coming from. There will be 20 different values per example because its features (lets call them x1,x2 and x3) are different. Then, there will be 10 examples because of mini batch gradient descent -  the average of the gradients of all 10 examples will be taken into account for the weights update. Is this correct?

No. The gradients of the weights would be the sum (instead of average) of the gradients for each example.


text:
Have agents that "dream" been explored in Reinforcement Learning?
I was reading this article about the question "Why do we dream?" in which the author discusses dreams as a form of rehearsal for future threats, and presents it as an evolutive advantage. My question is whether this idea has been explored in the context of RL.
For example, in a competition between AIs on a shooter game, one could design an agent that, besides the behavior it has learned in a "normal" training, seeks for time in which is out of danger, to then use its computation time in the game to produce simulations that would further optimize its behavior. As the agent still needs to be somewhat aware of its environment, it could alternate between processing the environment and this kind of simulation. Note that this "in-game" simulation has an advantage with respect to the "pre-game" simulations used for training; the agent in the game experiences the behavior of the other agents, which could not have been predicted beforehand, and then simulates on top of these experiences, e.g. by slightly modifying them.
For more experienced folks, does this idea make sense? has something similar been explored?
I have absolutely no experience in the field, so I apologize if this question is poorly worded, dumb or obvious. I would appreciate suggestions on how to improve it if this is the case.

It's not clear to me what the restriction really is that you're putting on the "imagination" strategy. Is the restriction that it needs to be performed online while the agent learns and interacts with the environment?

It seems to me dreaming, and sleep, wouldn't necessary for an algorithm, as the function we humans do while sleeping could likely be accomplished in parallel.  The closest thing I can think of, offhand, is "goalless search", which is a form of algorithmic creativity.

Yes, the concept of dreaming or imagining has already been explored in reinforcement learning.
For example, have a look at Metacontrol for Adaptive Imagination-Based Optimization (2017) by Jessica B. Hamrick et al., which is a paper that I gave a talk/presentation on 1-2 years ago (though I don't remember well the details anymore).
There is also a blog post about the topic Agents that imagine and plan (2017) by DeepMind, which discusses two more recent papers and also mentions Hamrick's paper.
In 2018, another related and interesting paper was also presented at NIPS, i.e. World Models, by Ha and Schmidhuber.
If you search for "imagination/dreaming in reinforcement learning" on the web, you will find more papers and articles about this interesting topic.

Model-based RL is obviously the correct approach. Mainly because it lets you simulate the environment internally without having direct interaction.
And all successful RL algorithms essentially are model-based because nobody has done real-time RL and been successful.

Right, but I guess my question is about the idea of a model based RL in which agents keep information they see in "busy times" (a fight in the case of a shooter game) and then seek for idle times where they can better process that information, by adapting to it or even doing simulations over variations of it to improve their behavior.

There isn't a concept of "idle time" for RL agents that I know of. Deep RL use the same power regardless of the current world.

Is Q-learning model-based? What was used to achieve super-human performance on the Atari games?

If the RL agent is running in a simulator to learn I would call the global approach to the problem effectively model based even if not explicit since the model has already been constructed.

@FourierFlux Well, the simulator is the game itself in the case of Atari and the DQN case. RL algorithms need an environment. So, according to your definition, every RL algorithm is model-based only because there's an environment and the distinction between model-based and model-free is meaningless. Please, have a look at Neil's answer and my answer to know the difference between model-based and model-free.

The Atari games tick speed has been dramatically increased to allow  many games to be played effectively meaning it is running in a simulator. I have yet to see any "model free" agent according to your definition learn anything in real time.

Model based RL is defined as an algorithm where an agent uses learned dynamics of the system to help with learning. Q-learning does not do this (not does DQN) and is strictly model free.


text:
What are the variables that need to be saved and loaded, so that a DQN model starts where it left off?
TensorFlow allows users to save the weights and the model architecture, however, that will be insufficient unless the values of certain other variables are also stored. For instance, in DQN, if $\epsilon$ is not stored the model will start exploring from scratch and a new model will have to be trained.
What are the variables that need to be saved and loaded, so that a DQN model starts where it left off? Some pseudocode will be highly appreciated!
Here is my current model with code
## Slightly modified from the following repository - https://github.com/gsurma/cartpole

from __future__ import absolute_import, division, print_function, unicode_literals

import os
import random
import gym
import numpy as np
import tensorflow as tf

from collections import deque
from tensorflow.models import Sequential
from tensorflow.layers import Dense
from tensorflow.optimizers import Adam

ENV_NAME = "CartPole-v1"

GAMMA = 0.95
LEARNING_RATE = 0.001

MEMORY_SIZE = 1000000
BATCH_SIZE = 20

EXPLORATION_MAX = 1.0
EXPLORATION_MIN = 0.01
EXPLORATION_DECAY = 0.995

checkpoint_path = "training_1/cp.ckpt"

class DQNSolver:

    def __init__(self, observation_space, action_space):
        self.exploration_rate = EXPLORATION_MAX

        self.action_space = action_space
        self.memory = deque(maxlen=MEMORY_SIZE)

        self.model = Sequential()
        self.model.add(Dense(24, input_shape=(observation_space,), activation="relu"))
        self.model.add(Dense(24, activation="relu"))
        self.model.add(Dense(self.action_space, activation="linear"))
        self.model.compile(loss="mse", optimizer=Adam(lr=LEARNING_RATE))

    def remember(self, state, action, reward, next_state, done):
        self.memory.append((state, action, reward, next_state, done))

    def act(self, state):
        if np.random.rand() < self.exploration_rate:
            return random.randrange(self.action_space)
        q_values = self.model.predict(state)
        return np.argmax(q_values[0])

    def experience_replay(self):
        if len(self.memory) < BATCH_SIZE:
            return
        batch = random.sample(self.memory, BATCH_SIZE)
        for state, action, reward, state_next, terminal in batch:
            q_update = reward
            if not terminal:
                q_update = (reward + GAMMA * np.amax(self.model.predict(state_next)[0]))
            q_values = self.model.predict(state)
            q_values[0][action] = q_update
            self.model.fit(state, q_values, verbose=0)
        self.exploration_rate *= EXPLORATION_DECAY
        self.exploration_rate = max(EXPLORATION_MIN, self.exploration_rate)

def cartpole():
    env = gym.make(ENV_NAME)
    #score_logger = ScoreLogger(ENV_NAME)
    observation_space = env.observation_space.shape[0]
    action_space = env.action_space.n
    dqn_solver = DQNSolver(observation_space, action_space)
    checkpoint = tf.train.get_checkpoint_state(os.getcwd()+"/saved_networks")
    print('checkpoint:', checkpoint)
    if checkpoint and checkpoint.model_checkpoint_path:
        dqn_solver.model = keras.models.load_model('cartpole.h5')
        dqn_solver.model = model.load_weights('cartpole_weights.h5')

    run = 0
    i = 0
    while i<5:
        i = i + 1
        #total = 0
        run += 1
        state = env.reset()
        state = np.reshape(state, [1, observation_space])
        step = 0
        while True:
            step += 1
            #env.render()
            action = dqn_solver.act(state)
            state_next, reward, terminal, info = env.step(action)
            #total += reward
            reward = reward if not terminal else -reward
            state_next = np.reshape(state_next, [1, observation_space])
            dqn_solver.remember(state, action, reward, state_next, terminal)
            state = state_next
            dqn_solver.model.save('cartpole.h5')
            dqn_solver.model.save_weights('cartpole_weights.h5')
            if terminal:
                print("Run: " + str(run) + ", exploration: " + str(dqn_solver.exploration_rate) + ", score: " + str(step))
                #score_logger.add_score(step, run)
                break
            dqn_solver.experience_replay()

if __name__ == "__main__":
    cartpole()

To answer your question, we need to know more details about your problem, learning algorithm, model, etc. There are many RL algorithms.

@nbro Thank you for your comment. I have included some code and the name of my model. Let me know if you have more questions.

That's a lot better. Thanks! Just a clarification, you're not necessarily looking for code (although this is appreciated), but you mainly want to understand which variables are required to restarting training, right?

@nbro - Exactly. This is just some sample code that I got and modified from a source. Once I understand the variables/parameters that need to be saved, I will implement it on my research code (which mainly follows the DQN algorithm)

Typically you would need to save the network weights, hyper-parameters and the replay buffer if you wanted to stop training and then come back at a later date and carry on training. Usually, I do this by writing it all as a class in Python (the agent, the memory buffer, hyper-parameters etc.) and saving the final object with Pickle.
Looking at your code, the only thing I would personally have done different would be to define the model outside of the class and have the class take as input a network; however I usually use PyTorch as opposed to Keras/Tensorflow so I'm not sure which method works better.
As per OP's request in the comments, here is a snippet of code I used for Car-pool.
class DQN:

def __init__(self, observation_space, action_space):
    self.exploration_rate = epsilon_max
    self.observation_space = observation_space
    self.batch_size = batch_size
    self.gamma = gamma

    self.action_space = action_space

    self.memory = deque(maxlen=max_memory)

    self.model = Net()
    self.loss_fn = nn.MSELoss()
    self.optimizer = optim.Adam(self.model.parameters(), lr=0.0001)

def remember(self, state, action, reward, next_state, done):
    self.memory.append((state, action, reward, next_state, done))

def act(self, state):
    self.model.eval()
    state = torch.from_numpy(state).type(torch.FloatTensor)
    self.exploration_rate *= exploration_decay
    self.exploration_rate = max(epsilon_min, self.exploration_rate)
    if np.random.uniform() < self.exploration_rate:
        return np.random.randint(0, self.action_space)
    q_values = self.model(state)
    action = torch.argmax(q_values, dim=1)
    return int(action)

def experience_replay(self):
    if len(self.memory) < batch_size:
        return

    self.optimizer.zero_grad()
    states,actions,rewards,next_states,dones = self.get_batch()
    states = torch.FloatTensor(states).reshape((self.batch_size,4))
    next_states = torch.FloatTensor(next_states).reshape((self.batch_size,4))
    rewards = torch.FloatTensor(rewards).reshape((self.batch_size,1))
    dones = torch.FloatTensor(dones).reshape((self.batch_size,1))

    # get the q update ready
    # first take max and set up target
    max_vals,argmax = torch.max(self.model(next_states),axis=1)
    q_target = rewards + self.gamma * max_vals.reshape((self.batch_size,1)) * (1-dones)

    q_values = self.model(states)
    for _ in range(self.batch_size):
        q_values[_][actions[_]] = q_target[_][0]
    input = self.model(states)
    q_values = q_values.detach()
    loss = self.loss_fn(input, q_values)
    loss.backward()
    self.optimizer.step()

def get_batch(self):
    batch = random.sample(self.memory, self.batch_size)

    states = []
    actions = []
    rewards = []
    next_states = []
    dones = []
    for state,action,reward,next_state,done in batch:
        states.append(state)
        actions.append(action)
        rewards.append(reward)
        next_states.append(next_state)
        dones.append(done)
    return states,actions,rewards,next_states,dones

def tensor_max(self, ten):
    ten = ten.numpy()
    ten = np.amax(ten, 1).reshape(1, 1)
    ten = torch.from_numpy(ten).type(torch.FloatTensor)
    return ten

Could you please post a sample of your code. That way, I can get an idea on how the pseudocode works.

I've added this now


text:
Why doesn't value iteration use $\pi(a \mid s)$ while policy evaluation does?
I was looking at the Bellman equation, and I noticed a difference between the equations used in policy evaluation and value iteration.
In policy evaluation, there was the presence of $\pi(a \mid s)$, which indicates the probability of choosing action $a$ given $s$, under policy $\pi$. But this probability seemed to be omitted in the value iteration formula. What might be the reason? Maybe an omission?

Do you really mean "policy evaluation", or are you asking about "policy iteration"? "Policy evaluation" is also the name of a phase within policy iteration. However, value iteration and policy iteration are both optimal control solvers, so it would be more usual to compare those. Also policy evaluation in general is not a single algorithm, but a whole family of them.

Iterative policy evaluation , where we iterate many times to find the value of a state wheelie following a policy, while the value iteration deals with the optimal action set, my question is the absence of Pi(a|s) in value iteration

You appear to comparing the value table update steps in policy iteration and value iteration, which are both derived from Bellman equations.
Policy iteration
In policy iteration, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$, but can also be of the form $\pi(a|s): \mathcal{A} \times  \mathcal{S} \rightarrow \mathbb{R} = Pr\{A_t = a |S_t =s\}$. Policy iteration then alternately evaluates then improves that policy, with the improvement always being to act greedily with respect to expected return. Because the policy function can be arbitrary, and also the current value estimates during evaluation might not relate to it directly, the function $\pi(s)$ or $\pi(a|s)$ needs to be shown.
Typically with policy iteration, you will see this update rule:
$$V(s) \leftarrow \sum_{r,s'} p(r,s'|s,\pi(s))(r + \gamma V(s'))$$
The above rule is for evaluating a deterministic policy, and is probably more commonly used. There is no real benefit in policy iteration to working with stochastic policies.
For completeness, the update rule for an arbitrary stochastic policy is:
$$V(s) \leftarrow \sum_a \pi(a|s) \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$
Value iteration
In value iteration, the current policy to evaluate is to always take the greedy action with respect to the current evaluations. As such, it does not need to be explicity written, because it can be derived from the value function, and so can the terms in the Bellman equation (specifically the Bellman equation for the optimal value function is used here, which usually does not refer the policy). What you would typically write for the update step is:
$$V(s) \leftarrow \text{max}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$
However, you can write this out as if there was a policy table:
$$\pi(s) \leftarrow \text{argmax}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$
$$a \leftarrow \pi(s)$$
$$V(s) \leftarrow \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$
This is not the usual way to implement it though, because of the extra maximum value search required to identify the action. In simple value iteration it does not matter what the interim action choices and policies actually are, and you can always derive them from the value function if you want to know.
Other value-based methods
You will find other algorithms that drive the current policy direct from a value function, and when they are described in pseudo-code they might not have an explicit policy function. It is still there, only the Bellman update is easily calculated directly from the value function, so the policy is not shown in the update step. Descriptions of SARSA and Q-learning are often like that.


text:
Based on the Turing test, what would be the criteria for an agent to be considered smart?
Based on the Turing test, what would be the criteria for an agent to be considered smart?

If an artificial agent (AA) passes the (standard) Turing test (i.e. where you have to imitate a human that speaks), then, on average, the AA should be able to imitate any human in any situation that mainly requires the conversation abilities and common-sense knowledge of a human, without being ever recognized as an AA.
For example, if you want to talk about football, you don't expect the AA only to say "I don't know" or to clearly avoid a topic (e.g. by redirecting you to a search engine) when it doesn't know something (although some humans behave in this way), but you expect it to have common-sense knowledge, such as that Messi, Cristiano Ronaldo, Pelé, Maradona, etc., are among the best players of all time, and this should be precious information that the AA should have in any case, even if it doesn't know much about football.
You also expect it to be emotional and have a personality, given that humans are emotional and have personalities. So, in the example above, maybe the AA could say that Maradona is its favorite player, and then it could explain why in an emotional way (e.g. by changing the tone of the voice).
The AA should also be able to keep track of (almost) everything you and it said, and it should be able to contextualize very well, as humans do. Some personal assistants already take context into account, but they don't do this very well or just do it to a little extent.
The AA should also be able to reason given the current situation. For example, if you explain something to the AA, you expect it to infer or predict something based on the information it has acquired and the common-sense knowledge.
Moreover, when you speak or write to the AA, you don't expect it to regularly hear badly or not understand what you say or ask (and ask you to repeat), but you expect it to understand well what you say almost always, provided you don't talk or write trash. You also don't expect big delays and you expect the AA to at least say something while it searches for a more appropriate answer, although not all humans behave in this way, but I think that interjections or words such as "hm", "well", "let me think...", etc., will be very important to make the AA look or sound like a human. In general, the AA should be as interactive as a human.
These are some traits that the AA absolutely needs to have in order to pass the Turing test (and be considered intelligent according to that test), but there are probably many others.


text:
How does the RL agent understand motion if it gets only one image as input?
Basic deep reinforcement learning methods use as input an image for the current state, do some convolutions on that image, apply some reinforcement learning algorithm, and it is solved.
Let us take the game Breakout or Pong as an example. What I do not understand is: how does the agent understand when an object is moving towards it or away from it? I believe that the action it chooses must be different in these two scenarios, and, from a single image as input, there is no notion of motion.

In the article Playing Atari with Deep Reinforcement Learning, Mnih et al, 2013, which was a major outbreak in Deep Reinforcement learning (especially in Deep Q learning), they don't feed only the last image to the network. They stack the 4 last images :

For the experiments in this paper, the function φ from algorithm 1
applies this preprocessing to the last 4 frames of a history and stacks
them to produce the input to the Q-function

So they add the motion through sequentiality. From various articles and own coding experiences, this seems to me to be the main common approach. I don't know if other techniques have been implemented.
One thing we could imagine would be to compute the Cross-correlation between a previous frame and the last one, and then feed the cross correlation product to the net.
Another idea would be to train previously a CNN to extract motion features from a sequence of frames, and feed these extracted features to your net. This article (Performing Particle Image Velocimetry using Artificial Neural Networks: a proof-of-concept), Rabault et al, 2017 is an example of a CNN to extract motion features.

Another alternative is to use a RNN and feed it the frames one at a time. It's not what the original Atari DQN did, but has been tried successfully: http://cs229.stanford.edu/proj2016/report/ChenYingLaird-DeepQLearningWithRecurrentNeuralNetwords-report.pdf

Obviously, how could I not mention it ? thank you !


text:
Why is the optimal policy for an infinite horizon MDP deterministic?
Could someone please help me gain some intuition as to why the optimal policy for a Markov Decision Process in the infinite horizon case (agent acts forever) is deterministic?

Maybe you should provide the quote, or the link to the article (or a reference to a book) that states it, just to contextualise.

Suppose you learned your action-value function perfectly. Recall that the action-value function measures the expected return after taking a given action in a given state. Now, the goal when solving an MDP is to find a policy that maximizes expected returns. Suppose you're in state $s$. According to your action-value function, let's say actions $a$ maximizes the expected return. So, according to the goal of solving an MDP, the only action you would ever take from state $s$ is $a$. In other words $\pi(a'\mid s) = \mathbf{1}[a'=a]$, which is a deterministic policy.
Now, you might argue that your action-value function will never be perfect. However, this just means you need more exploration, which can manifest itself as stochasticity in the policy. However, in the limit of infinite data, the optimal policy will be deterministic since the action-value function will have converged to the optimum.

The premise of this question is somewhat misleading. There is a deterministic optimal policy for a MDP, but this does not mean a stochastic optimal policy never exists. Talking about the optimal policy can be misleading, as there may be many different optimal policies.
For example, certainly we could imagine an MDP where $Q^*(s,a_0) = Q^*(s,a_1)$ for two different actions $a_1$ and $a_2$ that both maximize the optimal action-value function $Q^*$ at some state $s$. Then a stochastic policy choosing randomly between $a_1$ and $a_2$ at $s$ is optimal, but so is a deterministic policy that always picks $a_1$ at $s$, and a deterministic policy that always picks $a_2$ at $s$.

Here you have an answer that goes in a similar direction of what you say in your answer.


text:
Why does TD Learning require Markovian domains?
One of my friends and I were discussing the differences between Dynamic Programming, Monte-Carlo, and Temporal Difference (TD) Learning as policy evaluation methods - and we agreed on the fact that Dynamic Programming requires the Markov assumption while Monte-Carlo policy evaluation does not.
However, he also pointed out that Temporal Difference Learning cannot handle non-Markovian domains, i.e. it depends on the Markov assumption. Why is it so?
The way I understand it, the TD learning update is, in essence, the same as the Monte-Carlo update, except for the fact that the return instead of being calculated using the entire trajectory, is bootstrapped from the previous estimate of the value function, i.e. we can update the value as soon as we encounter a $(s,a,r,s')$ tuple, we don't have to wait for the episode (if finite) to terminate.
Where is the Markov assumption being used here, i.e the future is independent of the past given the present?

The Markov assumption is used when deriving the Bellman equation for state values:
$$v(s) = \sum_a \pi(a|s)\sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$
One requirement for this equation to hold is that $p(r,s'|s,a)$ is consistent. The current state $s$ is a key argument of that function. There is no adjustment for history of previous states, actions or rewards. This is the same as requiring the Markov trait for state, i.e. that $s$ holds all information necessary to predict outcome probabilities of the next step.
The one step TD target that is sampled in basic TD learning is simply the inner part of this:
$$G_{t:t+1} = R_{t+1} + \gamma \hat{v}(S_{t+1})$$
which when sampled is equal to $v(s)$ in expectation *, when $S_t = s$. That is, when you measure a single instance of the TD target and use it to update a value function, you implicitly assume that the values or $r_{t+1}$ and $s_{t+1}$ that you observed occur with probabilities determined by $\pi(a|s)$ and $p(r,s'|s,a)$ as shown by the Bellman equation.
So the theory behind TD learning uses the Markov assumption, otherwise the sampled TD targets would be incorrect.
In practice you can get away with slightly non-Markov environments - most measurements of state for machinery are approximations that ignore details at some level, for instance, and TD learning can solve optimal control in many robotics environments. However, Monte Carlo methods are more robust against state representations that are not fully Markov.

* Technically this sample is biased because $\hat{v}(S_{t+1})$ is not correct when learning starts. The bias reduces over time and multiple updates. So the expected value during learning is approximately the same as the true value as shown by the Bellman equation.

If we're working in the domain of deterministic policies, we don't have to worry about the expectation of the TD target, right? I suppose in that case the expectation of the TD target would equal itself. Please correct me if I'm wrong!

If the statement mentioned in the comment above is right, would we still require the Markov assumption for TD learning in the case of deterministic policies?

@cogito_ai No, both the first statement is wrong, and your suggestsed consequence in the second statement. For the first statement, the environment would also need to be deterministic before a single sample of the TD target was also guaranteed equal to the expected TD target. To answer the second comment, even in that case you need the Markov assumption - if the Markov asumption is broken, then one or both $s'$ or $r$ could be arbitrarily different when starting from the same state, so any TD target would be wrong, even one generated over many samples.

A beautiful answer! I think the critical intuition here is this: While $Q$-learning and other TD methods are model-free, they still leverage Markovity through the consistence of the Bellman equation (which means we can sample our TD targets properly)!


text:
What are some (deep) reinforcement learning books for beginners?
What are some books on reinforcement learning (RL) and deep RL for beginners?
I'm looking for something as friendly as the head first series, that breaks down every single thing.

Reinforcement Learning: An Introduction by Richard Sutton and Andrew Barto is undoubtedly one of the best books, to begin with. Despite its age, the book is still the canonical introduction to reinforcement learning. It does require some patience, but I think it's very approachable and rigorous at the same time!

If you are looking for a book that is more beginner friendly than the Sutton and Barto book (which you should of course check out also), try out:
Deep Reinforcement Learning Hands On


text:
When do SARSA and Q-Learning converge to optimal Q values?
Here's another interesting multiple-choice question that puzzles me a bit.

In tabular MDPs, if using a decision policy that visits all states an infinite number of times, and in each state, randomly selects an action, then:

Q-learning will converge to the optimal Q-values
SARSA will converge to the optimal Q-values
Q-learning is learning off-policy
SARSA is learning off-policy

My thoughts, and question: Since the actions are being sampled randomly from the action space, learning definitely seems to be off-policy (correct me if I'm wrong, please!). So that rules 3. and 4. as incorrect. Coming to the first two options, I'm not quite sure whether Q-learning and/or SARSA would converge in this case. All that I'm able to understand from the question is that the agent explores more than it exploits, since it visits all states (an infinite number of times) and also takes random actions (and not the best action!). How can this piece of information help me deduce if either process converges to the optimal Q-values or not?

Source: Slide 2/55

The true answers are 1 and 3.
1 is true because the required conditions for tabular Q-learning to converge is that each state action pair will be visited infinitely often, and Q-learning learns directly about the greedy policy, $\pi(a|s) := \arg \max_a Q_\pi(s,a)$,  and because Q-learning converges to the optimal Q-value function we know that the policy will be optimal (because the optimal policy is the greedy policy wrt the optimal Q-function).
3 is true because Q-learning is by definition an off-policy algorithm, because we learn about the greedy policy whilst following some arbitrary policy.
2 is false because SARSA is on-policy, so it will be learning the Q-function under the random policy.
4 is false because SARSA is strictly on-policy, for reasons analogous to why Q-learning is off-policy.

So a completely random policy counts as a policy too? Isn't that as good as not having a policy and sampling from the action space itself?

That’s exactly what the random policy does, it picks from all viable actions in the given state with equal probability. It’s good for guaranteeing exploration in off-policy algorithms.

Great, thanks! Also, when would SARSA converge to the optimal Q values? From what I remember, it should happen when (i) all state-action pairs are visited infinitely often (ii) the policy converges to the greedy policy. Could you confirm/elaborate more on this?

Yes, that is correct. In practice you would learn about an $\epsilon$-greedy policy which is not technically optimal but very close to it.


text:
Why is the reward in reinforcement learning always a scalar?
I'm reading Reinforcement Learning by Sutton & Barto, and in section 3.2 they state that the reward in a Markov decision process is always a scalar real number. At the same time, I've heard about the problem of assigning credit to an action for a reward. Wouldn't a vector reward make it easier for an agent to understand the effect of an action? Specifically, a vector in which different components represent different aspects of the reward. For example, an agent driving a car may have one reward component for driving smoothly and one for staying in the lane (and these are independent of each other).

In our self-driving car example, you are also assuming rewards as a scalar quantity implicitly. If the reward is a vector then the value function is also a vector (I'm not saying value function can't be a vector). Rich Sutton off policy function approximation, you may find something related to your question there.

See this and this questions too.

If you have multiple types of rewards (say, R1 and R2), then it is no longer clear what would be the optimal way to act: it can happen that one way of acting would maximize R1 and another way would maximize R2.  Therefore, optimal policies, value functions, etc., would all be undefined.  Of course, you could say that you want to maximize, for example, R1+R2, or 2R1+R2, etc.  But in that case, you're back at a scalar number again.
It can still be helpful for other purposes to split up the reward into multiple components as you suggest, e.g., in a setup where you need to learn to predict these rewards.  But for the purpose of determining optimal actions, you need to boil it down into a single scalar.

Rather than the survey by Liu et al. recommended above, I'd suggest you read the following survey paper for an overview of MORL (disclaimer - I was a co-author on this, but I genuinely think it is a much more useful introduction to this area)

Roijers, D. M., Vamplew, P., Whiteson, S., & Dazeley, R. (2013). A survey of multi-objective sequential decision-making. Journal of Artificial Intelligence Research, 48, 67-113.

Liu et al's survey, in my opinion, doesn't do much more than list and briefly describe the MORL algorithms which existed at that point. There's no deeper analysis of the field. The original version of their paper was also retracted due to blatant plagiarism of several other authors, including myself as can be confirmed here.
Our survey provides arguments for the need for multiobjective methods by describing 3 scenarios where agents using single-objective RL may be unable to provide a satisfactory solution that matches the needs of the user. Briefly, these are

the unknown weights scenario where the required trade-off between the objectives isn't known in advance, and so to be effective the agent must learn multiple policies corresponding to different trade-offs and then at run-time select the one which matches the current preferences (e.g. this can arise when the objectives correspond to different costs which vary in relative price over time);

the decision support scenario where scalarization of a reward vector is not viable (for example, in the case of subjective preferences, which defy explicit quantification), so the agent needs to learn a set of policies, and then present these to a user who will select their preferred option, and

the known weights scenario where the desired trade-off between objectives is known, but its nature is such that the returns are non-additive (i.e. if the user's utility function is non-linear), and therefore standard single-objective methods based on the Bellman equation can't be directly applied.

We propose a taxonomy of MORL problems in terms of the number of policies they require (single or multi-policy), the form of utility/scalarization function supported (linear or non-linear), and whether deterministic or stochastic policies are allowed, and relate this to the nature of the set of solutions which the MO algorithm needs to output. This taxonomy is then used to categorize existing MO planning and MORL methods.
One final important contribution is identifying the distinction between maximising Expected Scalarised Return (ESR) or Scalarised Expected Return (SER). The former is appropriate in cases where we are concerned about the results within each individual episode (for example, when treating a patient - that patient will only care about their own individual experience), while SER is appropriate if we care about the average return over multiple episodes. This has turned out to be a much more important issue than I anticipated at the time of the survey, and Diederik Roijers and his colleagues have examined it more closely since then (e.g., Multi-objective Reinforcement Learning
for the Expected Utility of the Return)

I didn't know the Liu paper was plagiarized. I think I will modify my answer accordingly. From now on I'll refer to your work instead in similar questions.

Markov decision problems are usually defined with a reward function $r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, and in these cases the rewards are expected to be scalar real values. This makes reinforcement learning (RL) easier, for example when defining a policy $\pi(s,a)=\arg\max_a Q(s,a)$, it is clear what is the maximum of the Q-factors in state $s$.
As you might have also realized, in practice however, problems often have multiple objectives that we wish to optimize at the same time. This is called multiobjective optimization and the related RL field is multiobjective reinforcement learning (MORL). If you have access to the paper Liu, Xu, Hu: Multiobjective Reinforcement Learning: A Comprehensive Overview (2015) you might be interested in reading it. (Edit: as Peter noted in his answer, the original version of this paper was found to be a plagiarism of various other works. Please refer to his answer for better resources.)
The above-mentioned paper categorizes methods for dealing with multiple rewards into two categories:

single objective strategy, where multiple rewards are somehow aggregated into one scalar value. This can be done by giving weights to rewards, making some of the objectives a constraint and optimize the others, ranking the objectives and optimize them in order etc. (Note: in my experience, weighted sum of rewards is not a good objective as it might combine two completely unrelated objectives in a very forced way.)
Pareto strategy, where the goal is to find Pareto-optimal strategies or a Pareto front. In this case we keep the rewards a vector and may compute a composite Q-factor, eg.: $\bar{Q}(s,a)=[Q_1(s,a), \ldots, Q_N(s,a)]$ and may have to modify the $\arg\max_a$ function to select the maximum in a Pareto sense.

Finally, I believe it is important to remind you that all these methods really depend on the use-case and on what you really want to achieve and that there is no one solution that fits all. Even after finding an appropriate method you might find yourself spending time tweaking hyper-parameters just so that your RL agent would do what you would like it to do in one specific scenario and do something else in a slightly different scenario. (Eg. taking over on a highway vs. taking over on a country road).


text:
How can Transformers handle arbitrary length input?
The transformer, introduced in the paper Attention Is All You Need, is a popular new neural network architecture that is commonly viewed as an alternative to recurrent neural networks, like LSTMs and GRUs.
However, having gone through the paper, as well as several online explanations, I still have trouble wrapping my head around how they work. How can a non-recurrent structure be able to deal with inputs of arbitrary length?

Transformer cannot handle arbitrary length. You must have misunderstood something. For example, BERT is a transformer architecture (encoder only), and it has a maximum length of 512 tokens. A very useful blog for understanding transformers is The Illustrated Transformer

Actually, there is usually an upper bound for inputs of transformers, due to the inability of handling long-sequence. Usually, the value is set as 512 or 1024 at current stage.
However, if you are asking handling the various input size, adding padding token such as [PAD] in BERT model is a common solution. The position of [PAD] token could be masked in self-attention, therefore, causes no influence. Let's say we use a transformer model with 512 limit of sequence length, then we pass a input sequence of 103 tokens. We padded it to 512 tokens. In the attention layer, positions from 104 to 512 are all masked, that is, they are not attending or being attended.

Thanks for the answer. Could you clarify one more point: What do you do when the input sequence is longer than 512/1024? Is a transformer simply inappropriate in that case?

Yes, it's the limitation of BERT. Actually, there are tons of researches trying to solve this issue such as SpanBERT, Longformer, Reformer, Sparse transformer, etc. We could categorize them into two categories roughly. One is embracing the length limitation and divide the sequence into sections, while the others assume the attention could be sparsified.

@tsu is that limitation still relevant to GPT 4?

@Weier After ~4 years, the limitation has been pushed up to 128K by OpenAI and 100M claimed by Google. IIUC, the main architecture of LLMs is still multi-head attention based transformer although a variety of researches on sparse and efficient transformers are proposed. I would say the main improvement on pushing the sequecne limitation might be attributed to quatization and the optimization on GPUs.

The accepted answer is wonderful; this answer provides an alternative approach for dealing with variable length inputs.  More specifically, what might be done when the input is longer than the maximum sequence length supported by the transformer you have built.
We have found it useful to wrap our transformer in a class that allows us to programmatically use a sliding window across inputs that are longer than the supported transformer input length.  If the input is less than or equal to the supported length, it is simply processed.  If it is longer, we iteratively slide across the data, passing each window into the transformer and then aggregate the outputs.
When we take this approach, we do not typically slide the window one element (word embedding) at a time, but instead use a longer stride, usually two to five embeddings at a time.  We have been intending to do some research into evaluating whether using multiple strides improves overall performance, but have not yet done so because of the prohibitive computational performance characteristics of using multiple strides.  Using a sliding window already significantly impacts the time to predict since we are running the predictions multiple times.
If this approach seems useful, a simple insight is that you need not pass the inputs in sequentially; instead, we typically build a batch with all of the windows and pass them through all at once.
Of course, there is a downside to this approach that might make you decide to choose to split the windows based on sentences or paragraphs.  otherwise, your positional encoding will end up being "off" since you are sliding across the inputs.


text:
How can we prevent AGI from doing drugs?
I recently read some introductions to AI alignment, AIXI and decision theory things.
As far as I understood, one of the main problems in AI alignment is how to define a utility function well, not causing something like the paperclip apocalypse.
Then a question comes to my mind that whatever the utility function would be, we need a computer to compute the utility and reward, so that there is no way to prevent AGI from seeking it to manipulate the utility function to always give the maximum reward.
Just like we humans know that we can give happiness to ourselves in chemical ways and some people actually do so.
Is there any way to prevent this from happening? Not just protecting the utility calculator physically from AGI (How can we sure it works forever?), but preventing AGI from thinking of it?

This is known as reward hacking in the literature; see, e.g., https://medium.com/@deepmindsafetyresearch/designing-agent-incentives-to-avoid-reward-tampering-4380c1bb6cd for discussion and further links.

This is the right answer, as far as I'm concerned, but rather than providing just a link to another article, please, try to summarise the main points from that article here, so that your answer is more self-contained.

You make a lot of assumptions about AGI, namely that 'we need a computer to compute the utility and reward AGI'. It not clear to me that (1) we can achieve AGI, (2) AGI will be on a computer as we know it and (3) AGI will work with a utility / reward function as we know them.
One thing I am sure though is that ML is known for "cheating" (see for exemple). Avoiding such cheating is part of the building process. So, when you assume that we can achieve AGI, it means that you assume we can build an AGI that do not "cheat". Thus, the answer is mostly contained in your assumptions.
Whether we are able to build an AGI, what "cheating" we would have to overcome to do so and how we will be able to do so is mostly undetermined.


text:
Why is depth-first search an artificial intelligence algorithm?
I'm new to the artificial intelligence field. In our first chapters, there is one topic called "problem-solving by searching". After searching for it on the internet, I found the depth-first search algorithm. The algorithm is easy to understand, but no one explains why this algorithm is included in the artificial intelligence study.
Where do we use it? What makes it an artificial intelligence algorithm? Is every search algorithm is an AI algorithm?

This question is very related to https://ai.stackexchange.com/q/2514/2444 and https://ai.stackexchange.com/q/1877/2444. If you think your question is a duplicate of one of these, let me know and I will mark your question as a duplicate.

I suggest reading the original IDA* paper, which connects DFS to IDA*.

This is a fundamentally a philosophical question. What makes AI AI? But first things, why would DFS be considered an AI algorithm?
In its most basic form, DFS is a very general algorithm that is applied to wildly different categories of problems: topological sorting, finding all the connected components in a graph, etc. It may be also used for searching. For instance, you could use DFS for finding a path in a 2D maze (although not necessarily the shortest one). Or you could use it to navigate through more abstract state spaces (e.g. between configuration of chess or in the towers of Hanoi). And this is where the connection to AI arises. DFS can be used on its own for navigating such spaces, or as a basic subroutine for more complex algorithms. I believe that in the book Artificial Intelligence: A Modern Approach (which you may be reading at the moment) they introduce DFS and Breadth-First Search this way, as a first milestone before reaching more complex algorithms like A*.
Now, you may be wondering why such search algorithms should be considered AI. Here, I'm speculating, but maybe the source of the confusion comes from the fact that DFS does not learn anything. This is a common misconception among new AI practitioners. Not every AI technique has to revolve around learning. In other words, AI != Machine Learning. ML is one of the many subfields within AI. In fact, early AI (around the 50s-60s) was more about logic reasoning than it was about learning.
AI is about making an artificial system behave "intelligently" in a given setting, whatever it takes to reach that intelligent behavior. If what it takes is applying well-known algorithms from computer science like DFS, then so be it. Now, what is it that intelligent means? This is where we enter more philosophical grounds. My interpretation is that "intelligence" is a broad term to define the large set of techniques that we use to approach the immense complexity that reality and certain puzzle-like problems have to offer. Often, "intelligent behavior" revolves around heuristics and proxy methods away from the perfect, provable algorithms that work elsewhere in computer science. While certain algorithms (like DFS or A*) may be proven to give optimal answers if infinitely many resources can be devoted to the task at hand, only in sufficiently constrained settings would such techniques be affordable. Fortunately, we can make them work in many situations (like A* for chess or for robot navigation, or Monte Carlo Tree Search for Go), but only if reasonable assumptions and constraints over the state space are imposed. For all the rest is where learning techniques (like Markov Random Fields for image segmentation, or Neural Nets paired with Reinforcement Learning for situated agents) may come handy.
Funny enough, even if intelligence is often regarded as a good thing, my interpretation can be summed up as imperfect modes of behavior to address immensely complex problems for which no known perfect solution exists (with rare exceptions in sufficiently bounded problems). If we had a huge table that, for each chess position, gives the best possible move you can make, and put that table inside a program, would this program be intelligent? Maybe you'd think so, but in any case it seems more arguable than a program that makes real-time reasoning and spits a decision after some reasonable time, even if it's not the best one. Similarly, do you consider sorting algorithms intelligent? Again, the answer is arguable, but the fact is that algorithms exist with optimal time and memory complexities, we know that we can't do better than what those algorithms do, and we do not have to resort to any heuristic or any learning to do better (disclaimer: I haven't actually checked if there's some madman out in the wild applying learning to solve sorting with better average times).

Good answer.  I speak and teach in the ML and AI fields.  I find that, generally, people who are not working in this field or who are new to the field have a misconception as to what ML and AI actually are and how they work.  They imagine what they read in scifi books and see in movies.  It is, however, effectively the application of algorithms to mathematical models to perform transformations in high dimensional vector space.  In another sense, it is just applied computational statistics and probability theory.  Since DFS fits in terms of an AI search approach.

@DavidHoelzer Exactly. Another pervasive trend that I've found with the rise of Deep Learning is the even narrower belief that if something does not have a neural net inside, then it cannot possibly be AI.

"It's just a linear model, that's not AI" is something I keep running into. Basic machine learning is taught in high school, but nobody seems to realise because it's written on a whiteboard instead of displayed in neon blue on a touchscreen.

Regarding sorting with ML: Isn't it the rule 34 of computer science? For every problem, there is a ML solution.

@jpa Why yes.

DFS on its own would not typically be considered AI imo.  It is a standard computer science deterministic algorithm.  Instead an intelligent agent might use DFS to inform its decision making as part of an AI package.

Any reason why you highlight that DFS is deterministic? Would you say that there is a stronger connection between AI and random algorithms than between elsewhere in computer science and random algorithms? Also, I would say that determinism isn't a strong feature of DFS. After all, you could visit the successor nodes in a random order, and the algorithm would be essentially the same. Other than that, I agree that DFS doesn't belong to AI anymore that it belongs to CS. However, it is worth it to study it in introductory AI courses as a basic building block.

AI and ML have strong components of probability. There may not be absolutely correct "answers" for the objective functions they seek to solve. Instead statistical concepts such as maximum likelihood estimation and bayesian analysis come into play. DFS does not involve randomization.


text:
When using experience replay in reinforcement learning, which state is used for training?
I'm slightly confused about the experience replay process. I understand why we use batch processing in reinforcement learning, and from my understanding, a batch of states is input into the neural network model.
Suppose there are 2 valid moves in the action space (UP or DOWN)
Suppose the batch size is 5, and the 5 states are this:
$$[s_1, s_2, s_3, s_4, s_5]$$
We put this batch into the neural network model and output Q values. Then we put $[s_1', s_2', s_3', s_4', s_5']$ into a target network.
What I'm confused about is this:
Each state in $[s_1, s_2, s_3, s_4, s_5]$ is different.
Are we computing Q values for UP and DOWN for ALL 5 states after they go through the neural network?
For example, $$[Q_{s_1}(\text{UP}), Q_{s_1}(\text{DOWN})],
\\ [Q_{s_2} (\text{UP}), Q_{s_2}(\text{DOWN})], \\
[Q_{s_3}(\text{UP}), Q_{s_3}(\text{DOWN})], \\
[Q_{s_4}(\text{UP}), Q_{s_4}(\text{DOWN})], \\
[Q_{s_5}(\text{UP}), Q_{s_5}(\text{DOWN})]$$

The way the states are used is as follows:
Typically your $Q$-network will state a state as input and output scores over the action space. I.e. $Q : \mathcal{S} \rightarrow \mathbb{R}^{|\mathcal{A}|}$. So, in your replay buffer you should store $s_t, a_t, r_{t+1}, s_{t+1}, \mbox{done}$ (note that done just represents where the episode ended on this transition and I add for completeness.
Now, when you are doing your batch updates you sample uniformly at random from this replay buffer. This means you get $B$ tuples of $s_t, a_t, r_{t+1}, s_{t+1}, \mbox{done}$. Now, I will assume $B=1$ as it is easier to explain and the extension to $B > 1$ should be easy to see.
For our state-action tuple $s_t, a_t$ we want to shift what the network predicts for this pair to be closer to $r_{t+1} + \gamma \arg\max_a Q(s,a)$. However, our neural network only takes the state as input, and outputs a vector of scores for each action. That means we want to shift the output of our network for the state $s_t$ towards the target I just mentioned, but only for the action $a_t$ that we took. To do this we just calculate the target, i.e. we calculate $r_{t+1} + \gamma \arg\max_a Q(s,a)$, and then we do gradient ascent like we would a normal neural network where the target vector is the same as the predicted vector everywhere except the $a_t$th element, which we will change to $r_{t+1} + \gamma \arg\max_a Q(s,a)$. This way, our network moves closer to our Q-learning update for only the action we want, in line with how Q-learning works.
It is also worth nothing that you can parameterise your Neural Network to be a function $Q: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ which would make training more in line with how tabular Q-learning but is seldom used in practice as it becomes much more expensive to compute (you have to do a forward pass for each action, rather than one forward pass per state).

Maybe worth noting that it is valid to model $\hat{q}(s,a, \theta)$ directly with NN mapping $Q : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$. That leads to a different approach using minibatches over all actions in each state for max and argmax operations (inefficient) but a simpler construction of training data. I think the approach you outline is more often used in practice though

@NeilSlater I had to do this recently... can get quite messy to programme (or maybe that was just the specific paper I was having to implement...)

You might make a neural network for $Q : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ if the number of valid actions in any state is low compared to full action space and/or actions have useful traits that can be generalised over. Also of course if you are working with an RL process that doesn't need max or argmax over Q (e.g. variations of Actor-Critic)

It was the case of the former, but the paper was weird. The state space as they defined it also depended on the action taken -- this and some other stuff they did made it annoying to put into code.

It's the B > 1 that I seek clarification for. If B > 1, suppose B = 5, do we do what we would do for B = 1 but 5 times, then compute the average for those 5?

@mamauwu ah, apologies. It just becomes a typical batch update like in normal neural networks. You could either loop through your batch and do this individually or you can do it as one update. Either way, I think the common method is to accumulate the loss for each sample in the batch, take the average, and then do backprop with it.

Perfect! That's the answer I was looking for. Thank you so much!

@mamauwu if you're happy with the answer, please mark it as accepted. :-)


text:
What are the differences between Q-Learning and A*?
Q-learning seems to be related to A*. I am wondering if there are (and what are) the differences between them.

Q-learning and A* can both be viewed as search algorithms, but, apart from that, they are not very similar.
Q-learning is a reinforcement learning algorithm, i.e. an algorithm that attempts to find a policy or, more precisely, value function (from which the policy can be derived) by taking stochastic moves (or actions) with some policy (which is different from the policy you want to learn), such as the $\epsilon$-greedy policy, given the current estimate of the value function. Q-learning is a numerical (and stochastic optimization) algorithm that can be shown to converge to the optimal solution in the tabular case (but it does not necessarily converge when you use a function approximator, such as a neural network, to represent the value function). Q-learning can be viewed as a search algorithm, where the solutions are value functions (or policies) and the search space is some space of value functions (or policies).
On the other hand, A* is a general search algorithm that can be applied to any search problem where the search space can be represented as a graph, where nodes are positions (or locations) and the edges are the weights (or costs) between these positions. A* is an informed search algorithm, given that you can use an (informed) heuristic to guide the search, i.e. you can use domain knowledge to guide the search. A* is a best-first search (BFS) algorithm, which is a family of search algorithms that explore the search space by following the next best location according to some objective function, which varies depending on the specific BFS algorithm. For example, in the case of A*, the objective function is $f(n) = h(n) + g(n)$, where $n$ is a node, $h$ the heuristic function and $g$ the function that calculates the cost of the path from the starting node to $n$. A* is also known to be optimal (provided that the heuristic function is admissible)

Note that there are algorithms like RTA* and LRTA* (and many others) that are much closer to Q-learning while keeping many of the principles of A*. (Although typically they learn a value function for states instead of a q-value for state/action pairs.)

@NathanS. I was not aware of these algorithms. Thanks for mentioning them. Maybe you could provide an answer that briefly explains them and the difference between them and A* and Q-learning, although that wasn't the question.


text:
Can the normal equation be used to optimise the RNN's weights?
I have made an RNN from scratch in Tensorflow.js. In order to update my weights (without needing to calculate the derivatives), I thought of using the normal equation to find the optimal values for my RNN's weights. Would you recommend this approach and if not why?

Unfortunately, this is not possible. The normal equation can only directly optimise a single layer that connects input and output. There is no equivalent for multiple layers such as those in any neural network architecture.


text:
What is the time complexity of the upsampling stage of the U-net?
I am trying to determine the complexity of the neural network we use. The neural network is a U-net generator with an input shape of NxN (not an image but image-like data) and output of the same shape. There is 7x downsampling and 7x upsampling. Downsampling is a simple convolutional layer, where I have no problem to determine complexity as stated here:
$$
O\left(\sum_{l=1}^{d} n_{l-1} \cdot s_{l}^{2} \cdot n_{l} \cdot m_{l}^{2}\right)
$$
I however cannot find what is big O complexity for the upsampling stage, where the UpSampling2D layer is used before convolution.
Any idea what is the time complexity of the upsampling convolutional layer, or where I might find information? Thanks in advance!

I recently gave an answer where I explain the idea behind how you should calculate the time complexity of a convolution, although, right now, I don't give a general formula, but only the time complexity in a specific case. I think you can extend my reasoning to your use case, if nobody answers this question. I may answer your question later (if I have some time).

@nbro by looking deeper into the problem, it seems my question is actually irrelevant, the UpSampling2d layer in keras according to it's documentation:
Repeats the rows and columns of the data by size[0] and size[1] respectively.
thus performs a linear function, which is followed by convolution

After further investigating the problem I have found the answer:
U-net generators' up-sampling stage consists of two steps:

Use UpSampling2D layer
Apply convolution on the output

The UpSampling2D layer is in the keras documentation described as:
Repeats the rows and columns of the data by size[0] and size[1] respectively.
From this information, we can calculate the time cost for UpSampling2D alone. Lets set size to (2,2), as is set in basic configuration of the U-net generator. The output of the UpSampling2D is then doubled. In case we started with (4,4,3), where the last index corresponds to number of channels, the output shape will be 8,8,3. We can see that each row and column need to be copied twice in each channel. From this we can define time complexity of a single up-sampling as:
$$
O\left(2 \cdot c \cdot n \cdot s\right)
$$
Where c corresponds to number of channels, n corresponds to input length (one side of a matrix) and s is equal to filter size. Assuming that length and filter size have square shape, the complexity is multiplied by 2. Since in this case the the filter size is known, equal to (2,2), the notation can be simplified to:
$$
O\left(4 \cdot c \cdot n \right) = O\left(c \cdot n \right)
$$
In my case, with only 1 channel, the complexity is simply
$$
O\left(n \right)
$$
Which means the up-sampling stage is linear, and the only important feature is input size, which is negligible to the complexity of the following convolutional layer and can be ignored.


text:
What do the state features of KukaGymEnv represent?
I trying to use DDPG augmented with Hindsight Experience Replay (HER) on pybullet's KukaGymEnv.
To formulate the feature vector for the goal state, I need to know what the features of the state of the environment represent. To be precise, a typical state vector of KukaGymEnv is an object of the numpy.ndarray class with a shape of (9,).
What do each of these 8 elements represent, and how can I formulate the goal state vector for this environment? I tried going through the source code of the KukaGymEnv, but was unable to understand anything useful.

Here's an incomplete answer, but it may help.
Your state is read by the function getExtendedObservation(). This function makes two things : it calls the function getObservation() from this source code, gets a state, and extend this state with three components :

relative x,y position and euler angle of block in gripper space

But what are the 5 first components returned by getObservation()? From what I read, there are positions, then euler angles describing the orientation. But that would make 6 + 3 = 9 features, so there is either only 2 positions, or only 2 euler angles. You may know kuka better than me and know the answer of this one :).
So, to sum up :
state = [X, Y, (Z, ) , Alpha, Gamma, (Beta, ), gripX, gripY, gripAlpha]

(Either Z or Beta is absent)

There's a mistake in the question. The state space for the environment is actually a 9 dimensional vector, in which case, your answer is correct. I ll rectify the typo right away. Thanks for the help!


text:
How can we teach a neural net to make arbitrary data associations?
Let's say I have pairs of keys and values of the form $(x_1, y_1), \dots, (x_N, y_N)$. Then I give a neural net a key and a value, $(x_i, y_i)$. For example, $x_i$ could be $4$ and $y_i$ could be $3$, but this does not have to be the case.
Is there a way to teach the neural net to output the $y_i$ variable every time it receives the corresponding $x_i$?
By the way, how do our brains perform this function?

Why do you need a neural network to perform this extremely simple task of outputting 3 whenever it receives 4? Can you provide more details about your problem? For example, do you have multiple different parts of numbers or just one pair or what? Also, ask only one question per post, i.e. what is your main question? Is that about mapping 4 to 3 or about brains? Moreover, have you ever heard of supervised learning?

So, I know there are way more simple ways to do this, but I am just curious about how to replicate how our brains memorize things in a neural net. And it wouldn’t be just mapping 4 to 3. It would be any arbitrary association of numbers, like how our brains can memorize anything

@DuttaA as far as I know, RBMs do unsupervised learning (visible neurons are for the X data only). If I'm wrong, could you developp your point in an answer ? I'd be pleased to read you.

In a nutshell : Memorizing is not Learning
So, first let's just remind the classical use of a neural net, in Supervised Learning :

You have a set of $(x_{train}, y_{train}) \in X \times Y$ pairs, and you want to extract a general mapping law from $X$ to $Y$
You use a neural net function $f_{\theta} : x \rightarrow f_{\theta}(x)$, with $\theta$ the weights (parameters) of your net.
You optimise $f_{\theta}$ by minimizing the prediction error, represented by the loss function.

Can this solve your question ? Well, I don't think so. With this scheme, your neural net will learn an appropriate mapping from the set $X$ to the set $Y$, but this mapping is appropriate according to your loss function , not to your $(x_{train}, y_{train})$ pairs.
Imagine that a small part of the data is wrongly labelled. A properly trained net learns to extract relevant features and thus will predict correctly the label, not like you did. So the net doesn't memorize your pairs, it infers a general law from the data, and this law may not respect each $(x_{train}, y_{train})$.
So classical Supervised Deep Learning should not memorize $(x_{train}, y_{train})$  pairs.
However, you could memorize using a net with too many parameters :  it's Overfitting !

In this case, you set up the net with too many parameters. That gives too much degrees of freedom to your net, and the net will use these DoFs to exactly fit rightly each $(x_{train}, y_{train})$  pair you feed during training.
However, for an input $x$ that it never saw during training, $f_{\theta}(x)$ would have no meaning. That's why we say an overfitted net did not learn, and overfitting is feared by many DL practitioner.

But as long as you want only to memorize, and not to learn, a overfitted net may be the a solution. An other solution for memorization may be Expert Systems, I don't know them enough to explain them, but you may check that if you want.
What about the brain ?
The matter in answering this question is that we don't really know how does the brain work. I highly recommend this article discussing neural networks and the brain.
Some thoughts to start :

The brain has an incredibly huge amount of parameters, and has a great plasticity. In that sense, we could draw a parallel with overfitted neural networks :  so the brain could be also able to overfit, and thus to memorize by this mean.
Our brain is not a feed forward network at all, we can't delimitate any layer, just some rough zones where we know that some specific information is processed. This makes any parallel between neural nets and the brain difficult.
It's still unclear how our brain updates itself. There's no backpropagation for instance. Our overfitted networks also stem from the update processes (for instance, adding regularization to the loss helps avoiding underfitting), but we have no idea of how this works in the brain, so that's another hurdle to drawing parallels !
A more personal thought : the brain is able to both learn and memorize ("The exception that proves the rule" motto shows that I think), while learning and memorizing are antonyms for neural nets...

How can you learn without memorizing?

ahah good question :) your comment asks for a proper definition of memorizing (and maybe I should have done it in my answer). If you consider memorizing as just 'storing the raw input data', then it has little to do with learning, as learning is a statistical optimization problem (for neural nets). When you learn, what you memorize are patterns, trends that you extracted from the raw data.


text:
Why is the mean used to compute the expectation in the GAN loss?
From Goodfellow et al. (2014), we have the adversarial loss:
$$ \min_G \, \max_D V (D, G) = \mathbb{E}_{x∼p_{data}(x)} \, [\log \, D(x)]  + \, \mathbb{E}_{z∼p_z(z)} \, [\log \, (1 − D(G(z)))] \, \text{.} \quad$$
In practice, the expectation is computed as a mean over the minibatch. For example, the discriminator loss is:
$$
\nabla_{\theta_{d}} \frac{1}{m} \sum_{i=1}^{m}\left[\log D\left(\boldsymbol{x}^{(i)}\right)+\log \left(1-D\left(G\left(\boldsymbol{z}^{(i)}\right)\right)\right)\right]
$$
My question is: why is the mean used to compute the expectation? Does this imply that $p_{data}$ is uniformly distributed, since every sample must be drawn from $p_{data}$ with equal probability?
The expectation, expressed as an integral, is:
$$
\begin{aligned}
V(G, D) &=\int_{\boldsymbol{x}} p_{\text {data }}(\boldsymbol{x}) \log (D(\boldsymbol{x})) d x+\int_{\boldsymbol{z}} p_{\boldsymbol{z}}(\boldsymbol{z}) \log (1-D(g(\boldsymbol{z}))) d z \\
&=\int_{\boldsymbol{x}} p_{\text {data }}(\boldsymbol{x}) \log (D(\boldsymbol{x}))+p_{g}(\boldsymbol{x}) \log (1-D(\boldsymbol{x})) d x
\end{aligned}
$$
So, how do we go from an integral involving a continuous distribution to summing over discrete probabilities, and further, that all those probabilities are the same?
The best I could find from other StackExchange posts is that the mean is just an approximation, but I'd really like a more rigorous explanation.
This question isn't exclusive to GANs, but is applicable to any loss function that is expressed mathematically as an expectation over some sampled distribution, which is not implemented directly via the integral form.
(All equations are from the Goodfellow paper.)

It seems your question is concerned with how an empirical mean works.
It is indeed true that, if all $x^{(i)}$ are independent identically distributed realisations of a random variable $X$, then $\lim_{n \rightarrow \infty} \frac{1}{n}\sum_{i=1}^n f(x^{(i)}) = \mathbb{E}[f(X)]$. This is a standard result in statistics known as the law of large numbers.


text:
How is dropout applied to the embedding layer's output?
model = tf.keras.Sequential([
    tf.keras.layers.Embedding(1000, 16, input_length=20),
    tf.keras.layers.Dropout(0.2),                           # <- How does the dropout work?
    tf.keras.layers.Conv1D(64, 5, activation='relu'),
    tf.keras.layers.MaxPooling1D(pool_size=4),
    tf.keras.layers.LSTM(64),
    tf.keras.layers.Dense(1, activation='sigmoid')
])

I can understand when dropout is applied between Dense layers, which randomly drops and prevents the former layer neurons from updating parameters. I don't understand how dropout works after an embedding layer.
Let's say the output shape of the Embedding layer is (batch_size,20,16) or simply (20,16) if we ignore the batch size. How is dropout applied to the embedding layer's output?
Randomly dropout rows or columns?

It doesn't drops rows or columns, it acts directly on scalars. The Dropout Layer keras documentation explains it and illustrates it with an example :

The Dropout layer randomly sets input units to 0 with a frequency of rate

After an Dense Layer, the Dropout inputs are directly the outputs of the Dense layer neurons, as you said. After your embedding layer, in your case, you should have rate * (16 * input_length) = 0.2 * 20 * 16 = 64 inputs set to 0 out of the 320 scalars inputs. These 64 dropped inputs are randomly selected in the 20x16 grid. Note that the Dropout rescales the non dropped inputs by multiplicating them by a factor $\frac{1}{1-rate}$.


text:
How AlphaGo Zero is learning from $\pi_t$ when $z_t = -1$?
I have questions on the way AlphaGo Zero is trained.
From original AlphaGo Zero paper, I knew that AlphaGo Zero agent learns a policy, value functions by the gathered data $\{(s_t, \pi_t, z_t)\}$ where $z_t = r_T \in \{-1,1\}$.
However, the fact that the agent tries to learn a policy distribution when $z_t = -1$ seems to be counter-intuitive (at least to me).
My assertion is that the agent should not learn the policy distribution of when it loses (i.e, gets $z_t=-1$), since such a policy will guide it to lose.
I think I have missed some principles and resulted in that assertion. Or is my assertion reasonable, either?

Intuitively I think there's definitely something to be said for your idea, but it's not a 100% clear case, and there are also some arguments to be made for the case that we should also be training the policy from data where $z_t = -1$.
So, first let's establish that if we do indeed choose to discard any and all data where $z_t = -1$, we are in fact discarding a really significant part of our data; we're discarding 50% of all the data we generate in games like Go where there are no draws (less than that in games like Chess where there are many draws, but still a significant amount of data). So this is not a decision to be made lightly (it has a major impact on our sample efficiency), and we should probably only do it if we really believe that policy learning from any data where $z_t = -1$ is actually harmful.

The primary idea behind the self-play learning process in AlphaGo Zero / AlphaZero may intuitively be explained as:

When we run an MCTS search biased by a trained policy $\pi_t$, we expect the resulting distribution of visits to be slightly better than what was produced by $\pi_t$ alone.
According to the expectation from point 1., we may use the visit counts of MCTS as a training target for the policy $\pi_t$, and hence we expect to get a slight improvement in the quality of that trained policy.
If we were to now run a new MCTS search biased by the updated policy in the same situation again, we would expect that to perform even better than it previously did because it is now biased by a new policy which has improved in comparison to the policy we previously used.

Of course, there can be exceptions to point 1. if we get unlucky, but on average we expect that to be true. Crucially for your question, we don't expect this to only be true in games where we actually won, but still also be true in games that we ultimately end up losing. Even if we still end up losing the game played according to the MCTS search, we expect that we at least put up a slightly better fight with the MCTS + $\pi_t$ combo than we would have done with just $\pi_t$, and so it may still be useful to learn from it (to at least lose less badly).
On top of this, it is important to consider that we intentionally build in exploration mechanisms in the self-play training process, which may "pollute" the signal $z_t$ without having polluted the training target for the policy. In self-play, we do not always pick the action with the maximum visit count (as we would in an evaluation match / an important tournament game), but we pick actions proportionally to the MCTS visit counts. This is done for exploration, to introduce extra variety in the experience that we generate, to make sure that we do not always learn from exactly the same games. This can clearly affect the $z_t$ signal (because sometimes we knowingly make a very very bad move just for the sake of exploration), but it does not affect the policy training targets encountered throughout that game; MCTS still tries to make the best that it can out of the situations it faces. So, these policy training targets are still likely to be useful, even if we "intentionally" made a mistake somewhere along the way which caused us to lose the game.

Thanks for your answer! It really helped me out understanding the training procedure of AlphaGo Zero, especially in understanding the power of "exploration" in learning.


text:
Is value iteration stopped after one update of each state?
In section 4.4 Value Iteration, the authors write

One important special case is when policy evaluation is stopped after just one sweep (one update of each state). This algorithm is called value iteration.

After that, they provide the following pseudo-code

It is clear from the code that updates of each state occur until $\Delta$ is sufficiently small. Not one update of each state as the authors write in the text. Where is the mistake?

Where the author mentions the policy evaluation being stopped after one state, they are referring to the part of the algorithm that evaluates the policy -- the pseudocode you have listed is the pseudocode for Value Iteration, which consists of iterating between policy evaluation and policy improvement.
In normal policy evaluation, you would apply the update $v_{k+1}(s) = \mathbb{E}_\pi[R_{t+1} + \gamma v_k(S_{t+1})|S_t = s]$ until convergence. In the policy iteration algorithm, you perform policy evaluation until the value functions converge in each state, then apply policy improvement, and repeat. Value iteration will perform policy evaluation for one update, i.e. not until convergence, and then improve the policy, and repeat this until the value functions converge.
The line
$$V(s) \leftarrow \max_a \sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]$$
perform both the early stopping policy evaluation and policy improvement. Lets examine how:
The $\sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]$ is the same as the expectation I wrote earlier, so we can see clearly that is policy evaluation for just one iteration. Then, we take a max over the actions -- this is policy improvement. Policy improvement is defined as (for a deterministic policy)
\begin{align}
\pi'(s) &= \arg\max_a q_\pi(s,a) \\ &= \arg\max_a \sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]\;.
\end{align}
Here, we assign the action that satisfies the $\mbox{argmax}$ to the improved policy in state $s$. This is essentially what we are doing in the   line from your pseudo when we take the max. We are evaluating our value function for a policy that is greedy with respect to said value function.
If you keep applying the line from the pseudocode of value iteration it will eventually converge to the optimal value function as it will end up satisfying the Bellman Optimality Equation.

Thank you for your explanation! Could you please point out the line in the code that does policy evaluation and the line that does "...then improve the policy..."?

the line under $v \leftarrow V(s)$ does both. you should familiarise yourself with policy eval and policy improvement and you will see why this is so. -- I can edit my answer in about 30 mins to reflect this.

+1 But strictly speaking, isn't the authors wrong in their claim?  Policy iteration where the evaluation is stopped after one sweep progresses very differently from value iteration as far as I can see. The similarity seems very superficial if one actually goes through the algorithms step by step.


text:
What is the most appropriate ML algorithm for creating recommendations
I am trying to find the best algorithm to create a list of recommendations for a user based on the interests of all other users.
Say I have a list of of samples:
$samples = [
    ['hot dog', 'big mac', 'whopper'],
    ['hot dog', 'big mac'],
    ['hot dog', 'whopper'],
    ['big mac', 'dave single'],
    ['whopper', 'mcnuggets', 'mcchicken'],
    ['mcchicken', 'original chicken sandwich'],
    ['mcchicken', 'mcrib']
];

And we will say each array in the sample list is unique user's food preferences.
Let's say now I have a user with this food preference:
['hot dog', 'mcchicken']

I want to be able to recommend to this user other foods that other users have in their preferences.
So in the simplest terms, it should return:
['whopper', 'big mac', 'original chicken sandwich', 'mcrib', 'mcnuggets']

Obviously I will also introduce other variables such as how each user rates each item in their preference list and also the percentage of users that need to have that item in order to use their other food items as recommendations.
But I would like to find the best algorithm to start working on it.
At first I thought Apriori might be my best guess, but I wasn't having luck once I introduced multiple items.

Why is "mcnuggets" not included in the output? I thought it should because one person likes ['whopper', 'mcnuggets', 'mcchicken'].

@VarunVejalla sorry I missed that. You're right, mcnuggets should also be included.

In that case, I don't think a machine learning approach is needed. Simply loop through all the samples. If there is a common element between the sample and the test user, add all elements in the sample (except for those already preferred by the user) to the recommendations.

@VarunVejalla yes I've thought about that before but I do not want it to be that simple. I was just giving a simple usage case as an example. I'd want to later introduce other variables to the equation i.e. how much each user rates such items, how much each items are priced, what categories each items belong in, etc... It can all be done manually using various logic, but I was hoping there was a ML way to do it smarter so I'm not looping through millions of items each time.

You can use Collaborative Filtering, and specifically its memory based approach.
The problem that you have discussed in the question should probably be solved using user-item collaborative filtering, which will calculate similarity between users and then recommend the item.
The similarity can be be calculated using cosine similarity or Pearson's similarity formulae.
The best thing about this approach is that no training is required here but if you wish to have very large data, this approach's performance decreases.