AI: Discounted returns

Compute what an agent is trying to maximise.

What to build

A program that computes the discounted return from every step of an episode.

Requirements

  • The return from step t is rₜ + γ rₜ₊₁ + γ² rₜ₊₂ + … up to the end of the episode.
  • Print the return from each step, in order, with three decimal places, separated by spaces.

Input

Line 1: γ. Line 2: the rewards.

Output

One line.

Constraints

At most 100 rewards.

Example

Input:

0.5
1 2 3

Output:

2.750 3.500 3.000

Why it works

Each return is the next reward plus the discounted return after it, so one backward pass computes them all.

Examples

Example 1 · Input
0.5
1 2 3
Expected output
2.750 3.500 3.000
Example 2 · Input
1
-1 -1 10
Expected output
8.000 9.000 10.000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Work backwards: the last step's return is its reward, and each earlier return is its reward plus γ times the next return.

Hint 2

Print the returns in the original order.

Solution

Show one correct solution (try it yourself first)
gamma = float(input())
rewards = list(map(float, input().split()))
returns, g = [], 0.0
for r in reversed(rewards):
    g = r + gamma * g
    returns.append(g)
print(" ".join(f"{g:.3f}" for g in reversed(returns)))

Lesson: Reinforcement learning →