A method and apparatus for marker aided autonomous vehicle localization are disclosed. Marker aided autonomous vehicle localization may include an autonomous vehicle identifying transportation network information, identifying an origin, identifying a destination, generating a plurality of candidate routes from the origin to the destination based on the transportation network information, wherein each route from the plurality of routes indicates a distinct combination of road segments and lanes, generating an action cost probability distribution for each action in each candidate route, generating a route cost probability distribution based at least in part on the action cost probability distribution, identify an optimal route from the plurality of candidate routes based at least in part on the route cost probability distribution, and operate the autonomous vehicle to travel from the origin to the destination using the optimal route.