Dynamic Programming for Nonlinear Costs

A Familiar Problem with New Rules

The modified exercise is still Jack's car rental problem. It is not a completely different optimization problem. The change is that the cost attached to an overnight arrangement now follows more complicated rules: one movement may be free, other movements may have direction-dependent charges, and parking may add a fixed charge after movement. These changes are useful because they show how dynamic programming handles costs that are not simply linear.

Why Policy Iteration Runs Again

A policy is a rule for choosing an action in the rental problem. When the movement and parking rules change, the cost attached to an action changes as well. The best action under the original rules therefore cannot simply be assumed to remain best under the modified rules. Policy iteration is used to re-solve the problem: evaluate the current rental policy under the new rules, improve the policy using those evaluations, and continue until the policy stabilizes.

The loop matters because the exercise changes the problem being solved. The original policy is valuable as a baseline, but the modified costs require a fresh solution. A policy that stabilizes under the new movement and parking rules is the policy relevant to the modified problem.

Movement Cost by Direction

The movement rule is directional. A car moved from the first location to the second can use the employee's free shuttle, but the allowance covers only one car. The first car moved in that direction receives the special free treatment. Every additional car moved from the first location to the second costs $2. Movement in the opposite direction costs $2 for every car moved.

The Overnight Parking Threshold

The parking rule is assessed after movement is complete. The relevant quantity is the number of cars left overnight at each location. Whenever a location exceeds 10 overnight cars, a second-parking-lot charge of $4 is added. The charge is fixed: it does not increase according to how far the overnight count is above 10.

Combining Costs in Dynamic Programming

The modified problem has a nonlinear cost pattern because different parts of an action are treated differently. The first car sent in one direction can be free, later cars in that direction are charged, movement in the opposite direction is charged for every car, and the parking charge appears as a fixed amount only after an overnight threshold is crossed. These rules do not need to be forced into one simple linear expression.

Dynamic programming accommodates this by evaluating the actual cost of each action and the possible future states that follow it. The method breaks a complex problem into simpler subproblems. It does not require every cost to have the same linear form, so it can represent the free-movement exception, direction dependence, threshold charge, and other arbitrary dynamics within the problem.

Implementation Checks

A staged implementation check is safer than changing every rule at once. First confirm that the program solves the original rental problem correctly. Then introduce the free shuttle rule and the limited-parking rule separately. At each stage, inspect the states, available actions, transition probabilities, rewards or costs, and policy changes. Finally, check that policy iteration stabilizes on the modified problem.

• Applying the free shuttle allowance to every car moved from the first location to the second.

  The free treatment applies to only one car.

  Fix: Apply the free allowance to the first car and charge $2 for each additional car in that direction.

• Using the same movement rule in both directions.

  The free shuttle exception is specified for movement from the first location to the second; the opposite direction costs $2 for every car moved.

  Fix: Handle the two directions separately.

• Charging parking before determining the overnight counts.

  The second-parking-lot charge is assessed after movement.

  Fix: Complete the movement calculation, determine the cars left overnight at each location, and then apply the threshold rule.

• Making the parking charge grow with every car above 10.

  The charge is a fixed $4 whenever the overnight count exceeds 10.

  Fix: Use one fixed $4 charge for each location that exceeds the threshold.

• Trusting the modified implementation without checking the original problem.

  An existing error can be confused with an error introduced by the modification.

  Fix: Validate the original problem first, then add the new rules incrementally.

Apply the Rules

Key Takeaways

1. The exercise modifies Jack's car rental problem rather than replacing it, so the original problem should serve as a reference case.
2. Policy iteration must re-solve the rental problem because the modified movement and parking rules change action costs and the resulting policy.
3. The first car moved from the first location to the second can use the free shuttle; additional cars in that direction cost $2 each, while movement in the opposite direction costs $2 per car.
4. After movement, a fixed $4 parking charge applies at any location with more than 10 overnight cars.
5. Dynamic programming can represent these nonlinear costs and arbitrary dynamics by evaluating actual action costs and possible future states.
6. A trustworthy implementation checks the original problem first and then verifies states, actions, transitions, costs, and policy stabilization as the new rules are introduced.