Why is the sliding puzzle problem episodic?

Question

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?

Answer 1

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.