Dynamic programming, approximation in function space, successive approximations - One Line Questions

1. What is 'successive approximations'? — A method where a problem is solved by repeatedly applying a process, with each step bringing the solution closer to the true value.
2. What is a 'policy' in dynamic programming? — A rule that specifies the decision to be taken in each state.
3. In dynamic programming, what is a 'stage' typically associated with? — A decision-making point or a step in the problem's progression
4. What is a 'spline' in the context of function approximation? — A piecewise polynomial function that is smooth at the points where the pieces join (knots).
5. In the context of dynamic programming, what is 'memoization'? — Storing the results of expensive function calls and returning the cached result when the same inputs occur again.
6. What is a 'normed vector space'? — A vector space where each vector has a length or magnitude (norm).
7. What is 'policy iteration' in dynamic programming? — An algorithm that alternates between evaluating a policy and improving it.
8. What is the 'value iteration' algorithm in dynamic programming? — An iterative method to compute the optimal value function by repeatedly applying the Bellman optimality equation.
9. What does the 'principle of optimality' state in the context of dynamic programming? — An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision.
10. What is the 'best approximation' of a function f in a function space with respect to a given norm? — A function g such that the norm of the difference ||f - g|| is minimized.
11. Consider the Fibonacci sequence. How can dynamic programming be used to compute F(n)? — By iteratively computing F(0), F(1), F(2), ..., F(n), storing each result.
12. How can dynamic programming be applied to approximate solutions in function space? — By discretizing the function space and applying standard dynamic programming techniques.
13. What is the advantage of using 'successive approximations' over direct methods for solving certain equations? — Successive approximations can handle problems where direct analytical solutions are difficult or impossible to obtain.
14. What is the fundamental principle behind dynamic programming? — Breaking down a problem into overlapping subproblems and solving each subproblem only once
15. What is the primary difference between dynamic programming and recursion with memoization? — Dynamic programming typically solves subproblems in a bottom-up manner, while recursion with memoization is top-down.
16. What is 'least squares approximation'? — Finding a function that minimizes the sum of the squares of the errors at given points.
17. In the context of approximation in function space, what is 'regression'? — Finding a function that best fits a set of data points in some average sense, without necessarily passing through any of them.
18. What is 'interpolation' in the context of function approximation? — Finding a function that passes through a given set of points.
19. What does 'approximation in function space' generally refer to? — Finding a function that is close to an optimal function or satisfies certain properties, often when exact solutions are difficult or impossible.
20. Which type of problem is often solved using successive approximations? — Solving non-linear equations or systems of equations.
21. For the method of successive approximations to converge to a unique fixed point, what condition must the function g(x) typically satisfy? — g(x) must be a contraction mapping (i.e., |g'(x)| < 1 in the relevant interval).
22. In the context of solving equations, what does the method of successive approximations (or fixed-point iteration) involve? — Rearranging the equation into the form x = g(x) and iterating x_{n+1} = g(x_n).
23. What is the Chebyshev approximation (or minimax approximation)? — Minimizing the maximum absolute error between the function and its approximation.
24. Which of the following is NOT a characteristic of problems typically solved by dynamic programming? — Greedy choice property
25. Which type of problems are most suitable for dynamic programming? — Problems exhibiting optimal substructure and overlapping subproblems
26. What is the Bellman equation for the Q-function, often solved using successive approximations? — Q(s,a) = R(s,a) + gamma * max_{a'} Q(s',a')
27. What is the concept of 'discretization' in approximation? — Replacing a continuous variable or function with a finite set of discrete values or points.
28. Which of the following is a common application of dynamic programming? — All of the above
29. Which of the following is a common type of basis function used in approximation? — All of the above
30. What is the Weierstrass Approximation Theorem fundamentally about? — That any continuous function on a closed interval can be approximated arbitrarily well by a polynomial.
31. What does it mean for an approximation to be 'arbitrarily well'? — The error can be made smaller than any pre-assigned positive number.
32. Consider the Bellman equation in dynamic programming. How are successive approximations used to solve it? — The value function is iteratively updated using the Bellman equation until convergence.
33. How does the choice of norm affect the 'best approximation' in function space? — Different norms measure 'closeness' differently, leading to different best approximations.
34. What is the 'curse of dimensionality' in dynamic programming? — The exponential increase in the number of states as the number of variables or dimensions increases, making computation infeasible.
35. In the context of approximation, what is an 'error bound'? — An upper limit on the magnitude of the error of the approximation.
36. What is an 'initial guess' in the method of successive approximations? — The first approximation (x_0) used to start the iterative process.
37. What is the 'state-action value function' (Q-function) in reinforcement learning, which heavily relies on dynamic programming principles? — The expected return starting from state 's', taking action 'a', and following a particular policy thereafter.
38. What is a 'state' in a dynamic programming problem? — A unique configuration or representation of the subproblem being solved.
39. What is the 'horizon' in a dynamic programming problem? — The number of stages or time periods over which decisions are made.
40. What is the 'state-space' in dynamic programming? — The set of all possible configurations or situations that the system can be in.
41. What is 'function space' in mathematics? — The set of all functions that map from one set to another.
42. What is the primary advantage of using approximation methods in function space? — They can handle problems that are computationally intractable or have no exact analytical solution.
43. How does successive approximations relate to dynamic programming? — Dynamic programming can be viewed as a form of successive approximation where optimal policies are iteratively improved.
44. What is the role of basis functions in function approximation? — They define the space of functions from which the approximation is chosen.
45. In approximation theory, what is a 'norm' used for? — To measure the 'distance' or 'error' between two functions.
46. In the context of the Bellman equation V(s) = max_a [ R(s,a) + gamma * sum_{s'} P(s'|s,a) * V(s') ], what is the role of successive approximations? — To iteratively update the value function V(s) until it converges to the optimal value function.
47. What does 'function approximation' aim to achieve? — To find a simpler function that captures the essential characteristics of a more complex function or data.
48. Which of the following is a common goal in approximation in function space? — To find a simpler function that closely approximates a more complex function or data.
49. What is a common stopping criterion for the method of successive approximations? — All of the above.
All One Line Questions
E-Book Dynamic programming, approximation in function space, successive approximations Online Test Dynamic programming, approximation in function space, successive approximations Question Bank Dynamic programming, approximation in function space, successive approximations