Reward Shaping and Inverse RL

Introduction: The Reward Engineering Challenge

In reinforcement learning, the reward function R(s,a,s') defines what the agent should optimize. But designing good rewards is surprisingly difficult. How do you reward a self-driving car? "Reach destination quickly" → drives recklessly. "Follow safety rules" → drives too slowly. "Minimize fuel" → poor passenger comfort. Real-world objectives are complex and often involve implicit human preferences that are hard to formalize.

Reward Shaping and Inverse Reinforcement Learning (IRL) address this fundamental challenge. At Indian autonomous vehicle companies (Motional India, Nuro India operations), engineers use these techniques to learn driving policies from human demonstrations instead of hand-crafting complex reward functions.

The Reward Shaping Problem: Dense vs Sparse Rewards

Sparse Rewards (Hard): Give reward only at goal.

Example: Chess RL agent gets +1 for winning, 0 for everything else. With 10⁴⁰ possible states, finding the goal by random exploration is impossible. The agent has no learning signal for intermediate progress.

Dense Rewards (Easy but Wrong): Give reward at every step.

Example: "Reward = -distance_to_goal" teaches the agent to move toward the goal, BUT it might learn shortcuts that violate constraints (cutting through walls, ignoring physics). The reward function doesn't capture all the goals (safety, elegance, efficiency).

This is the reward misalignment problem: the specified reward doesn't match the true objective.

Potential-Based Reward Shaping: The Mathematical Solution

Instead of designing the true reward, we design a potential function Φ(s) that guides learning without changing the optimal policy:

R_shaped(s, a, s') = R(s, a, s') + γΦ(s') - Φ(s)

The potential Φ is a heuristic value estimate: Φ(s) = "how good is state s?" It guides the agent but doesn't change optimal behavior because the shaped reward preserves the policy gradient.

Theorem (Ng et al. 1999): Potential-based shaping preserves optimal policy — argmax_π E[R_shaped] = argmax_π E[R]

Why? For any trajectory τ = s₀ → s₁ → ... → sₜ:

ΣR_shaped = ΣR + γΦ(sₜ) - Φ(s₀)

The potential difference cancels out when you take expectations (Φ(sₜ) - Φ(s₀) is constant for fixed start/end), so the ranking of policies doesn't change.

Complete Reward Shaping Implementation

import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict

class SimpleNavigationEnv:
    """4x4 grid, agent starts at (0,0), goal is (3,3)."""

    def __init__(self, grid_size=4):
        self.grid_size = grid_size
        self.start = (0, 0)
        self.goal = (grid_size - 1, grid_size - 1)
        self.reset()

    def reset(self):
        self.state = self.start
        return self.state

    def step(self, action):
        """action: 0=up, 1=down, 2=left, 3=right"""
        x, y = self.state
        dx, dy = [(-1, 0), (1, 0), (0, -1), (0, 1)][action]
        x, y = max(0, min(self.grid_size - 1, x + dx)), max(0, min(self.grid_size - 1, y + dy))
        self.state = (x, y)

        # Sparse reward (only at goal)
        reward_sparse = 1.0 if self.state == self.goal else 0.0

        done = self.state == self.goal
        return self.state, reward_sparse, done

    def potential_function(self, state):
        """Heuristic: negative Manhattan distance to goal."""
        x, y = state
        goal_x, goal_y = self.goal
        distance = abs(x - goal_x) + abs(y - goal_y)
        return -distance / (2 * self.grid_size)  # Normalize to [-1, 0]


class QLearningAgent:
    """Q-learning with and without reward shaping."""

    def __init__(self, env, use_shaping=False):
        self.env = env
        self.use_shaping = use_shaping
        self.gamma = 0.99
        self.lr = 0.1
        self.Q = defaultdict(lambda: np.zeros(4))  # Q[state][action]
        self.episode_rewards = []

    def shaped_reward(self, state, action, next_state, sparse_reward):
        """Apply potential-based reward shaping."""
        if not self.use_shaping:
            return sparse_reward

        Φ_s = self.env.potential_function(state)
        Φ_s_prime = self.env.potential_function(next_state)

        shaped = sparse_reward + self.gamma * Φ_s_prime - Φ_s
        return shaped

    def train_episode(self):
        """Run one training episode."""
        state = self.env.reset()
        episode_reward = 0

        for step in range(100):  # Max 100 steps
            # Epsilon-greedy
            if np.random.rand() < 0.1:
                action = np.random.randint(4)
            else:
                action = np.argmax(self.Q[state])

            next_state, sparse_reward, done = self.env.step(action)
            shaped_reward = self.shaped_reward(state, action, next_state, sparse_reward)

            # Q-learning update
            best_next_action = np.argmax(self.Q[next_state])
            td_error = shaped_reward + self.gamma * self.Q[next_state][best_next_action] - self.Q[state][action]
            self.Q[state][action] += self.lr * td_error

            episode_reward += sparse_reward  # Track sparse reward (true objective)
            state = next_state

            if done:
                break

        self.episode_rewards.append(episode_reward)

    def train(self, num_episodes=500):
        """Train for multiple episodes."""
        for _ in range(num_episodes):
            self.train_episode()


# Experiment: Compare with and without shaping
print("="*70)
print("REWARD SHAPING EXPERIMENT: Navigation Task")
print("="*70)

env = SimpleNavigationEnv(grid_size=5)

# Without shaping (sparse reward only)
agent_sparse = QLearningAgent(env, use_shaping=False)
agent_sparse.train(num_episodes=500)

# Reset environment
env = SimpleNavigationEnv(grid_size=5)

# With shaping (sparse + potential)
agent_shaped = QLearningAgent(env, use_shaping=True)
agent_shaped.train(num_episodes=500)

# Compare convergence
print(f"Sparse reward convergence (avg last 50 episodes): {np.mean(agent_sparse.episode_rewards[-50:]):.3f}")
print(f"Shaped reward convergence (avg last 50 episodes): {np.mean(agent_shaped.episode_rewards[-50:]):.3f}")

# Plot
plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)
plt.plot(np.convolve(agent_sparse.episode_rewards, np.ones(10)/10, mode='valid'), label='Sparse Reward')
plt.plot(np.convolve(agent_shaped.episode_rewards, np.ones(10)/10, mode='valid'), label='Shaped Reward')
plt.xlabel('Episode')
plt.ylabel('Episode Reward')
plt.title('Learning Curves: With vs Without Reward Shaping')
plt.legend()
plt.grid(True, alpha=0.3)

plt.subplot(1, 2, 2)
# Calculate success rate (episodes where goal reached)
success_sparse = np.cumsum(agent_sparse.episode_rewards) / (np.arange(len(agent_sparse.episode_rewards)) + 1)
success_shaped = np.cumsum(agent_shaped.episode_rewards) / (np.arange(len(agent_shaped.episode_rewards)) + 1)
plt.plot(success_sparse, label='Sparse Reward')
plt.plot(success_shaped, label='Shaped Reward')
plt.xlabel('Episode')
plt.ylabel('Success Rate')
plt.title('Cumulative Success Rate')
plt.legend()
plt.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

Inverse Reinforcement Learning: Learning from Demonstrations

Instead of specifying rewards, what if we have expert demonstrations and want to infer what the expert was optimizing for?

Problem: Given expert trajectories τ_expert = [s₀ → a₀ → s₁ → ... → sₜ], find reward function R such that the expert's policy is optimal under R.

Ambiguity: Many reward functions could explain the same behavior. Example: expert reaches office = optimize "minimize commute time" or "maximize salary" or "avoid traffic." IRL finds reward functions that generalize.

Maximum Entropy Inverse RL (MaxEnt IRL)

Instead of finding one reward, find the distribution of rewards consistent with expert behavior:

P(R | expert_demos) ∝ exp(E_τ~expert[R(τ)])

Maximum entropy IRL selects rewards that make expert behavior most likely while staying maximally uncertain about rewards elsewhere.

Algorithm (Ziebart et al. 2008):

1. Initialize reward function R
2. Solve forward RL problem: find policy π that optimizes current R
3. Measure divergence between π and expert policy
4. Update R to favor expert trajectories, penalize non-expert trajectories
5. Repeat until convergence

Indian Applications: Autonomous Vehicles and Robotics

Self-Driving Cars: Instead of hand-engineering rewards for "drive safely and efficiently," record expert human drivers and use IRL to learn their implicit policy. The learned reward captures safety, comfort, legality, social norms — all baked into human driving.

Industrial Robots: Record skilled factory workers assembling products, use IRL to learn their technique. The robot learns quality standards, efficiency tricks, and safety practices without explicit programming.

Surgical Robots: Record expert surgeons, learn their decision-making policy. Critical because surgery involves implicit knowledge (feel of tissue, experience, judgment) hard to specify formally.

Key Insight: Why IRL Matters

Reward engineering is the bottleneck in RL deployment. For every hour of RL algorithm research, companies spend 10 hours tuning reward functions. IRL shifts focus from "how do we specify objectives" to "how do we learn from human behavior," which is far more scalable for real-world systems.

Practice Problems for Advanced Students

1. (Theory): Prove that potential-based reward shaping preserves optimal policy. Show that the potential difference cancels in trajectory returns.

2. (Implementation): Implement Q-learning with and without potential-based shaping. Measure convergence speed. Verify that policy converges to same optimal but shaped converges faster.

3. (Design): Design a potential function for a robotic manipulation task (pick up object, place it). Show that it accelerates learning without changing the optimal policy.

4. (IRL): Implement MaxEnt IRL on a simple MDP. Learn reward function from expert demonstrations. Verify that learned policy mimics expert.

5. (Real-World): Design an IRL system to learn defensive driving from Indian drivers. How would you collect demonstrations? What reward features would you expect to learn (speed, distance to other cars, lane changes)?

Key Takeaways — Master These Concepts

• Reward misalignment: Specified rewards often don't capture true objectives — critical problem in RL deployment
• Sparse vs dense rewards: Sparse = no learning signal, dense = possible misalignment. No perfect solution, must balance
• Potential-based shaping: Mathematically proven to preserve optimal policy while accelerating learning
• Inverse RL: Learn rewards from behavior — shifts from "specify goals" to "learn from examples"
• MaxEnt IRL: Find distribution of reward functions that explain expert behavior, not just one
• Practical impact: Reduces reward engineering burden, enables learning from human/expert demonstrations
• Real applications: Autonomous driving, robotics, surgery, finance — anywhere expert behavior is available

Deep Dive: Reward Shaping and Inverse RL

At this level, we stop simplifying and start engaging with the real complexity of Reward Shaping and Inverse RL. In production systems at companies like Flipkart, Razorpay, or Swiggy — all Indian companies processing millions of transactions daily — the concepts in this chapter are not academic exercises. They are engineering decisions that affect system reliability, user experience, and ultimately, business success.

The Indian tech ecosystem is at an inflection point. With initiatives like Digital India and India Stack (Aadhaar, UPI, DigiLocker), the country has built technology infrastructure that is genuinely world-leading. Understanding the technical foundations behind these systems — which is what this chapter covers — positions you to contribute to the next generation of Indian technology innovation.

Whether you are preparing for JEE, GATE, campus placements, or building your own products, the depth of understanding we develop here will serve you well. Let us go beyond surface-level knowledge.

The Theory of Computation: What Can and Cannot Be Computed?

At the deepest level, computer science asks a philosophical question: what are the limits of computation? This leads us to some of the most beautiful ideas in all of mathematics:

  THE HIERARCHY OF COMPUTATIONAL PROBLEMS:

  ┌──────────────────────────────────────────────────┐
  │ UNDECIDABLE — No algorithm can ever solve these  │
  │ Example: Halting Problem                         │
  │ "Will this program eventually stop or run        │
  │  forever?" — Alan Turing proved in 1936 that     │
  │  no general algorithm can determine this!        │
  ├──────────────────────────────────────────────────┤
  │ NP-HARD — No known efficient algorithm           │
  │ Example: Travelling Salesman Problem             │
  │ "Visit all 28 state capitals with minimum        │
  │  travel distance" — checking all routes would    │
  │  take longer than the age of the universe        │
  ├──────────────────────────────────────────────────┤
  │ NP — Verifiable in polynomial time               │
  │ P vs NP: Does P = NP? ($1 million prize!)       │
  ├──────────────────────────────────────────────────┤
  │ P — Solvable efficiently (polynomial time)       │
  │ Examples: Sorting, searching, shortest path      │
  └──────────────────────────────────────────────────┘

  If P = NP were proven, it would mean every problem
  whose solution can be VERIFIED quickly can also be
  SOLVED quickly. This would break all encryption,
  solve protein folding, and revolutionise science.

This is not just theoretical. The P vs NP question ($1 million Clay Millennium Prize) has profound implications: if P=NP, every encryption system in the world (including UPI, Aadhaar, banking) would be breakable. Indian mathematicians and computer scientists at ISI Kolkata, IMSc Chennai, and IIT Kanpur are actively researching computational complexity theory and related fields. Understanding these theoretical foundations is what separates a programmer from a computer scientist.

India's Scale Challenges: Engineering for 1.4 Billion

Building technology for India presents unique engineering challenges that make it one of the most interesting markets in the world. UPI handles 10 billion transactions per month — more than all credit card transactions in the US combined. Aadhaar authenticates 100 million identities daily. Jio's network serves 400 million subscribers across 22 telecom circles. Hotstar streamed IPL to 50 million concurrent viewers — a world record. Each of these systems must handle India's diversity: 22 official languages, 28 states with different regulations, massive urban-rural connectivity gaps, and price-sensitive users expecting everything to work on ₹7,000 smartphones over patchy 4G connections. This is why Indian engineers are globally respected — if you can build systems that work in India, they will work anywhere.

ML Pipeline: From Raw Data to Production Model

At the advanced level, machine learning is not just about algorithms — it is about building robust pipelines that handle real-world messiness. Here is a production-grade ML pipeline pattern used at companies like Flipkart and Razorpay:

# Production ML Pipeline Pattern
import numpy as np
from sklearn.model_selection import cross_val_score
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

def build_ml_pipeline(model, X_train, y_train, X_test):
    """
    A standard ML pipeline with validation.
    Works for classification, regression, or clustering.
    """
    # Step 1: Create pipeline (preprocessing + model)
    pipe = Pipeline([
        ('scaler', StandardScaler()),
        ('model', model)
    ])

    # Step 2: Cross-validation (5-fold) — prevents overfitting
    cv_scores = cross_val_score(pipe, X_train, y_train, cv=5)
    print(f"CV Score: {cv_scores.mean():.4f} ± {cv_scores.std():.4f}")

    # Step 3: Train on full training set
    pipe.fit(X_train, y_train)

    # Step 4: Evaluate on held-out test set
    test_score = pipe.score(X_test, y_test)
    print(f"Test Score: {test_score:.4f}")
    return pipe

The key insight is that preprocessing, training, and evaluation should always be encapsulated in a pipeline — this prevents data leakage (where test data information leaks into training). Cross-validation gives you a reliable estimate of model performance. The ± value tells you how stable your model is across different data splits.

In Indian tech, these patterns power recommendation engines at Flipkart, fraud detection at Razorpay, demand forecasting at Swiggy, and credit scoring at startups like CRED and Slice. IIT and IISc researchers are pushing boundaries in areas like fairness-aware ML, efficient inference for mobile (important for India's smartphone-first population), and domain adaptation for Indian languages.

Research Frontiers and Open Problems in Reward Shaping and Inverse RL

Beyond production engineering, reward shaping and inverse rl connects to active research frontiers where fundamental questions remain open. These are problems where your generation of computer scientists will make breakthroughs.

Quantum computing threatens to upend many of our assumptions. Shor's algorithm can factor large numbers efficiently on a quantum computer, which would break RSA encryption — the foundation of internet security. Post-quantum cryptography is an active research area, with NIST standardising new algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium) that resist quantum attacks. Indian researchers at IISER, IISc, and TIFR are contributing to both quantum computing hardware and post-quantum cryptographic algorithms.

AI safety and alignment is another frontier with direct connections to reward shaping and inverse rl. As AI systems become more capable, ensuring they behave as intended becomes critical. This involves formal verification (mathematically proving system properties), interpretability (understanding WHY a model makes certain decisions), and robustness (ensuring models do not fail catastrophically on edge cases). The Alignment Research Center and organisations like Anthropic are working on these problems, and Indian researchers are increasingly contributing.

Edge computing and the Internet of Things present new challenges: billions of devices with limited compute and connectivity. India's smart city initiatives and agricultural IoT deployments (soil sensors, weather stations, drone imaging) require algorithms that work with intermittent connectivity, limited battery, and constrained memory. This is fundamentally different from cloud computing and requires rethinking many assumptions.

Finally, the ethical dimensions: facial recognition in public spaces (deployed in several Indian cities), algorithmic bias in loan approvals and hiring, deepfakes in political campaigns, and data sovereignty questions about where Indian citizens' data should be stored. These are not just technical problems — they require CS expertise combined with ethics, law, and social science. The best engineers of the future will be those who understand both the technical implementation AND the societal implications. Your study of reward shaping and inverse rl is one step on that path.

Key Vocabulary

Here are important terms from this chapter that you should know:

🏗️ Architecture Challenge

Design the backend for India's election results system. Requirements: 10 lakh (1 million) polling booths reporting simultaneously, results must be accurate (no double-counting), real-time aggregation at constituency and state levels, public dashboard handling 100 million concurrent users, and complete audit trail. Consider: How do you ensure exactly-once delivery of results? (idempotency keys) How do you aggregate in real-time? (stream processing with Apache Flink) How do you serve 100M users? (CDN + read replicas + edge computing) How do you prevent tampering? (digital signatures + blockchain audit log) This is the kind of system design problem that separates senior engineers from staff engineers.

The Frontier

You now have a deep understanding of reward shaping and inverse rl — deep enough to apply it in production systems, discuss tradeoffs in system design interviews, and build upon it for research or entrepreneurship. But technology never stands still. The concepts in this chapter will evolve: quantum computing may change our assumptions about complexity, new architectures may replace current paradigms, and AI may automate parts of what engineers do today.

What will NOT change is the ability to think clearly about complex systems, to reason about tradeoffs, to learn quickly and adapt. These meta-skills are what truly matter. India's position in global technology is only growing stronger — from the India Stack to ISRO to the startup ecosystem to open-source contributions. You are part of this story. What you build next is up to you.

Crafted for Class 10–12 • Reinforcement Learning • Aligned with NEP 2020 & CBSE Curriculum