0
$\begingroup$

Why is the sliding puzzle problem episodic and not sequential?

From what I understand, an environment is episodic if each episode is independent and doesn't affect past or future episodes. The actions in the next episode don't depend on the actions in past episodes. In other words, current actions/decisions have no effect on future decisions.

For example, an agent that looks at radiology images to determine if there is a sickness is an example of an episodic environment. One image has nothing to do with the next.

However, in a sequential environment, an agent requires memory of past actions to determine the next best actions and current actions affect future decisions e.g chess

But I think the sliding puzzle can be considered a sequential environment because the agent must make a series of actions (moving tiles) in a specific order to reach the goal state (the solved puzzle). The agent's decision at each step is based on the current state of the puzzle, and the agent's actions affect the state of the puzzle for subsequent steps. These episodes aren't independent, they directly affect each other.

But if we say the sliding puzzle problem is episodic because each puzzle can be seen as one episode, then can't I say the same about chess? Or a crossword puzzle? Or any sequential problem then? One chess match doesn't affect another, and looking at it like that chess would be episodic in that sense (which seems wrong, right?). So why are chess and crossword puzzles sequential but the sliding puzzle is episodic?

$\endgroup$
2
  • 1
    $\begingroup$ By sliding puzzle, can you confirm you're referring to this? Can you please provide the source that defines an "episodic problem" like you defined? Is this from the AIMA book? $\endgroup$
    – nbro
    Jan 14 at 22:10
  • $\begingroup$ That is what I am referring to, although an eight instead of fifteen one. It was said to be an episodic problem according to my university lecture materials which uses the AIMA book $\endgroup$
    – numq
    Jan 24 at 17:24

1 Answer 1

1
$\begingroup$

You might be mixing the definitions of a step and an episode, which is composed of many steps, at least in reinforcement learning.

In a sliding puzzle problem, where the goal is to move the tiles such that an initial configuration becomes another configuration, each move (or action) would be a step in the episode. Each game would be an episode. Games can be considered independent of each other unless e.g. the board configuration of the next game depends on something that happened in the previous game. This would be in the context of RL.

However, it seems to me that you took the definitions of episodic/sequential problems from the AIMA book (or some other source that is based on this book). For completeness, here's excerpt from the book that defines these problems

Episodic vs. sequential: In an episodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then performs a single action. Crucially, the next episode does not depend on the actions taken in previous episodes. Many classification tasks are episodic. For example, an agent that has to spot defective parts on an assembly line bases each decision on the current part, regardless of previous decisions; moreover, the current decision doesn’t affect whether the next part is defective. In sequential environments, on the other hand, the current decision could affect all future decisions. Chess and taxi driving are sequential: in both cases, short-term actions can have long-term consequences. Episodic environments are much simpler than sequential environments because the agent does not need to think ahead.

Now, this definition of episodic problem does not seem to be consistent with the usage of an episodic problem in RL, which is just a problem that doesn't go on forever, but ends after a finite number of steps. Chess and the sliding puzzle problems could be formulated as episodic problems in RL.

However, chess is not episodic according to Norvig and Russell's book because your action at time step $t$ affects your future actions and states.

You're probably not familiar with bandit problems, but it seems to me that AIMA's definition of episodic problems matches the definition of a bandit problem, which is a simple instance of the full RL problem, which is also called sequential decision making problem, because this is a problem where you take actions in sequence.

Why is the sliding puzzle problem episodic?

At this point, you should have understood that there can be more than one definition of a term. According to the common usage of the terms "episode" and "episodic tasks" in RL, the sliding puzzle problem would be episodic. I also think it would be a sequential problem according to the AIMA book because your current action can indeed affect the actions you take in the future, unless e.g. you don't care about the number of moves you make before ending the game.

$\endgroup$
4
  • $\begingroup$ Thank you for the reply. My professor also told me that the definitions are not strict and can be interpreted differently. These classifications are there to help pick a technique to solve it. I was mostly confused because going only by the AIMA book the touring Romania problem in chapter 3 should be sequential, but it is said to be episodic. $\endgroup$
    – numq
    Jan 24 at 17:29
  • $\begingroup$ @numq According to AIMA, sequential means that your current actions may affect the future actions, while in episodic tasks your current action does not affect the next action. I am not sure which problem the Romania problem is, but if you're referring to the problem of finding the shortest path in a Romanian map, if I remember correctly, then I think whether it's sequential or episodic (still using the AIMA definitions) depends on your actual goal (i.e. problem definition). $\endgroup$
    – nbro
    Jan 24 at 19:22
  • $\begingroup$ But let's say that you want to go from one start state to a goal state. Then your current action may affect your next action, especially in a directed graph, where you may not be able to go back. Let's say you take some action $a$ in state $s$, which leads you to state $s'$, from which you cannot go out, then your action $a$ determined the actions you can now take in $s'$. This seems to me that it would be a sequential problem. $\endgroup$
    – nbro
    Jan 24 at 19:23
  • $\begingroup$ So, basically, if there's dependence between the present and the future, then it's sequential, if there's no such dependency, it's episodic. Again, I'm using the AIMA definitions here. In RL, we care about problems where the present affects the future (so that's the default) and they are called sequential problems too, but in RL you also have episodes, which is something different to what AIMA refers to, which seems to be a step (in RL) $\endgroup$
    – nbro
    Jan 24 at 19:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .