High Dimensional Optimal Policies

This package implements a suite of algorithms for identifying optimal policies using the methodology of Kreindler et al. [1].

Installation

HighDimensionalOptimalPolicies.jl is not registered on the Julia registry. To download, run

import Pkg;
Pkg.add("https://github.com/pdeffebach/HighDimensionalOptimalPolicies.jl.git")

This quick-start solves for the optimal policy propblem outlined in the Tutorial. Of a set of 100 prizes, which 50 do we pick? The top 50 of course! Nonetheless, given the high dimensionality of the state space, this problem is a simple illustration for how various options in the package the set of optimal policies that get chosen.

We need three inputs,

initfun: A starting policy guess, of the form initfun(rng) where rng is a random number generator.
nextfun: Given a policy guess, what is the next policy guess? Of the form nextfun(rng, state).
objfun: What is the objective value of this policy?

(; initfun, nextfun, objfun) = HighDimensionalOptimalPolicies.quickstart()

(initfun = HighDimensionalOptimalPolicies.var"#43#46"{Int64, Int64}(100, 50), nextfun = HighDimensionalOptimalPolicies.var"#44#47"(), objfun = HighDimensionalOptimalPolicies.var"#45#48"{Vector{Float64}}([0.07813372094455777, 0.047141098935208806, 0.03977568635719537, 0.03847255501736185, 0.036497356662372714, 0.029792597052741367, 0.02561947427177983, 0.02296544336257491, 0.02288379269525107, 0.020837994602844502  …  0.0015064301685648654, 0.0014846606431991743, 0.0014570752335335833, 0.0014252347482119944, 0.001306504023507347, 0.00126203351896114, 0.0012331724761549853, 0.0009771321100815033, 0.0008103684570198063, 0.0005043701038627763]))

Get 200 policies drawn from the distribution of optimal policies using the get_best_policy function.

out = get_best_policy(
    IndependentSimulatedAnnealingSolver();
    initfun = initfun,
    nextfun = nextfun,
    objfun = objfun,
    max_invtemp = 50.0,
    invtemps_curvature = 2.0,
    n_invtemps = 5,
    n_inner_rounds = 100,
    n_independent_runs = 200)

MultiMCMCSolverOutput with 5 temperatures and maximum inverse temperature 50.0

Get the a vector of the best policy guesses with get_policy_vec

get_policy_vec(out)

101-element Vector{Vector{Bool}}:
 [1, 0, 1, 1, 1, 1, 0, 1, 0, 0  …  0, 0, 0, 1, 0, 1, 0, 1, 0, 0]
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 0  …  1, 1, 0, 1, 0, 0, 0, 1, 1, 1]
 [1, 1, 1, 1, 0, 0, 0, 1, 0, 1  …  1, 1, 0, 0, 0, 1, 0, 1, 1, 1]
 [1, 1, 0, 1, 1, 0, 1, 0, 1, 1  …  1, 0, 0, 1, 1, 1, 1, 0, 0, 1]
 [1, 0, 1, 0, 0, 1, 1, 1, 1, 1  …  1, 0, 1, 0, 1, 0, 1, 0, 0, 1]
 [1, 1, 0, 1, 1, 0, 1, 0, 1, 1  …  1, 0, 1, 1, 1, 0, 1, 1, 0, 0]
 [1, 1, 1, 1, 1, 1, 1, 0, 1, 1  …  1, 0, 1, 1, 0, 0, 1, 1, 0, 1]
 [1, 1, 0, 1, 1, 0, 1, 1, 1, 1  …  0, 1, 0, 0, 0, 0, 1, 1, 0, 0]
 [1, 1, 1, 1, 0, 0, 0, 0, 1, 0  …  1, 1, 0, 0, 0, 0, 1, 0, 0, 0]
 [1, 1, 1, 1, 1, 0, 1, 1, 1, 0  …  1, 1, 0, 0, 0, 1, 0, 0, 0, 1]
 ⋮
 [1, 1, 1, 1, 0, 1, 0, 0, 1, 0  …  0, 0, 1, 1, 0, 0, 1, 1, 0, 1]
 [1, 1, 1, 0, 1, 1, 1, 0, 1, 1  …  1, 0, 1, 0, 0, 1, 0, 0, 0, 1]
 [1, 1, 1, 1, 1, 0, 1, 1, 1, 1  …  0, 1, 0, 1, 0, 0, 0, 1, 0, 0]
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1  …  1, 1, 1, 0, 0, 0, 1, 0, 1, 1]
 [1, 1, 1, 1, 0, 0, 1, 1, 0, 1  …  0, 0, 1, 0, 0, 0, 0, 0, 0, 1]
 [1, 1, 1, 1, 1, 1, 0, 0, 0, 1  …  1, 0, 1, 0, 0, 0, 1, 1, 0, 0]
 [1, 1, 1, 1, 1, 0, 1, 1, 1, 0  …  1, 0, 0, 1, 1, 1, 0, 1, 0, 0]
 [1, 1, 1, 1, 1, 1, 0, 1, 1, 1  …  0, 1, 0, 1, 0, 0, 0, 1, 1, 0]
 [1, 0, 0, 1, 1, 0, 1, 0, 1, 1  …  1, 1, 0, 0, 0, 0, 1, 0, 0, 1]

get the vector of objective values with get_objective_vec

get_objective_vec(out)

101-element Vector{Float64}:
 0.5739761102349119
 0.6748979167286446
 0.5632919825611253
 0.597789653586218
 0.5622593673753741
 0.5925779899394757
 0.6419298523390141
 0.58119744895027
 0.5372782649778083
 0.6112734480796396
 ⋮
 0.5917364510841812
 0.5922372575317341
 0.650210063190699
 0.6688609614300842
 0.5855820026855645
 0.6268217498577492
 0.6145283134404902
 0.6637164070126829
 0.5724303262015549

Motivation

Policymakers are often tasked with identifying "optimal" policies. That is, the choices that policymakers can make which result in the highest level of welfare (however defined) for a population. Sometimes there are only a few levers available to the policymaker, such that their choice involves manipulating only a small number of key policies. For instance, "what should the interest rate paid on bank deposits in the Federal Reserve?" involves finding the optimal value of one key variable.

Often, however, policymakers have a multitude of levers at their disposal, and finding the "optimal" policy involves an optimization problem of hundreds, thousands, or even tens of thousands of different variables. For example, Kreindler et al. [1] asks what the optimal transportation network looks like in Jakarta, Indonesia. This task involves

Where should the buses go? Along a network with 1000s of nodes and an order of magnitude more edges.
How many buses should go on each route?
Which routes should have separate Bus Rapid Transit lanes? Which should have normal lanes?

In this instance, the state space of policy choices is so large that it is impossible to characterize a single "best" policy. Additionally, the problem is not convex, such that an interative procedure is unlike to find the globally optimum solution. Finally, policymakers might have other considerations not fully captured in an economist's simplified model of the economy, and would prefer a menu of candidate policies rather than one answer by itself. Finally, it may also be useful to learn what "qualities" are associated with a set of optimal policies rather than analyze one policy on its own.

While optimal transportation policy is the main motivation of this package and will serve as it's guiding example, the same reasoning can be applied to any economic problem where the state space of policy levers is large, for instance place-based policies where resources are distributed across many different locations, or a tax system where taxes must be levied on a wide variety of goods.

High Dimensional Optimal Policies

Installation

Quick Start

Motivation