Framing an indefinite horizon MDP, cost minimization with must-visit states
<p>Looking for some help in framing a problem of the indefinite horizon, cost minimization, with some must visit states.</p>

<p>We are given a budget b and a cost matrix M which represents the deduction for travel between states ( Mij represents the cost for traveling from i to j ), similar to a classic traveling salesman problem. In this case the time may be negative representing additions to the budget, Mij may not necessarily be equal to Mji. Also in this case M is 4x4, but this may not be the case, generally lets say that 3 &lt;= len(M) &lt;= 5, as I assume this may require some brute force methods with lots of operations...</p>

<pre><code>0 1 -3 1
6 0 2 2
4 2 0 3
1 2 3 0
</code></pre>

<p>Each row represents a given state i and each column then represents the cost of traveling toward j. </p>

<p>The problem is thus: given b and M, excluding state=0 and state=len(M) what is the maximum number of unique states we can travel to and end up at state=len(M) with b >= 0. </p>

<p>Given the above M, and b=0, then I think the ouput would be [2], the path is [0] -> [2] -> [3] and the full rollout looks like this:</p>

<pre><code>state nextstate deduction time
 --       0        ---     0
 0        2         -3     3
 2        3         3      0
</code></pre>

<p>I have attempted to solve this problem as a reinforcement learning problem with a e-greedy solution and a heuristic policy to select a next state, I have also thought of this like a TSP and looked at a solution using Floyd-Warshall but I am not quite sure how to fit the constraints within the problem set up. </p>

<p>I think that there is a way to find a direct solution, and my intuition seems to be able to look at a general M and a given b and come up with a solution, but I am not able to cleanly phrase the algorithm...</p>

<p>Some direction is appreciated on how to frame this cleanly and come up with a direct solution.</p>

<p>In case your cost matrix contains negative cycles then all the states can be eventually visited. You can use <a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm" rel="nofollow">Bellman-Ford</a> to detect the cycles so rest of the answer assumes that no such cycle exists.</p>

<p>The algorithm consists of three parts. First it finds all the paths with cost less than budget from start state to end state. For every such path the states visited and total cost is tracked. Then it finds all the loops originating from (and terminating to) end state and tracks the visited states &amp; total costs.</p>

<p>After all the paths and loops are known the algorithm starts to add loops to the paths. In case that loop adds new state and total cost is within the budget the addition is successful. Addition continues until there's no way to add a loop to existing paths. Finally the path containing most visited states is picked as a result.</p>

<p>Here's non-refined implementation of the above:</p>

<pre><code>M = [
    [0, 2, 2, 2, -1],
    [6, 0, 2, 2, -1],
    [6, 3, 0, 2, -1],
    [6, 3, 2, 0, -1],
    [6, 3, 2, 2, 0]
]

BUDGET = 1
SOURCE = 0
DEST = len(M) - 1

def all_paths_step(source, dest, visited, cost):
    for i in range(len(M)):
        if i in visited:
            continue
        new_cost = cost + M[source][i]
        new_set = visited | {i}
        if i == dest:
            yield new_set, new_cost
        elif i not in visited:
            yield from all_paths_step(i, dest, new_set, new_cost)

def all_paths(source, dest, cost=0):
    result = {}
    for states, cost in all_paths_step(source, dest, frozenset([source]), cost):
        result[states] = min(result.get(states, float('inf')), cost)

    return result

to_dest = all_paths(SOURCE, DEST)
loops = {}

for i in range(len(M)):
    if i == DEST:
        continue
    for states, cost in all_paths(i, len(M) - 1, M[len(M) - 1][i]).items():
        loops[states] = min(loops.get(states, float('inf')), cost)

possible = {visited: cost for visited, cost in to_dest.items() if cost &lt;= BUDGET}

process = set(possible.keys())
while process:
    process_next = set()
    while process:
        states = process.pop()
        for path, cost in loops.items():
            cost += possible[states]
            new_states = states | path
            if path &lt;= states or cost &gt;= possible.get(new_states, BUDGET + 1):
                continue
            possible[new_states] = cost
            process_next.add(new_states)
    process = process_next

print('result: {}'.format(max(possible, key=len)) if possible else 'none')
</code></pre>

<p>Output, visited states in no particular order:</p>

<pre><code>result: frozenset({0, 2, 3, 4})
</code></pre>

java python algorithm